13.6 연습 문제¶
13.6.1 개념 확인¶
1. 이 순열 알고리즘은 결과를 빠뜨리는가¶
한 백트래킹 알고리즘이 1, 2, 3 순서로 숫자를 시도하며 모든 순열을 생성한다. 숫자 x를 선택할 때마다 다음을 수행한다.
- 현재 경로의 끝에
x를 추가한다. x를 ‘사용함’으로 표시한다.- 재귀 호출로 다음 위치를 채운다.
재귀 호출이 반환된 뒤, 학생은 경로 끝의 x만 삭제하고 다음 숫자를 계속 시도했다.
- 알고리즘이 처음 얻는 순열은 무엇인가? 순열 6개를 모두 얻을 수 있는가?
- 재귀 호출에서 이전 단계로 돌아가기 전에 경로 끝의 숫자를 삭제하는 것만으로 충분한가? 충분하지 않다면 무엇을 더 해야 하는지 이유와 함께 설명하라.
참고 답안
-
처음 얻는 순열은
[1, 2, 3]이지만, 모든 순열을 얻을 수는 없다. 반환하면서 경로는 짧아져도 숫자 1, 2, 3은 여전히 모두 ‘사용함’으로 표시되어 있어 이후 분기에서 선택할 숫자가 없기 때문이다. -
충분하지 않다. 경로 끝의
x를 삭제한 뒤에는x를 다시 ‘사용하지 않음’으로 표시해야 한다. 현재 경로와 사용 여부 표시가 함께 탐색 상태를 나타낸다. 선택할 때 두 곳을 수정했으므로 되돌아갈 때도 두 곳을 모두 복원해야 다른 분기에서x를 다시 선택할 수 있다.
2. 숫자를 선택하는 순서가 중요한가¶
정렬된 배열 [2, 3, 5]와 목표 값 5가 주어지며, 각 숫자는 반복해서 선택할 수 있다.
알고리즘에서는 각 탐색 경로의 숫자가 작은 것부터 큰 것 순으로만 나타나도록 제한한다.
- 서로 다른 어떤 조합을 얻을 수 있는가?
- 같은 숫자들을 다른 순서로 반복해서 탐색할 필요가 없는 이유는 무엇인가? ‘작은 것부터 큰 것 순’이라는 제한은 어떤 역할을 하는가?
- 현재 경로가
[3]이고 2가 더 필요한 상황에서 다음 후보 숫자가 3이다. 이때 이 단계의 나머지 후보를 모두 확인하지 않고 멈출 수 있는 이유는 무엇인가?
참고 답안
-
서로 다른 조합은
[2, 3]과[5]다. -
이 문제에서는
[2, 3]과[3, 2]를 같은 조합으로 취급하므로 숫자를 선택하는 순서는 답에 반영하지 않는다. 경로의 숫자가 작은 것부터 큰 것 순으로 나타나도록 정하면 탐색 중에[3, 2]같은 중복 조합을 바로 건너뛸 수 있다. -
현재 2가 더 필요한데 후보 숫자 3은 이미 2보다 크다. 배열이 정렬되어 있으므로 3 뒤의 후보는 더 크기만 할 뿐이고, 모두 현재 조합에 추가할 수 없다. 따라서 이 단계의 확인을 바로 끝낼 수 있다.
3. 다음 퀸은 어디에 놓을 수 있는가¶
4 × 4 체스판에 행별로 퀸을 놓으며, 행과 열의 인덱스는 모두 0부터 시작한다.
현재 (0, 1)과 (1, 3)에 퀸을 놓았고, 이제 인덱스 2인 행에 다음 퀸을 놓으려 한다.
- ‘같은 열’이라는 이유로 제외되는 열은 어디인가?
- 남은 열 가운데 ‘같은 대각선’이라는 이유로 제외되는 위치는 어디인가?
- 인덱스 2인 행에서 시도해 볼 수 있는 위치는 어디인가?
참고 답안
-
인덱스 1과 3인 열에 이미 퀸이 있으므로
(2, 1)과(2, 3)은 제외된다. -
남은 위치 중
(2, 2)는(1, 3)과 같은 대각선에 있으므로 역시 제외된다.(2, 0)은 이미 놓인 두 퀸 중 어느 것과도 같은 열이나 같은 대각선에 있지 않다. -
인덱스 2인 행에서 시도할 수 있는 위치는
(2, 0)뿐이다.이 단계에서는 현재 배치가 조건에 맞는다는 것만 확인한 셈이다. 이후 체스판을 완성할 수 없다면 여전히 되돌아가 더 앞 단계의 다른 선택을 시도해야 한다.
13.6.2 프로그래밍 연습¶
1. 중복 원소가 없는 모든 순열¶
정수 배열 nums에는 원소가 적어도 하나 있으며, 모든 원소가 서로 다르다.
각 원소를 한 번씩 사용하여 만들 수 있는 모든 순서를 나열하고, 각 순서를 배열로 반환하라.
결과에서 순열들이 나오는 순서는 상관없다.
백트래킹을 사용하고, 각 위치의 원소가 현재 순열에 이미 선택되었는지 불리언 배열로 기록하라.
풀이 힌트
- 재귀 깊이는 순열의 몇 번째 위치를 채우는 중인지를 나타낸다.
- 각 단계에서는 아직 사용하지 않은 원소만 시도한다.
- 경로 길이가
nums의 길이에 도달하면 경로의 복사본을 답에 추가한다.