Backtracking_동전 던지기

동전 던지기

- 3개의 동전들을 던질 때, 나올 수 있는 값들의 모든 가능한 조합들을 출력하는 문제

- 가정) 앞면 : 0, 뒷 면 : 1

- 알고리즘)

for (c1 = 0; c1<= 1; c1++)
     for (c2 = 0; c2 <= 1; c2++)
	      for (c3 = 0; c3 <= 1; c3++)
	       	   
//[c1, c2, c3]을 출력한다

 

동전 던지기의 상태 공간 트리

순열 생성

- <1, 2, . . . , N>의 모든 순열을 생성하라.

- 예: N = 3인 경우

  <1, 2, 3>, <1, 3, 2>, <2, 1, 3>,

  <2, 3, 1>, <3, 1, 2>, <3, 2, 1>

아이디어

배열의 첫 번째, 두 번째와 세 번째 요소를 각각 첫 번째 요소와 교환한 후 배열의 나머지 부분에 대해 순열을 생성하는 일을 재귀적으로 반복한다.

 

 

되추적 알고리즘

permute(A[ ], k) 	// <A[k], A[k + 1], ⋯ , A[N – 1]>의 모든 순열을 생성
// 입력: A[0 . . N – 1] – 순열을 저장하는 배열,  k – 배열 A의 지수
// 출력: <A[k], A[k + 1], ⋯ , A[N – 1]>의 모든 순열
1  if (k = N) { A[0 . . N – 1] 을 출력한다; return  }
2  for (i = 1; i <= N; i++)     // A[k]를 i로 정하기 전에 가능한지 확인
3      if (promising(A, k, i)) {  // A[k]를 i로 정하는 것이 가능한 경우
4         A[k] = i
7         permute(A, k + 1) } // <A[k+1], ⋯ , A[N–1]>의 모든 순열을 생성

// 최초 호출: permute(A, 0)