1.2 알고리즘 소개 [디딤돌 자료구조와 알고리즘 with C++]

1.2 알고리즘 소개

알고리즘은 특정 문제를 해결하기 위한 논리를 말해요. 해결해야 할 어떠한 문제가 주어지면 문제에 주어지는 선행 조건과 영향 인자와 후행 조건을 알아겠죠.

 

선행 조건은 알고리즘을 수행 하기 전의 상태를 말합니다. 그리고 영향 인자는 문제를 해결하는데 영향을 주는 인자예요. 후행 조건은 문제를 해결하고 난 후의 상태를 말해요. 결국 알고리즘은 선행 조건인 상태에서 주어진 영향 인자를 가지고 후행 조건에 맞게 문제를 해결하는 것이죠.

 

예를 들어 특정 범위 내의 정수의 합계를 구하는 문제를 살펴봅시다.

 

이 때는 선행 조건은 특별한 것이 없네요. 문제를 해결하는 데 영향을 주는 인자는 범위의 시작과 끝이겠죠. 따라서 알고리즘을 함수로 구현한다면 입력 인자로 범위의 시작 정수와 끝 정수가 필요하겠죠. 알고리즘 수행 결과는 범위 내의 정수의 합계예요.

 

선거에서 이기기 위한 방법을 찾는 것은 매우 어려운 알고리즘이예요. 선거를 이기기 위해 후보자가 누구이고 유권자는 누구이며 선거에 영향을 주는 시대 흐름이나 경제 상황 등을 고려해야겠죠. 이와 같은 문제는 해답을 찾기 위해 필요한 인자가 무엇인지 파악하는데 어려움이 있어요. 이러한 문제를 해결하는 것은 현실적으로 불가능에 가깝다고 할 수 있겠죠.

 

이처럼 결과에 영향을 주는 입력 인자가 무엇인지 판별하지 못하면 정확한 알고리즘을 구하기 어려워요. 하지만 정답을 구하지 못했다고 알고리즘의 가치가 없는 것은 아니예요. 알고리즘은 정확한 정답을 구할 수 없을 때 의미있는 근사해를 구하는 것도 의미가 있거든요. 우리가 흔히 인공지능 알고리즘이라고 부르는 대부분 정답을 구하는 것이 아니라 의미있는 근사해를 구하는 것이 많아요.

 

문제에 따라 수학적으로 정답은 구할 수 있지만 컴퓨터에서 정답을 구하려면 시간적 제약으로 풀 수 없는 문제도 있어요. 가령 100개의 돌을 옮기는 하노이 탑 문제는 2의 100승에 가까운 횟수의 이동이 필요해요.

 

이러한 문제는 현재의 컴퓨터 기술 수준에서는 1조년이라는 시간으로도 해결할 수 없어요. 이처럼 시간적 제약이 있는 문제는 정답을 구하는 것보다 의미있는 근사해를 구하는 것이 실용성이 높다고 할 수 있어요.

 

 

여기에서는 여러 종류의 알고리즘을 해결하는 방법에 따라 분류하여 기술할게요.

 

이 책에서는 반복 알고리즘, 재귀 알고리즘, 분할 정복 알고리즘, 동적 프로그래밍, 탐욕 알고리즘 등을 다룰 거예요. 진화 알고리즘, 신경망 회로나 세포 이론, 개미집 이론, 새 떼 이론 등의 의사 결정 알고리즘처럼 최적해를 구하기 힘든 문제를 근사치를 구하는 알고리즘은 다루지 않아요.

 

이 책에서는 다양한 정렬 알고리즘과 검색 알고리즘을 문제 해결 방법에 따라 분류하여 다룰 거예요. 알고리즘의 의사 코드로 간략히 소개한 후에 직접 구현하는 실습을 진행합니다. 특히 알고리즘 수행 시간을 측정하는 코드와 함께 점근식으로 수행 성능을 평가하는 방법도 알아볼게요.

 

이 책에서 다루는 정렬 알고리즘은 거품 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬, 기수 정렬, 힙 정렬, 쉘 정렬 등이 있어요.

 

그리고 검색 알고리즘에는 순차 검색, 이진 검색을 다룰 거예요. 그리고 그래프 상에서 다양한 경로 찾기 알고리즘을 다룰 거예요.

 

이 외에도 큐를 이용한 스케쥴러 시뮬레이션, 스택을 이용해서 재귀 알고리즘을 반복 알고리즘으로 변환하는 방법을 다룰 거예요.

 

동적 프로그래밍에서는 피보나치 수열처럼 단순한 문제부터 순열 문제 및 깊이 우선 탐색처럼 스택을 이용하는 알고리즘도 다루고 있어요.

 

탐욕 알고리즘에서는 거스름 돈 문제처럼 단순한 문제로 기본적인 개념을 소개한 후에 최소 신장 트리를 만들기 위한 프림 알고리즘, 크루스칼 알고리즘도 다룰 거예요.

 

이 외에도 프로그램에서 자주 사용하는 기본적인 다양한 알고리즘을 다룰게요.