[알고리즘 전략] 완전탐색

** [한권으로 합격하는 취업 코딩테스트] 책을 참고해 작성했습니다.

** 주의점, 기억해야할 것을 위주로 작성합니다. 

 

브루트 포스 Brute-Force

 

- 무차별 대입이라는 의미. 

- 완전탐색 전략을 충실히 사용해서 확실하게 답을 구하는 알고리즘

- 어떤 문제를 풀 때 먼저 '무식하게 모든 경우를 다 살펴봐도 될까?' 생각해보기 (제한시간 오버되면 다른 방법 생각하기) 

 

** 문제 푸는 방법   1. 반복문   2. 재귀   3. 순열   4. 조합

=> 삼성 코테에서 순열 조합 많이 쓰인다고 함.

 

순열 

- n개의 수 중에서 r개를 뽑아 줄을 세우는 총 방법의 수: nPr = n! / (n-r)! 

- 순서 고려 O 

- permutations(배열이름, 몇개를 고를지)

from itertools import permutations 

arr = [0,1,2,3] 
for i in permutations(arr, 4):
	print(i)

 

조합

- n개의 수 중에서 r개를 뽑기만 하는 총 방법의 수: nCr = n! / {(n-r)! * r!}

- 순서 고려 X 

- combinations(배열이름, 몇개를 고를지) 

from itertools import combinations 

arr = [0,1,2,3] 
for i in combinations(arr, 2):
	print(i)

 

 

** 대표문제 

- 백설공주와 일곱 난쟁이

- 유레카 이론 (아이디어 필요한) 

- 사탕게임 (다시 풀어보기)