Page 187 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

●
●
●
●
？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？

1 2 3 3 4

？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？
●
●
● ●
5 6 7 8

[그림 5-16] 0열에 퀸을 1개만 배치한 조합

예를 들어, ‘그림 5-16의 1 에 대해 1열에 퀸을 배치하는’ 조합을 나열하면 그림 5-17과 같
이 8가지 방법으로 나열할 수 있습니다.
즉, 그림 5-16 1 의 문제를 ‘8개의 부분 문제’로 나눈 결과가 그림 5-17입니다.

● ● ● ● ●
●
●
●
？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？

1 2 3 4
● ● ● ●

？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ ？
●
●
●
●
5 6 7 8

[그림 5-17] 그림 5-16의 1 에 대해 1열에 퀸을 1개만 배치한 조합

그림 5-16의 2 ~ 8 에 대해서도 마찬가지로 생각하면 0열과 1열에 배치하는 방법은 64가
지입니다. 이 작업을 반복하여 7열까지 배치하는 조합을 모두 나타내면 그림 5-18과 같으며,

총 16,777,216가지입니다.

05•재귀 알고리즘 187