1. 동전 거스름돈 총금액 800, 동전 종류 : 10, 50, 100, 400, 500 그리디 : 500, 100, 100, 100 -> 최적해가 아니다 소스코드 # coin[] : 동전의 금액을 젖아 # choice[] : 선택한 동전 집합 # best : 거스름돈에 대한 최소 동전 개수 def coinChange(choice, N, money): global best if best N best = N else: for i in range(len(coin): if money - coin[i] >= 0: choice[N] = coin[i] coinChange(choice, N+1, money-coin[i])

1. 순열 예시) 원소 개수 n = 4 -> 집합 = {A, B, C, D}, 4!인 24가지의 경우가 존재 따라서 상태 공간 트리에서의 단말노드의 수는 24개이다. 24개의 후보해가 존재한다는 것이고 이것은 단말노드의 수와 같다. 노드 방문 시마다 원소를 가리키는 인덱스 값을 저장 같은 원소 수를 갖는 부분집합과 순열의 상태 공간 트리의 높이는 같다. 순열의 경우 높이가 다른 노드는 선택지 수가 동일하지 않다. 선택할 때마다 다음 선택의 선택지 수가 하나씩 줄어든다. 소스코드 # order[] : 순열의 순서를 저장하는 리스트 def permutation(order, k, n): if k == n: # 다 선택하면 print_order_array(order, n): # 출력 else: check = [..

1. n-Queens 문제 n x n 체스판에서 n개의 퀸들을 서로 위협하지 않도록 배치하는 문제 2. 백트래킹 초기 상태에서 목표 상태로 가는 경로를 탐색하는 기법 해를 찾는 도중 해가 아니면 되돌아가서 다시 해를 찾는 기법 최적화(optimize)문제와 결정(decision)문제를 해결할 수 있다. 최적화 문제 미로 찾기, Subset sum 등 결정 문제 n-Queen, Map coloring 등 루트까지 되돌아갔는데 더이상 선택지가 없다면 답이 없는 것이다. 백트래킹의 핵심은 상태 공간 트리를 탐색하는 것! 해를 찾기 위한 선택의 과정을 트리로 표현 트리의 내부 노드는 해로 가는 중간 상태 트리의 단말 노드는 하나의 후보해에 대한 최종 상태 상태 공간 트리를 깊이 우선 탐색(DFS)하는 방법이 백..