Algorithm/덱

[알고리즘] 백준 3190 뱀 // 덱 bfs, 구현, 뱀-꼬리 문제는 덱

https://www.acmicpc.net/problem/3190 * 풀이1(오답)한방향 (->) 진행만 구현후 회전함면 되는지? 안됨참고 : 시계회전은 a[i][j] = a[j][n-i-1] 임반시계 : [n-j-1][i]각 방향에 따라 dfs 돌기로함예제3에서오답 -> 표 디버깅 -> 회전시 꼬리의 위치갱신이 어려움꼬리가 (1,4) 였는데 바로 (2,4)로 되버림 // (1,5)가 되야 맞음꼬리의 상태를 어떻게해야 저장하지? -> 덱 * 풀이21-idx는 무조건 0-idx로 바꿔서 풀기!visit으로 몸통을 체크할것head가 지나가면서 visit을 기록하는 걸로 생각하면 쉬움.#include using namespace std;int sec,y,x;int n,k,L, a[104][104], vis[1..

[알고리즘] 백준 5430 AC // 덱, 구현

https://www.acmicpc.net/problem/5430  * 풀이1#include using namespace std; int t;int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >>t; while(t--) { string s1,s2; int n; cin>>s1>>n>>s2; deque d; if(s2!="[]") { s2 = s2.substr(1,s2.size()-2); // [, ] 날리기 string buf=""; for(auto c : s2) { if(c==',') { d...

백준 5430 AC c++ // 파싱, 덱 사용법

https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 0. 덱 뒤쪽에서도 삽입,삭제 가능한 업그레이드 벡터라고 생각하면 된다. 양쪽끝에서 삽입,삭제하는 문제일때 사용하면 된다. 1. 시행착오 끝에서 2번째줄이 없는경우 : 정답이 빈칸인경우 "["이 팝되서 "]" 만출력된다. 예외처리조건추가후 []이 출력됨. string ret = "["; while (d.size()) { if (!rev) { ret += to_string(d.front()); ret += ","; d.pop_front(); } else ..

백준 5430 cpp // string find,+=시간복잡도, split 구현방법, 예외처리방법

https://www.acmicpc.net/problem/5430] 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net *예외처리방법 최악입력 : [] 일때 별도로 처리해준다. *string find,+=시간복잡도 find : O(n) for(i=0~n) s+='A' //O(n) for(i=0~n) s=s+'A' //O(n^2) 결론 : += 를 사용해라. * 의사코드 1.배열을 파싱해서 데큐에 담기 2.명령어를 하나씩돌면서 R이면 참조위치를 앞뒤 바궈주기 D이면 참조위치에 맞춰서 pop하기 3. 결과값완성하기 참조위치가 앞이면 d의 원소 앞부터 추가 참조위치가 뒤면 ..

백준 1021 cpp // 데큐, 규칙찾기, find함수 사용법

https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net ※ 주의 : pop은 앞에서만 가능. *의사코드 - 모두 앞으로 보낼때 vs 모두 뒤로 보낼때 이동횟수가 적은것을 선택한다. while(m-- // 목표) 1. while(앞!=목표){ cnt1++, q1, 뒤로보내는 로직 } while(앞!=목표){ cnt2, q2, 앞으로 보내는로직 } 2. 두 카운트 중 최소값 선택 d=최소값인큐 d.pop_front() ret+=cnt *내 코드 #in..

백준 10866 cpp // 덱 사용법

https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net * 덱? 양방향으로 넣고 뺄수있는 큐를 말한다. #include using namespace std; int n; deque d; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for (int i = 1; i > op; if (op == "push_front") { int temp = 0; ..