본문 바로가기

C++ 코딩 문제 풀이151

[Baekjoon] 2559번: 수열 https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 문제 해결 과정 착안 $n$ 번째 숫자 $a_n$ 부터 $(n+K-1)$ 번째 숫자 $a_{n+K-1}$ 까지 연속된 $K$ 개의 숫자를 더한 값을 $S_n$ 이라고 하면, $$S_{n+1} = S_n + a_{n+K} - a_n \quad(n \geq 1,\space 2 \leq K \leq N)$$ 이므로, 이전 단계의 합의 값을 알면 숫자 두 개만 더하고 뺌으로써 다음 번째의 연.. 2023. 6. 18.
[Baekjoon] 1966번: 프린터 큐 https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 문제 해결 과정 착안 얼핏 보았을 때 우선순위 큐와 같은 동작인 것처럼 보이나, 현재 문서의 우선순위보다 우선순위가 높은 문서가 큐에 하나라도 있는 경우 현재 문서를 큐의 가장 뒤쪽으로 보내는 작업 때문에 std::priority_queue 클래스를 사용해봤자 해결에 별 도움이 되지 않을 것이라 판단하였다. 본래 큐 클래스는 Front의 값에 대해서만 확인 가능하고 큐의 중간에 있는 요소들은 접근할 .. 2023. 6. 17.
[Baekjoon] 9663번: N-Queen https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 해결 과정 착안 백트래킹(backtracking, 퇴각검색) 알고리즘에 대한 대표적인 문제이나, 직접 풀어보는 건 처음이라 백트래킹이 아직 익숙하지 않아서 착안이 어려웠다. 생각해내기 가장 어려웠던 부분은 단계별로 배치되는 퀸에 의해 8 방향 직선으로 가려지는 체스판 상의 위치를 어떻게 표시해야 문제를 쉽게 해결할 지를 생각해내는 것이었다. 그래서 처음에는 체스판을 계속 새로 만들고 퀸의 위치마다 직선 방향.. 2023. 6. 16.
[Baekjoon] 1463번: 1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 해결 과정 착안 자연수 $n=1, 2, ..., N$ 에 대해 $n=1$ 부터 반복문을 통해 $n$의 값을 증가시키면서 $3n, 2n, n+1$ 에 대한 연산 횟수의 값을 동적계획법(dynamic programming)을 통해 최솟값으로 갱신함으로써 문제를 해결하고자 했다. 구현 주어지는 수 $N$ 보다 큰 수에 대해서는 계산할 필요가 없으므로, $n=i$ 일 때, $3i, 2i, i+1$ 의 값이 $N$ 보다 작거나 같을 때에만 계산을 하도록 하였다. $3i, 2i, i+1$ 의 연산 횟수가 이미 계산되.. 2023. 6. 15.
[Baekjoon] 11866번: 요세푸스 문제 0 https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 문제 해결 과정 착안 입력받은 $N$ 과 $K$ 의 값에 따라 큐(queue) 자료 구조를 사용해 요소를 하나씩 dequeue하고 반복문의 현재 루프가 $K$ 의 배수 번째에 해당하는 루프이면 숫자를 출력, 아니라면 다시 enqueue를 수행하여 문제를 해결하고자 했다. 구현 크기가 고정된 큐 자료 구조를 사용하며, enqueue 및 dequeue 연산을 반복적으로 수행하기 때문에 효율적인 메모리 활용을 위하여, 문제에 맞게 원형 큐(circular queue, 환형 큐) 자료 구.. 2023. 6. 14.
[Baekjoon] 11047번: 동전 0 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제 해결 과정 착안 동전의 수를 최소화하기 위해 가능한 한 가장 높은 단위의 화폐부터 사용하여 주어지는 금액을 맞추고자 하였다. 구현 보유하고 있는 동전의 가치가 오름차순으로 주어지므로, 스택(stack) 자료 구조를 사용해 입력받는 순서로 동전의 가치가 맞추고자 하는 금액보다 작은 경우 이를 스택에 넣도록 구현하였다. 입력이 완료.. 2023. 6. 13.

티스토리툴바