[Ch.01 - 알고리즘이란] 알고리즘은 문제 해결 과정을 묘사하는 것

1. 알고리즘의 정의

---

알고리즘이란 어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것이다. 알고리즘을 설계하기 위해서는 우선 해야 할 작업을 명확하게 명시해야 한다. 다시 말하면, 설계하고자 하는 알고리즘이 "무엇을" 하는지 입력과 출력으로 명시해야 한다.

 

예를 들어, 학생 100명의 시험 점수 중 최고 점수를 알고자 한다면 다음과 같이 표현할 수 있다.

입력	출력
학생 100명의 시험 점수	입력된 100개의 점수 중 최댓값

 

이런 입출력을 요구하는 알고리즘은 대략 다음과 같을 것이다.

maxScore(x[], n)
{
    x[1...n]의 값을 차례대로 보면서 최댓값을 계산한다
    return 위에서 찾은 값
}

 

이런 쉬운 문제도 있지만, 알고리즘으로 해결하고자 하는 문제들은 난이도가 다양하다. 현실적인 시간 내에 최적의 해를 보장하지 못하는 경우도 존재한다. 예로 다음과 같다.

입력	출력	문제 난이도
서울시 지하철 노선도, 출발역, 도착역	출발역에서 도착역까지 가는 최단 경로	낮음
n개의 행렬과 각 행렬의 차원	이 행렬들을 모두 곱하기 위해 가장 빨리 끝나는 곱셈 순서	다소 높음
어떤 영업사원이 방문해야 할 고객 n명의 위치	모든 고객들을 방문하고 돌아오는 가장 짧은 경로	시간 내에 최적의 해 보장 불가

 

 

2. 명확하게

---

알고리즘은 이전과 같은 다양한 문제의 해결 과정을 모호하지 않게 묘사해야 한다. 앞 절의 maxScore()로 다시 돌아가보자. 이 함수는 매우 추상적으로 표현되어 있지만, 실제 알고리즘을 만들 때는 점진적으로 구체화하는 과정을 거쳐 모호함이 없는 수준에서 마무리한다. 함수나 서브루틴도 구체화 과정에서 도입되는 것이다.

 

알고리즘은 명확하게 설계해야한다. 명확하다는 것은 모호하지 않고 이해하기 쉽다는 것이다. 명확한 것과 자세한 것은 다르다. 지나친 세부 사항을 기호로 구구절절 기술하는 것은 오히려 알고리즘의 명확성을 떨어뜨린다. 명확성은 독자의 수준을 고려해야한다. 프로그래밍을 할 줄 아는 독자라면 "배열 x[1...n]의 최대값"이라 표현하여도 충분히 알아들을 수 있고 독자가 나머지 세부 사항을 쉽게 구현할 수 있지만, 프로그래밍을 모르는 독자하면 더욱 자세하게 기술해야 할 것이다. 그러니, "모호하지 않다"는 것은 독자 수준에 따라 상대적이다.

 

 

3. 효율적으로

---

알고리즘은 가능한 효율적이어야 한다. 알고리즘은 궁극적으로 컴퓨터로 구현되기 때문에 컴퓨터의 빠른 계산 능력을 감안하면 비효율적인 알고리즘도 적은 입력에 대해서는 충분히 빠르게 해결한다. 하지만, 충분히 많은 양의 입력을 받는다면 이야기가 달라진다. 충분히 큰 입력에 대해서는 알고리즘의 효율성에 따라 소요 시간이 크게 차이가 난다. 같은 문제를 해결하는데 알고리즘을 어떻게 설계했는지에 따라 100년이 걸릴 수도, 1분이 걸릴 수도 있다. 입력이 충분히 큰 경우에 대한 분석을 점근적 분석^{Asymptopic Analysis}이라고 하는데, 고등학교 수학에서 배우는 극한과 비슷하다고 보면 된다.