포털:고등학교/과학 계열 전문 교과/정보과학(2015 개정)/탐색 기반 알고리즘

1 탐색 기반 알고리즘

1. 탐색 기반 알고리즘이란?

탐색 기반 알고리즘은 컴퓨팅 시스템의 탐색 능력을 기반으로 문제 해결을 위한 해를 찾는 알고리즘을 뜻한다. 또한 이러한 알고리즘을 효율적으로 설계하기 위한 반법을 탐색 기반 알고리즘 설계 방법이라고 한다.

• 탐색의 예
- 용의자들 중에서 범인을 찾는 문제
- 상대방이 마음속에 생각하고 있는 100이하의 자연수 1개를 맞히는 문제
- 탐색한 해의 개수를 세는 계수(counting) 문제
- 탐색한 해 중 가장 품질이 좋은 해를 찾는 최적화(optimization) 문제

2. 탐색 기반 알고리즘 설계 방법

첫 번째, 해가 존재할 수 있는 집합(탐색 공간)을 설정한다. ex) 파일, 폴더
두 번째, 탐색 공간의 크기에 따라 탐색 시간이 달라지므로 탐색 공간의 크기를 줄인다.

탐색 알고리즘의 구분

탐색 공간의 구조	탐색 방법	탐색 알고리즘
선형 구조	선형 탐색	순차 탐색, 2진 탐색
비선형 구조	비선형 탐색	깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)

탐색 알고리즘은 구조화한 데이터의 형태에 따라 선형 탐색과 비선형 탐색으로 구분한다.
선형 탐색 - 리스트, 큐, 스택 (선형적으로 구조화)
비선형 탐색 - 트리, 그래프 (비선형적으로 구조화)

탐색 대상에 따른 알고리즘

탐색 대상	탐색 기반 알고리즘
탐색 공간의 전체	전체 탐색
탐색 공간의 일부	부분 탐색

2 전체 탐색

1. 전체 탐색 알고리즘 설계 방법

전체 탐색을 통해 문제를 해결하는 알고리즘을 브루트 포스 알고리즘(brute-force algorithm), 소모적 탐색 알고리즘(exhaustive search algorithm)이라고 부르기도 한다.
전체 탐색은 알고리즘을 설계하기 쉬운 반면, 탐색 시간이 오래 걸리는 경우 합리적인 시간 내에 해를 찾이 못할 수도 있다는 단점이 있다.
컴퓨터의 빠른 계산 능력을 이용하면 전체 탐색을 매우 유용하게 사용할 수 있지만, 컴퓨터의 계산 능력에 대한 의존도가 높은 방법이다.

2. 선형 전체 탐색

일반적인 선형 전체 탐색 알고리즘을 설계하기 위해서, 탐색 공간을 선형적으로 구조화하여 표현하고, 이를 순차 탐색 또는 2진 탐색을 통해 탐색 하면 된다.
예를 들어, 10 이하의 자연수 n의 모든 약수의 합을 구하는 문제가 있다.
(1. 탐색 공간의 구조화)

10의 약수가 될 수 있는 자연수를 집합으로 표현한다.

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

이처럼 문제의 해가 될 수 있는 자료를 선형적으로 표현할 수 있고, 배열이나 리스트와 같은 자료 구조를 바탕으로 저장할 수 있다.

(2. 구조화한 자료에서 원하는 해 탐색)

선형적인 자료 구조에서 활용할 수 있는 탐색 방법은 순차 탐색 알고리즘이다.
따라서 첫 번째 원소부터 마지막 원소까지 순차적으로 탐색하면서 10의 약수를 찾는다.
탐색 과정에서 10의 약수의 수는 남기고, 아닌 수는 배제하면 되는데, 이때 10의 약수란 10을 현재 원소로 나누어 떨어지는 수이다.

탐색 결과 : {1, 2, 5, 10}
문제 해결 : 1 + 2 + 5 + 10 = 18

마지막으로 이 알고리즘 과정을 C 언어를 이용해 소스 코드를 작성할 수 있다.

3. 비선형 전체 탐색

비선형 전체 탐색 알고리즘을 설계하기 위해서는 제일 먼저 문제 상황을 분석하여 탐색 공간을 비선형적으로 구조화하여야 한다.
이 공간 탐색을 위해 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)을 적용할 수 있는데, 일반적으로 구현이 간단한 깊이 우선 탐색을 많이 사용한다.

DFS : 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다.
BFS : 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다.

깊이 우선 탐색을 바탕으로 문제를 해결하는 방법을 퇴각 검색 또는 백트래킹(backtracking)이라고 한다.
백트랙은 더 이상 깊은 노드로 탐색할 수 없을 경우 부모 노드로 되돌아가는 과정이고, 백트래킹은 백트랙을 바탕으로 전체 탐색을 수행한다는 의미의 의태어이다.
백트래킹은 재귀 함수를 이용하여 간단하므로 유용하게 사용된다. 그러나 입력 크기(n)가 증가함에 따라 탐색 공간의 크기가 커지므로 시간 내에 해를 구할 수 없는 상황도 생기게 된다.
예를 들어, 자연수 n을 자연수의 합으로 나타낼 수 있는 모든 순열의 개수를 구하는 문제가 있다.
만약 3을 입력하면 (1 + 1 + 1), (1 + 2), (2 + 1), (3)으로 4가 출력된다.

(1. 탐색 공간의 구조화)

입력값 n이 3이라고 할 때, n을 자연수의 합으로 표현해야 하기 때문에 루트 노드인 3에서 뻗어 나가는 간선은 최대 3개이다.
합해서 3이 되는 순열을 구하는 문제이므로, 가장 왼쪽 간선 부터 마지막에 1, 2, 3을 더해서 3이 되는 것을 의미한다고 할 수 있다. 따라서 레벨 2읠 노드들의 값은 좌측부터 2, 1, 0이다.
레벨 2의 마지막 노드는 값이 0이고 루트 노드까지 연결하는 간선에 부여된 가중치가 3이다. 따라서 하나의 해라고 할 수 있다.

(2. 문제 해결)

가장 왼쪽의 노드 부터 살펴보면 차례대로 (1, 1, 1), (1, 2), (2, 1), (3)으로 4가 출력된다.

해결 과정 정리
가장 먼저 탐색 공간의 구조를 알아내기 위해 탐색 과정을 분석하였다. 루트 노드의 값인 자연수 n에 대하여 최대 n개의 자식 도느가 만들어진다. 이렇게 생성된 자식 도느에 대하여 또다시 최대 n개의 자식 노드가 만들어진다. 결룰 문제 해결을 위해 탐색해야 하는 공간이 비선형적 자료 구조인 n진 트리의 형태로 나타난다.

마지막으로 이 알고리즘 과정을 C 언어를 이용해 소스 코드를 작성할 수 있다.

3 탐색 공간의 배제

1. 탐색 공간의 배제

탐색 공간의 배제란, 효율적인 탐색 전략을 설계함으로써 탐색 공간의 크기를 줄이는 효과를 가져오는 알고리즘 설계 방법을 뜻한다.(부분탐색)
예를 들어 주어진 문제를 해결하기 위해 전체 탐색을 할 경우 O(n³)의 시간 복잡도를 가지는 알고리즘이 불가피하다고 할 때, 적절한 전략을 활용하여 O(n²), O(n) 등의 알고리즘으로 해를 찾도록 설계하는 것이다.

2. 탐욕 알고리즘 설계 방법

전체 탐색 공간 중 일부를 배제하여 효율적으로 문제를 해결하는 방법 중 하나는 탐욕 알고리즘을 설계하는 것이다. 탐욕 알고리즘(greedy algorithm)이란 현재 상태에서 다음 상태를 탐색할 때 모든 상태를 고려하지 않고, 최선의 상태만을 고려하여 선택하는 알고리즘 설계 방법으로 욕심쟁이 알고리즘 또는 그리디 알고리즘이라고 불린다.
이 방법은 탐색 공간 상에 여러 개의 해가 존재할 때 이들 중에 가장 적절한 해를 찾는 최적화 문제를 해결할 때 유용하게 적용할 수 있다.
탐욕 알고리즘 설계 방법을 적용하면 탐색 문제의 해를 간단하게 구할 수 있다는 장점이 있다. 그러나 이 탐색 구조에 있어서 논리적 비약이 있다.

예를 들어, 노드의 합이 최대가 되는 경로가 무엇인지 구하는 문제가 있다.
전체 탐색을 이용하여 다음 상태로 이동할 경우 값이 큰 노드를 선택했을 때, 이러한 선택이 전체 공간에서의 최대 합을 보장한다는 논리적 근거가 없기 때문에 이렇게 해서 얻어진 해가 최적해임을 보장하기 어렵다는 문제가 발생한다.
탐욕 알고리즘을 사용하여 해결해면 항상 최적해임을 보장하는 것은 아니지만 비교적 질 좋은 해를 쉽고 간단하게 구할 수 있다. 전체 탐색을 적용할 때의 시간 복잡도인 O(n²)이 O(n)으로 줄어든다.

3. 분기한정 알고리즘 설계 방법

탐색 공간을 배제하여 탐색 알고리즘의 효율을 높이기 위한 또 하나의 방법은 탐색 경험에 근거하여 특정 지역의 탐색 필요 여부를 판단하는 방법이다. 즉, 탐색 과정에서 더 이상 탐색할 필요가 없다고 판단되는 경로에 대해서 탐색을 진행하지 않고, 백트랙을 수행하는 방식이라 할 수 있다. 이것을 분기한정(branch and bound) 알고리즘 설계 방법이라고 한다.
탐색의 효율을 높이기 위해 이득을 취할 수 있는 행위를 한다는 점에서 탐욕 알고리즘과 유사해 보이지만 분기한정 알고리즘은 정확한 근거를 바탕으로 탐색을 제한하는 알고리즘이므로 항상 최적해를 보장한다.
일반적으로 DFS의 형태로 전체 탐색을 진행하다가 탐색이 불필요한 노드가 발견되면 백트랙을 수행한다.
예를 들어, 다음과 같은 탐색을 해야 하는 비선형 탐색 공간이 있다.

이때 노드 내부의 번호는 탐색 순서를 뜻한다. 만약 2번에서 3번으로 진행하려고 할 때, 3번 이하의 모든 노드를 더 이상 탐색할 필요가 없다고 판단할 방법이 있다면 바로 9번으로 진행할 수 있다.
전체 탐색을 했다면 탐색 횟수가 11회가 되었을 상황에서 분기한정 알고리즘을 설계하여 6회만에 동일한 경과를 얻는 알고리즘을 구현할 수 있게 되었다.
따라서 보다 효율적인 탐색을 수행할 수 있도록 하는 부분 탐색 알고리즘 설계 기법이라고 할 수 있다.