알고리즘 정리 - "완전탐색"

 

완전탐색이란 

모든 경우의 수를 다 찾아보는 해결 방법이다.

 

가령 자물쇠의 비밀번호를 찾는 문제가 나온다고 할 때,

가장 쉬운 방법은 0000 부터 9999까지 한번씩 다 해보면 그 중간에 정답을 찾을 수 있는 방법입니다.

 

구현하기 쉽지만 코딩테스트에서는 오랜 시간이 걸리게 되어 Timeout을 일으킬 수도 있는 방법론입니다.ㅜㅜ

그래도 중간중간 로직을 손봐주면 확실히 무작정 코드를 짜는 것보다는 정확도와 성능을 높일 수 있으니,

한번 공부해보시면 좋을 것 같습니다.

 

완전탐색의 종류

 

1. Brute Force : for 문과 if 문을 사용하여 전체를 다 살펴보기

관련 예제: 프로그래머스 K번째 수 문제 https://datacodingschool.tistory.com/86

프로그래머스 - 'K번째수' 문제풀이

2. 비트마스크 : 용어 그대로 비트에 관한 것이다. 

비트(bit)는 0과1로 이루어진 컴퓨터에서 사용되는 최소 단위이다. (0,1 혹은 true,false 혹은 on,off)

관련 예제: 백준 2098번, 외판원 순회 문제 https://www.acmicpc.net/problem/2098

2098번: 외판원 순회

이진수 -> 십진수

십진수 - > 이진수 로 변환시키면서 문제를 풀 수 있다.

 

또한 이진수로 비트 변환 시킨 상태에서 다양한 비트 연산을 할 수 있다.

& (AND) : 대응하는 두 비트가 모두 1일 때 1반환

1010 & 1111 = 1010

| (OR) : 대응하는 두 비트 중 하나라도 1일 때 1반환

1010 | 1101 = 1111

^ (XOR) : 대응하는 두 비트가 서로 다를 때 1 반환

1010 ^ 1111 = 0101

~ (NOT) : 비트를 모두 반대 방향으로 뒤집는 변환

~1010 = 0101

>>, << (쉬프트 연산) : 왼쪽이나 오른쪽으로 비트를 옮긴다.

0001101 << 3 = 1101000
0001101 >> 2 = 0000011

 

참고한 블로그를 살펴보면,

왼쪽 시프트는 A * 2^B 를 의미하고, 오른쪽 시프트는 A / 2^B 를 의미한다.

0001 -> 0010 -> 0100 -> 1000 => 1, 2, 4, 8 .....

1000 -> 0100 -> 0010 -> 0001 => 8, 4, 2, 1 ..... 

(A + B) / 2 를 (A + B) >> 1 로 사용할 수도 있듯이 많은 곳에서 일반적인 사칙연산을 더 효율적으로 할 수 있다.

출처: https://mygumi.tistory.com/361 [마이구미의 HelloWorld]

 

 

3. 순열

순열(Permutation)은, 중복없이 원소들을 하나씩 뽑은 모든 경우의 수를 말한다.

예를 들어 {a,b,c,d}일 때, 2개를 뽑아서 일렬로 세우는 방법은 12가지

ab ac ad  ba bc bd  ca cb cd  da db dc 

경우의 수는 4*3 = 12이다.

 

4. 백트래킹

모든 경우의 수를 갈때, 비효율적인 루트는 차단하고, 가능성있는 곳을 탐색하는 알고리즘

관련 예제: 백준 9663 N-queen 문제, https://www.acmicpc.net/problem/9663

9663번: N-Queen

 

5. BFS, DFS

넓이우선탐색(BFS) : 현재 정점에 연결된 가까운 점들부터 탐색

깊이우선탐색(DFS) : 현재 정점에서 최대한 갈 수 있는 점까지 들어가면서 탐색

관련 예제: 백준 2667 단지번호붙이기 문제, https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기