기록보관소

숨바꼭질은 너비우선탐색을 활용하여 해결할 수 있는 문제입니다. 수빈이가 이동할 수 있는 3가지 방법을 탐색 방법으로 생각하여 동생의 위치까지의 최단 거리를 계산하는 문제로 바꾸어 생각할 수 있습니다. 따라서 너비우선탐색이 사용될 수 있습니다. 작성한 코드는 다음과 같습니다. #include #pragma warning(disable : 4996) int N, K; struct que { int x, time; }; struct que queue[100000+20]; int wp, rp; int visit[100000+20]; int main(void) { scanf("%d %d", &N, &K); visit[N] = 1; queue[wp].x = N; queue[wp++].time = 0; while (..

AC문제는 큐를 활용한 문제이다. 큐의 pop을 활용하는 문제로 뒤집기 함수로가 추가된 문제이다. 뒤집기의 경우 pop할 때 경우에 따라 head와 tail 중 1개를 선택하여 1만큼 이동시키면 된다. 주의할 점은 테스트 케이스의 입력이 큰 편이라 수행시간에 여유가 없다는 점이다. 가능하면 O(n+p)의 시간에 수행하여야 한다. 문제를 풀면서 놓쳤던 부분은 다음과 같다. 먼저 모든 처리를 하고 출력을 할 때 출력형식에 맞추어 출력하는 것에 모든 것의 성패가 달렸다는 점을 느낄 수 있었다. 다 풀었다고 느꼈을 때 자만하지 말고 끝까지 주의를 기울여 풀어야 한다는 점이다. 입력에서도 입력 버퍼에 무엇이 있는지 주의를 기울여야 한다는 점이다. ps에서 끝까지 방심하지 말라는 교훈을 얻은 것 같다. 작성한 코드..

프린터 큐는 큐를 활용해서 푸는 문제이다. 다만 단순히 큐만을 사용하는 문제는 아니었다. 큐에 있는 원소의 우선순위 중 가장 높은 수를 알아야 하는 데 이때 구글링을 해보면 우선순위 큐를 사용하는 유저들이 많았다. 아직 우선순위 큐에 대해 다루지 않았기 때문에 이번 풀이에서는 계수를 이용해서 문제를 풀었다. 해당 우선순위를 가지는 값의 개수를 저장하는 배열을 선언하고, 이 배열을 조사함으로써 현재 큐에서 우선순위가 가장 큰 경우를 찾고 그 값에 따라 큐에서 pop을 한 값을 다시 push할지 하지 않을 지 결정하는 식으로 해결하였다. 관찰한 값을 표시하기 위해 flag 변수가 필요했고, 구조체를 활용하여 flag와 우선순위 값을 묶고, 구조체를 원소로 하는 배열을 선언하였다. 다른 풀이에서는 구조체가 아..

요세푸스 문제 0은 큐를 활용하여 풀 수 있는 문제이다. 사람들이 큐에서 K-1번 쉬프트 로테이션을 한 후 pop을 하여 사람의 번호를 추출함으로써 해결할 수 있다. 작성한 코드는 다음과 같다. #include #define size 2000 //http://ark-hive.tistory.com/ //사람들이 큐에서 쉬프트로테이션을 하면 어떻게 될까? int N, K; int queue[size]; int head, tail; int pop() { head += 1; head %= size; return queue[(head +size - 1)%size]; } void push(int x) { queue[tail] = x; tail += 1; tail %= size; } int main(void) { s..

카드 2 문제는 큐를 활용하는 문제이다. 카드 덱의 위쪽은 head, 카드 덱의 아래쪽을 tail로 생각하면 간단하게 해결할 수 있다. 카드를 바닥에 버리는 것은 pop을 하는 것으로, 위쪽의 카드를 아래쪽으로 넣는 것을 pop 후 push로 생각할 수 있다. 이러한 과정을 카드가 1장이 남을 때까지 반복하여 마지막에 큐에 남은 원소를 출력하면 된다. 작성한 코드는 다음과 같다. #include #define size 1000000 //http://ark-hive.tistory.com int N; int queue[size]; int head, tail; int pop() { head += 1; head %= size; return queue[(head+size- 1)%size]; } void push(..

원소를 삽입할 때 Enqueue, 원소를 제거할 때 Dequeue를 한다. 큐는 FIFO(first in, first out, 선입선출)의 특성을 같는다. 큐는 머리(head)와 꼬리(tail)을 갖는 데, 원소는 꼬리로 삽입되고 머리에서 제거된다. tail은 원소가 삽입될 위치를 가리키며 head는 삭제될 원소를 가리킨다. 따라서 head=tail이면 큐는 비어있으며, 이때 원소를 삭제하려고 하면 underflow가 발생한다. head=tail+1 또는 head=1일 때 tail이 배열의 마지막 원소를 가리키는 상태이면 큐가 가득찬 상태이며, 이때 원소를 삽입하려고 하면 overflow가 발생한다. 수행시간 Enqueue와 Dequeue에는 O(1)만큼의 시간이 걸린다.