완전탐색(Brute-Force Search)

완전탐색

가능한 경우의 수를 모두 나열하여 목표 값을 찾는 방법으로, 경우의 수가 적을 때 유용

시간이 오래 걸림

종류 : 단순 부르트포스, 비트마스크, 백트래킹, 재귀, 순열/조합/부분집합, BFS/DFS

 

 

단순 부르트포스(Brute-Force)

for문과 if문 등으로 모든 case를 만드는 방법

 

 

비트마스크(Bitmask)

시간복잡도 : O(1)

요소가 n개인 집합의 모든 부분집합을 구할 때, 각 요소의 포함 여부를 0, 1로 구분해 배열에 저장할 수 있음

비트(2진수) 연산을 통해 부분집합을 표현하는 방법으로, 요소가 두 가지 상태만을 가질 때 사용 가능

비트 연산
시간복잡도 : O(1)연산자 : AND(&), OR(|), NOT(~), XOR(^), Shift(<<, >>)비트 연산자는 우선순위가 낮으므로 괄호로 구분해줘야 함

장점

• 타 알고리즘에 비해 빠른 연산속도 → 시간복잡도 O(1)
• 적은 메모리 사용량 → 하나의 정수로 많은 경우의 수를 표현 가능하기 때문
• 간결한 코드 → 집합 연산들을 비트 연산자로 작성가능하기 때문

단점 : 요소의 수가 클 때는 사용하기 어려움

 

 

 

백트래킹

분할정복, 재귀함수를 이용하여 가지치기 하는 방법

가지치기(Pruning) : 목표값을 찾아가다가 비유망 노드는 제외하고 유망 노드를 탐색

* 비유망 노드(non-promising node) : 목표 값이 없는 노드

* 유망 노드(promising node) : 목표 값이 있는 노드

장점 : 탐색 시간을 단축시켜줌

 

 

재귀(Recursive Funtion)

특정 기능을 수행하는 함수를 생성하고, 해당 함수 내에서 자기 자신을 호출하여 반복 작업을 수행

 

 

순열, 조합, 부분집합

코드 짤 때 참고 https://www.oct14jh.com/algorithms/concept/brute-force

순열(Permutation)

서로 다른 요소 n개 중 r개를 선택하는 것으로, 순서에 의미 있음(ABCD와 DBAC는 다른 것)

해당 순서의 요소를 사용할지 여부는 boolean배열이나 비트마스킹을 통해 체크 가능

순열의 개수 : nPr개( nPr = n! / (n-r)! )

 

조합(Combination)

서로 다른 요소 n개 중 r개를 선택하는 것으로, 순서에 의미 없음(ABCD와 DBAC가 같은 것)

조합의 개수 : nCr개(nCr = nPr / r!)

 

부분집합(SubSet)

요소당 2가지의 경우의 수를 가짐(해당 요소를 포함하거나, 포함하지 않거나)

모든 집합의 개수(자기자신과 공집합 포함) : 2^n개

 

 

 

너비 우선 탐색(Breadth-First Search BFS), 깊이 우선 탐색(Depth-First Search DFS)

https://namu.wiki/w/BFS

https://velog.io/@himinhee/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-DFS%EA%B9%8A%EC%9D%B4-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89-BFS%EB%84%88%EB%B9%84-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89

시간 복잡도

N : 노드, E : 간선

• 인접 리스트로 표현된 그래프 : O(N+E)
• 인접 행렬로 표현된 그래프 : O(N^2)

 

DFS

루트 노드(혹은 다른 임의의 노드)에서 시작해, 다음 분기(branch)로 넘어가기 전 해당 분기를 완벽히 탐색하는 방법

해당 분기의 마지막 노드에 도착한 경우, 가장 가까운 갈림길로 돌아가 다른 방향으로 다시 탐색을 시작

주로 재귀를 사용해 구현하며, 스택을 사용하기도 함

방문한 노드에 대한 구분 필요 → 구분하지 않을 경우 무한 재귀에 빠질 수 있음

장점 

• 찾는 요소의 깊이가 깊을수록 빨리 구할 수 있음
• 현재 경로상의 노드들만 기억하면 되기 때문에 메모리 사용량이 BFS에 비해 적은 편 
• BFS보다 간단함

단점

• 목표 값이 없는 곳도 모두 방문하여 비효율적인 방법이 될 수도 있음 → 백트래킹 알고리즘과 함께 사용하여 가지치기 진행
• 트리의 깊이가 너무 깊거나 끝이 없는 경우는 사용 지양(스택오버플로우 발생 가능)
• 목표 값이 여러개일 때, 목표 값에 도달한 경로가 최단 경로라는 보장이 없음
• BFS보다 느림

 

BFS

가중치가 없는 (혹은 동일한) 그래프의 최단경로를 찾을 때 주로 사용

* 가중치가 있는 그래프의 최단경로는 Dijkstra를 통해 탐색

하나의 요소를 방문하고, 해당 요소와 같은 깊이의 요소들을 탐색 후 자식노드로 이동

즉, 깊이 별로 순환탐색

주로 큐(Queue)를 사용해 구현

장점

• 모든 간선의 길이가 동일할 때, 시작점에서 목표 값까지의 최단 경로를 찾을 수 있음 → 한 갈림길에서 연결되는 모든 길을 탐색하기 때문(가중치가 없는 그래프 한정)
• DFS보다 빠름

단점

• 자식노드의 자식노드 탐색 시 메모리 소모가 크기 때문에, 트리의 깊이마다 노드들이 많을 때는 사용 지양
• DFS보다 복잡함

 

 

DFS, BFS 각각 적합한 문제 유형

DFS : 경로 특징을 저장해야 하는 문제, 검색 대상의 그래프가 매우 큰 문제

BFS : 최단 거리 혹은 경로를 구하는 문제

 

 

 

 

 

 

---

참고

https://intrepidgeeks.com/tutorial/algorithm-complete-navigation-technology

[알고리즘] 완전탐색 기법

그래프_최단경로(BFS, Dijkstra) :: muntari Log (tistory.com)

그래프_최단경로(BFS, Dijkstra)

 

https://velog.io/@himinhee/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-DFS%EA%B9%8A%EC%9D%B4-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89-BFS%EB%84%88%EB%B9%84-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89

[알고리즘] DFS(깊이 우선 탐색), BFS(너비 우선 탐색)