C++ 코딩 문제 풀이/백준113 [Baekjoon] 11729번: 하노이 탑 이동 순서 https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 문제 해결 과정 착안 첫 번째 장대에 쌓여있는 \(N\) 개의 원판을 최소 이동 횟수로 세 번째 장대로 옮기기 위해서는, \(N-1\) 개의 원판을 두 번째 장대로 옮긴 뒤 가장 아래의 원판을 세 번째 장대로 옮기고 다시 \(N-1\) 개의 원판을 세 번째 장대로 옮기는 과정을 수행하여야 한다(이 방법이 정말 최소 횟수로 이동하는 방법인지에 대한 의문이 들 수도 있는데, 이와 관련해서.. 2023. 5. 22. [Baekjoon] 4779번: 칸토어 집합 https://www.acmicpc.net/problem/4779 4779번: 칸토어 집합 칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다. 전체 집합이 유한이라고 가정하고, www.acmicpc.net 문제 해결 과정 착안 주어진 문제에서의 배열을 3등분하여 왼쪽, 가운데, 오른쪽 부분 배열로 나누고 이때 왼쪽과 오른쪽의 부분 배열에 대해서 같은 과정을 반복적으로 수행하여 최종 답을 얻을 수 있다. 즉, 부분 문제들의 해를 합하여 최종 해를 구할 수 있는 문제이므로 분할 정복(divide and conquer) 알고리즘을 구현하여 문제를 해결하고자 하였다. 인수로 전달되는 배열의 길이가 1이 될.. 2023. 5. 21. [Baekjoon] 24260번: 알고리즘 수업 - 병합 정렬 1 https://www.acmicpc.net/problem/24060 24060번: 알고리즘 수업 - 병합 정렬 1 첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 500,000), 저장 횟수 K(1 ≤ K ≤ 108)가 주어진다. 다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109) www.acmicpc.net 문제 해결 과정 착안 문제에서 주어진 합병 정렬(병합 정렬, merge sort) 의사 코드를 그대로 구현하여 문제를 해결하였다. 구현 알고리즘의 의사 코드를 그대로 제공하여 편리하게 구현할 수 있었다. 처음에는 중간 결과를 합치는 merge 함수에서 사용되는 tmp 배열을 크기에 맞게 계속 할당/해제하는 방식으로 구현했는데, tmp 배열을 아예 최.. 2023. 5. 20. [Baekjoon] 14888번: 연산자 끼워넣기 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 문제 해결 과정 착안 연산자 우선순위가 아닌, 연산이 주어지는 순서대로 순차적으로 계산하는 문제이고 주어지는 연산자의 종류나 수를 알 수 없기 때문에 최댓값, 최솟값을 구하기 위해서는 모든 경우에 대해 계산을 해야한다고 판단하여 백트래킹(퇴각검색) 알고리즘으로 구현하고자 하였다. 구현 각각의 사칙연산에 대한 연산을 수행하는 함수를 만들어 문제.. 2023. 5. 19. [Baekjoon] 1912번: 연속합 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 해결 과정 착안 주어지는 임의의 수열 내의 연속된 숫자들의 합 중에서 가장 큰 값을 찾아야하는데, 이때 몇 개의 연속된 숫자의 합이 최대일지는 알 수 없으므로 반복적으로 연속합을 구하고 비교하는 것을 요구한다. 따라서 기존에 구해놓은 연속합의 값을 저장하고, 추가적인 연속된 숫자를 입력받으면 더해서 비교한 뒤 필요하면 다시 저장하여 사용하는 방식으로 동적계획법(dynamic programming) 알고.. 2023. 5. 18. [Baekjoon] 9184번: 신나는 함수 실행 https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 문제 해결 과정 착안 구하고자 하는 값이 어떠한 점화식의 형태를 이용하여 구해지도록 함수를 구현해야 하므로, 동적계획법(dynamic programming)을 사용하여 구현해보고자 하였다. 구현 메모이제이션에 사용할 배열들을 편의상 전역 변수로 만들어 모든 함수에서 접근 가능하도록 구현하였다. * int result[21][21][21] : 계산한 값을 저장. * bool computed[21][21.. 2023. 5. 17. 이전 1 ··· 11 12 13 14 15 16 17 ··· 19 다음
