[WEEK02] 완전탐색

1) Brute Force : for 문이나 if 문을 활용하여 모든 경우의 수 알아봄

 

2) 비트마스크 (Bitmask) : 각 원소가 A인지 B인지 두가지 상태만을 가질 때 0, 1로 구분하여 배열을 저장

 

3) 재귀함수

 

4) 순열

 

5) BFS, DFS

 

6) 백트래킹

 : 현재 상태에서 가능한 모든 선택지를 다 따라 들어가며 탐색하는 알고리즘

 : 원하는 값과 불일치하는 부분이 생기면 탐색을 진행하지 않고 전단계로 돌아감

  ex) 오목에서 앞으로 진행될 수를 생각해보고 가장 적절한 자리에 두는 것

대표문제 : N과 M

 

cf) DFS(Depth First Search)와 백트래킹의 차이점

: 백트래킹은 불필요한 탐색을 하지 않음

: DFS는 모든 경우의 수를 탐색함