와드의 블로그

문제1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있습니다. 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 경로를 계획하려고 합니다. 단, 한 번 갔던 도시로는 다시 갈 수 없습니다. (맨 마지막에 출발 도시로 돌아오는 것 제외) 각 도시간 이동 비용이 주어졌을 때, 가장 적은 비용이 드는 순회 경로를 구하는 프로그램을 작성하는 문제입니다.입력: 도시의 개수 N (2 ≤ N ≤ 10), 비용 행렬 W (비용은 1,000,000 이하, 갈 수 없는 경우 0)출력: 외판원의 순회에 필요한 최소 비용핵심 최적화: 시작점 고정이 문제는 모든 도시를 방문하고 다시 처음으로 돌아오는 사이클(Cycle)을 찾는 문제입니다. 순회 경로가 0..

문제1부터 N까지의 수로 이루어진 순열이 주어졌을 때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하는 문제입니다.입력: 첫째 줄에 N (1 ≤ N ≤ 10,000)이 주어집니다. 둘째 줄에 순열이 주어집니다.출력: 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력합니다. 만약 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력합니다.풀이: O(N) 시간 복잡도의 수학적 알고리즘 (Next Permutation)N이 최대 10,000이므로 모든 순열을 생성하는 재귀(DFS) 방식은 사용할 수 없습니다. 현재 배열의 상태를 뒤에서부터 훑으며 단 한 번의 순회(O(N))만으로 다음 상태를 유추하는 알고리즘을 적용해야 합니다.알고리즘 단계 분석피벗 지점(i) 찾기: 배열의 뒤에서부터 탐색하..

문제10부터 10까지의 정수로 이루어진 N개의 수열 A가 있습니다. 이 수열의 i번째 수부터 j번째 수까지의 합의 부호(+, -, 0)가 주어질 때, 부호 조건들을 모두 만족하는 수열 A를 찾는 프로그램을 작성하는 문제입니다.입력: 첫째 줄에 수열의 크기 N (1 ≤ N ≤ 10)이 주어집니다. 둘째 줄에는 N(N+1)/2 길이의 문자열 형태의 부호 배열이 주어집니다.출력: 부호 조건을 만족하는 수열 A를 공백으로 구분하여 출력합니다. (조건을 만족하는 수열이 여러 개일 경우 아무거나 하나만 출력합니다.)풀이: 백트래킹을 활용한 부분 합 유효성 검사이 문제는 10개의 자리에 -10부터 10까지 21개의 숫자를 무작위로 채우면 21^10 번의 탐색이 필요하여 시간 초과가 발생합니다. 따라서 백트래킹(DFS..