📖 List 3

📌 완전 검색 (Exhaustive Search) (= 브루트포스)

✅ Baby-gin Game

• 0~9 사이 숫자 카드에서 임의 카드 6장을 뽑을때 3장의 카드가 연속적인 번호를 갖는 경우를 run이라 하고, 3장의 카드가 동일한 번호를 갖는 경우를 triplet이라고 한다.

• 6장 카드가 run과 triplet로만 구성된 경우를 baby-gin이라고 부름

• 6자리 숫자를 입력받아 baby-gin 여부를 판단하는 프로그램을 작성하자

• 667767은 두 개의 triplet이므로 baby-gin

• 054060은 한 개의 run과 한 개의 triplet이므로 baby-gin

• 101123은 한 개의 triplet이지만 023이 run이 아니므로 baby-gin이 아니다.
  (123이 run으로 쓰여도 011이 run이나 triplet이 아님)

• 위 방식의 완전 검색 방법은 6!으로 720가지

✅ 완전 검색

• 완전 검색 방법은 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법

• Brute-force 혹은 Generate-and-Test 기법

• 모든 경우의 수 테스트 후, 최종 해법 도출

• 일반적으로 경우의 수가 상대적으로 적을 때 유용

• 수행 속도는 느리지만, 신뢰도가 높음.

  • 해답을 찾아내지 못할 확률이 작다.

✅ 완전 검색을 활용한 Baby-gin 접근

• 6개 숫자로 만들 수 있는 모든 숫자를 나열 (중복 포함) - 순열 생성

• 앞 세자리와 뒤 세자리를 잘라 run triplet 여부를 테스트하고 판단

✅ 순열(Permutation)

• 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것

• 서로 다른 n개 중 r개를 택하는 순열 : nPr

nPr = n (n-1) ... * (n-r+1)

nPn = n! => Factorial

ex> {1, 2, 3}을 포함하는 모든 순열을 생성하는 함수

• 동일한 숫자가 포함되지 않았을 때 각 자리 수 별로 loop을 이용해 아래와 같이 구현할 수 있다.

for i1 from 1 to 3 {
	for i2 from 1 to 3 {
    	if i2 != i1 {
        	for i3 from 1 to 3 {
            	if i3 != i1 and i3 ! i2 {
                	print(i1, i2, i3)
                }
            }
        }
    }
}

📌 탐욕 알고리즘 (Greedy Algorithm)

✅ 탐욕 알고리즘

• 탐욕 알고리즘은 최적해를 구하는 데 사용하는 방법

  • 최적해로는 최솟값, 최댓값 등으로 생각하면 됨

• 여러 경우 중 하나를 결정해야 할 때마다 그 순간마다 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종 해답에 도달한다.

• 각 선택 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 하여, 그것이 최적이라는 보장은 없다.

• 일반적으로 머릿속에 떠오르는 생각을 검증없이 바로 구현하면 그게 Greedy 접근이 된다.

✅ 탐욕 알고리즘의 동작 과정

1. 해 선택 : 현재 상태에서 부분 문제의 최적 해를 구한 뒤, 이를 부분해집합에 추가한다.

2. 실행 가능성 검사 : 새로운 부분해 집합이 실행 가능한지 확인한다. 곧, 문제의 제약 조건을 위반하지 않는지를 검사한다.

3. 해 검사 : 새로운 부분해 집합이 문제의 해가 되는지를 확인한다. 아직 전체 문제의 해가 완성되지 않았다면 1)의 해 선택부터 다시 시작한다.

ex> 거스름돈 문제

✅ Baby-gin을 완전검색이 아닌 방법으로 풀기

• 6개 숫자는 6자리 정수 값으로 입력

• counts 배열의 각 원소를 체크하여 run과 triplet 및 baby-gin 여부 판단