[알고리즘] 4. 탐욕 알고리즘

1. 탐욕 알고리즘 Greedy Algorithm

• 여러 경우 중 하나를 결정해야 할 때, 그 순간 최적이라고 여겨지는 것을 선택한다.
• 최적해를 찾는 문제에 특화되어있다.
• 최적의 선택들 → 결과마저 최적이라는 보장 x
• 머릿속에 떠오르는 생각을 검증 없이 구현하면 탐욕 알고리즘

*탐욕 알고리즘의 과정

1. 해 선택: 현재 상태에서 부분 문제의 최적해 선택, 해 집합(Solution Set)에 추가
2. 실행 가능성 검사: 새로운 해 집합이 실행 가능한지 확인. 문제의 제약조건 위반 여부를 확인
3. 해 검사: 새로운 부분 해 집찹이 문제의 해가 되는지 확인.

*탐욕 알고리즘을 활용한 Baby-gin 접근

i = 0
tri = run = 0

while i < 10:

	if c[i] >= 3 : #triplet 조사 후 데이터 삭제
		c[i] -= 3
		tri += 1
		continue;
		
	if c[i] >=1 and c[i+1]>=1 and c[i+2]>=1 : #run
		c[i] -= 1
		c[i+1] -= 1
		c[i+2] -= 1
		run += 1
		continue
	i += 1

if run + tri == 2 : print("Baby Gin")
else : print("Lose")