기록보관소

배수와 약수 문제는 정수의 특성을 활용하는 문제이다. 서로 같지 않은 자연수는 약수 관계, 배수 관계, 아무것도 아닌 관계 중 1가지를 가지게 된다. 이 점을 유의하여 나머지를 기준으로 분류하여 요구하는 문장을 출력하면 된다. 작성한 코드는 다음과 같다. #include int num1, num2; int main(void) { while (1) { scanf("%d %d", &num1, &num2); if (num1 == 0 && num2 == 0) break; else { if (num2 % num1 == 0) { printf("factor\n"); } else if (num1 % num2 == 0) { printf("multiple\n"); } else { printf("neither\n"); } ..

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

회전하는 큐는 데크를 사용하여 푸는 문제입니다. front에서만 pop이 될 수 있으므로 뽑아낼 원소의 위치와 front사이의 가능한 두 개의 거리를 비교하여 거리가 작은 쪽으로 로테이션합니다. 뽑아낼 원소를 모두 뽑아내기 위해 로테이션하는 총 횟수를 계산하여 출력함으로써 문제를 해결할 수 있습니다. 작성한 코드는 다음과 같습니다. #include #define size 100 int N, M; int extracted[100]; int index_extracted; int total_op; int deque[size]; int front = 0, back = 1; int temp_front, temp_back; void rotate_clock() { deque[back]=deque[(front+1+si..

덱은 양방향에서 입력과 출력이 모두 가능한 자료구조입니다. 양방향의 입출력으로 인해 환형의 형태를 가진다는 점을 주의하며 이전의 큐 문제와 비슷하게 코드를 작성를 하여야 합니다. 2021.07.08 - [알고리즘/문제풀이] - [BOJ 18528번]큐 2 [BOJ 18528번]큐 2 큐 2 문제는 자료구조 큐를 활용하여 해결할 수 있는 문제이다. 자료구조 큐에 대한 학습을 하였다면 어려움없이 무난하게 풀 수 있는 문제이다. 큐에 대한 내용은 다음 링크에 확인할 수 있다. 2 ark-hive.tistory.com 작성한 코드는 다음과 같습니다. #include #define size1 20020 int N; int temp; int x; int deque[size1]; int front; int back=..

프린터 큐는 큐를 활용해서 푸는 문제이다. 다만 단순히 큐만을 사용하는 문제는 아니었다. 큐에 있는 원소의 우선순위 중 가장 높은 수를 알아야 하는 데 이때 구글링을 해보면 우선순위 큐를 사용하는 유저들이 많았다. 아직 우선순위 큐에 대해 다루지 않았기 때문에 이번 풀이에서는 계수를 이용해서 문제를 풀었다. 해당 우선순위를 가지는 값의 개수를 저장하는 배열을 선언하고, 이 배열을 조사함으로써 현재 큐에서 우선순위가 가장 큰 경우를 찾고 그 값에 따라 큐에서 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(..

큐 2 문제는 자료구조 큐를 활용하여 해결할 수 있는 문제이다. 자료구조 큐에 대한 학습을 하였다면 어려움없이 무난하게 풀 수 있는 문제이다. 큐에 대한 내용은 다음 링크에 확인할 수 있다. 2021.07.07 - [알고리즘/이론] - [알고리즘/이론]큐 [알고리즘/이론]큐 원소를 삽입할 때 Enqueue, 원소를 제거할 때 Dequeue를 한다. 큐는 FIFO(first in, first out, 선입선출)의 특성을 같는다. 큐는 머리(head)와 꼬리(tail)을 갖는 데, 원소는 꼬리로 삽입되고 머리에서 제거된다 ark-hive.tistory.com 구현할 때 주의할 점은 getchar 함수를 사용할 때 다음과 같이 괄호를 써주어야 한다는 점이다. 연산자의 우선순위규칙 때문에 비교연산이 우선 수행된..