완전탐색

Brute force

exhaustive key search
= 노가다

모든 경우의 수를 탐색하는 알고리즘

모든 경우의 수?

• 순열 or 조합 + 로직
  (보통 1억 미만까지 가능하다) 컴퓨터를 믿고 넘기자!

보통 1억 미만이면 완전탐색!!
1억 이상이면 다른 알고리즘을 생각해보자.

반복문을 활용한 완전탐색

for or while

단순히 선형적으로 숫자 찾기

재귀함수를 활용한 완전탐색

반복문으로 되면 무조건 반복문으로.

그 외 너무 복잡하거나 어떠한 행위는 반복하는데 매개변수만 수정해서 넘기면 될 거 같다? 그러면 재귀함수로.

• 조합 or 순열 + (DFS, BFS 등 알고리즘)
• 경우의 수 마다 생각해야 하는 로직도 나옴.

백트래킹

back tracking
완전탐색 & 가지치기

최대한 불필요한 탐색을 피함.

완전탐색에서 원상복구를 잘해라?

원복의 필요성 -> 상태값이 그 다음 경우의 수에 반영이 안 될 때

예제 문제 15686