완전 탐색(Exhaustive Search)

완전 탐색 : 가능한 모든 경우를 구해서 문제를 해결하는 방법

단점 : 실행시간이 너무 길다

Brute_force 방식

1. N 반복문

2. Queue 이용

3. 순열을 이용

4. 재귀 이용 - 장점 : 코드가 간결하고 구현이 직관적

어려운 문제를 쉽게 풀 수 있다

단점 : 쉬운 문제를 어렵게 풀어야 한다

ex) Top-down 방식

탐색 공간의 배제

1. 수학적 배제 - 이분탐색, Greedy 방식

2. 경험적 배제 - 특정 조건을 두고 계속 탐색할지 결정함

탐색을 진행하는 중에 조건을 설정하고 상황에 따라서,경험한 정보를 이용해서 조건이 갱신되기 때문에 경험적 배제라고 함

Branch & Bound(가지치기)라고도 불린다

해결 전략에 따른 구현법

1. 백트래킹 - 답이 나올때까지 계속 검색하다가 답이 아니며 그 이전 단계로 돌아가서 다시 검색을 시작하는 방법

Pruning(가지치기)라는 방법으로 경우의 수를 줄임

ex) DFS, BFS

2. 분할 정복 - 주어진 문제를 풀 수 있을때까지 작은 문제로 계속 나누어 푸는 방법

DP와의 차이점은 중복 호출을 하지 않는다(DP는 중복호출이 일어나 메모이제이션을 필요로 하기 때문에)

Divide(분할), Merge(병합), Base case(기저 케이스)

ex) 루프, 재귀

병합 정렬 : 구현하기 쉬운 대표적인 정렬

최악의 경우에도 O(NlogN) 복잡도

N만큼의 버퍼공간이 추가로 필요(병합 용도)

분할 정복으로 구현

어떻게 함수를 만들어야 할지(작은 문제를 어떻게 호출해야 할지, 부분 문제의 정답을 합쳐야 하는 경우에는 합치는

것을 어떻게 해야 할지)

3. 이진 탐색 - 정렬된 구조에서 목적값의 위치를 찾는 방법

탐색 범위를 반으로 줄여가면서 찾음

분할 정복의 한 갈래

4. DFS - 깊이 우선 탐색

일단 밑으로 내려가서 탐색

ex) 지도, 미로, 체스판, 장기

ex) 특정 좌표까지 경우의 수라든지 도달 여부 등을 확인할 때 사용 가능

최단 거리 문제에서는 부적절함

IT