3주차-완전탐색

완전탐색은 brute force 라고 불리는 탐색 방법.

 

어떤 벽을 4개를 세우고 한 점으로부터의 최단 거리를 구하는 문제라면,

완전탐색은 모든 경우의 수를 다 계산해서 따지는 알고리즘이 완전탐색

 

- 시간복잡도가 1억 미만이면 시도해볼만하다.

- 반복문으로 해결할 수 있다면 반복문으로 하는게 좋다.

- nC1, nC2 와 같이 조합을 이용하여 경우의 수를 다 계산해야 하는 경우 재귀함수를 사용하는 것이 좋다.

 

 

 

 

백트래킹은 완전탐색에서 불필요한 부분을 제외한 탐색 방법

 

 - 이 경우의 수는 탐색하지 않아도 될 것 같은데? 라고 가능성이 없는 경우의 수를 제외시키는 것