백트래킹(퇴각검색)10 [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] 15652번: N과 M (4) https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 해결 과정 착안 1부터 \(N\)까지의 자연수를 중복을 허용하되, 비내림차순을 만족하는 순서로 뽑아 수열을 만든다. 따라서 다음 항을 구하는 함수를 실행할 때, 현재 항보다 큰 숫자로만 구할 수 있도록 조건문을 추가하고자 하였다. 이후, 수열의 길이가 \(M\)이 될 때까지 재귀를 통해 수열을 만들고 길이가 \(M\)이 되면 출력한다. 구현 이전 포스트의 코드와 대부분 유사하여 이전 포스트.. 2023. 5. 15. [Baekjoon] 15651번: N과 M (3) https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 해결 과정 착안 1부터 \(N\)까지의 자연수를 중복을 허용하여 뽑아 수열을 만든다. 만들어지는 모든 수열을 출력해야하므로 수열의 길이가 \(M\)이 될 때까지 재귀를 통해 수열을 만들고, 길이가 \(M\)이 되면 출력한다. 구현 이전 포스트의 코드와 대부분 유사하여 이전 포스트의 코드를 수정하여 문제를 해결하였다. 중복된 수를 다시 뽑는 것이 가능하므로, Visited 여부를 확인할 필요.. 2023. 5. 13. [Baekjoon] 15649번: N과 M (1) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 해결 과정 착안 주어지는 입력 \(N\), \(M\)에 따라 \(N\) 개의 정점을 가지는 그래프를 만든 다음, 각 정점에 대하여 인접 정점을 오름차순으로 방문 가능하도록 자신을 제외한 모든 정점들과 연결한다. 만들어진 그래프로부터 \(M\) 개의 정점이 순회될 수 있는 모든 경로를 순서대로 출력하기 위하여 백트래킹(backtracking, 퇴각검색) 알고리즘을 구현하고자 하였다. // 의.. 2023. 5. 11. 이전 1 2 다음
