Part1.기초에서 학습할 내용
→ 알고리즘의 설계와 분석을 학습
→ 알고리즘을 분석할 때 필요한 기본 개념 학습
- 1.0 개요
- 1.1 알고리즘
- 1.2 기술로서의 알고리즘
1.0 개요
알고리즘이 고속 하드웨어, 그래픽 기반의 사용자 인터페이스, 객체 지향 시스템, 네트워크 등과 같이 중요한 컴퓨터 기술 중 하나임을 확인한다.
알고리즘의 후보해는 많지만 대부분이 문제의 해가 아니다. 문제의 해 혹은 "최상의" 해를 찾는 일은 대단히 도전적인 일이다.
1.1 알고리즘
알고리즘(Algorithm)은 어떤 입력을 어떤 출력으로 변환하는 잘 정의된 일련의 계산 절차를 말한다. 또한 알고리즘을 잘 정의된 계산 문제를 풀기 위한 도구로도 볼 수 있다.
알고리즘이 모든 입력 사례에 대해 항상 올바른 출력을 내고 종료할 경우 이를 타당하다(correct)고 하며, 그 타당한 알고리즘이 주어진 계산 문제를 푼다(solve)고 말한다. 타당하지 않은 알고리즘은 모든 또는 일부 입력 사례에서 종료하지 않거나 잘못된 답을 도출하며 종료할 것이다. 타당하지 않은 알고리즘일지라도 오류의 비율을 조절할 수 있다면 유용할 때가 있다.(소수 찾기 알고리즘)
어떤 문제를 알고리즘으로 푸는가
convex hull 찾기, 최단 경로 찾기, FFT(Fast Fourier Transform), 위상 정렬(Topological sorting) 등을 푼다.
자료구조
자료구조는 자료를 편리하게 접근하고 변경하기 위해 자료를 저장하거나 조작하는 방법을 말한다. 완벽한 자료구조는 없으니 각 자료구조의 장점과 한계를 잘 아는 것이 중요하다.
어려운 문제들
알고리즘의 효율성에 관한 일반적인 척도는 속도, 즉 알고리즘이 결과를 내는데 걸리는 시간이다. 최적해가 알려지지 않은 문제도 많은데, 그 중 하나가 NP-완비 문제이다.
병렬성
프로세서의 클럭 속도는 오랫동안 계속 증가했지만 이제는 물리적 한계로 인해 클럭 속도를 계속 증가시키기 어려워졌다. 바로 클럭 속도 증가에 따른 전력 밀도 증가와 발열 때문이다. 이러한 한계를 극복하고자 클럭 속도를 증가시키는 것이 아닌 여러 계산을 동시에 처리하도록 멀티 코어 컴퓨터가 등장하게 된다. 이는 일종의 병렬 컴퓨터(parallel computer)이며, 멀티 코어 컴퓨터로부터 최고의 성능을 얻으려면 알고리즘을 설계할 때 병렬성을 염두에 두어야 한다.
1.2 기술로서의 알고리즘
컴퓨터가 무한히 빠르고 메모리 비용이 들지 않아도 알고리즘 학습은 필요하다. 어떤 기법이든 가장 쉽게 구현할 수 있는 것을 가장 자주 사용할 것이다. 컴퓨터는 무한히 빠를 수 없으며 메모리 비용 또한 저렴해지더라도 전혀 안들 수는 없다. 그러므로 자원을 효율적으로 사용해야 하며, 시간과 공간 측면에서 효율적인 알고리즘이 필요하다.
효율성
동일한 문제를 해결하기 위한 알고리즘이 효율성 면에서 극적으로 다를 수 있다. 이런 차이는 HW나 SW로 인한 차이보다 훨씬 더 심각할 수 있다.
컴퓨터 A가 컴퓨터 B보다 1000배 빠르게 명령어를 수행한다고 가정하자. 컴퓨터 A에는 삽입 정렬을 수행하고 컴퓨터 B에는 병합 정렬을 수행한다. 입력 값은 같으며, 출력 결과도 동일하게 나와야 한다. 삽입 정렬의 소요 시간은 $c_1n^2$이며, 병합 정렬의 소요 시간은 $c_2n\log_2n$이다. $n$은 정렬할 수열의 길이이며, 일반적으로 $c_1<c_2$의 관계를 가진다. $n=1000000$인 경우 각 컴퓨터가 명령을 수행하는데 걸리는 시간은 다음과 같다.
$$ time_A = {c_1 1000000 \times 1000000 \over 1000} = 1,000,000,000 $$
$$ time_B = c_2 1000000 \times \log_{2}1000000 = 100,000,000 $$
결과적으로 빠른 컴퓨터를 사용하면서도 적절한 알고리즘을 사용하지 못하여 최종 소요 시간이 늘어나는 것을 볼 수가 있다.
알고리즘과 다른 기술들
앞서 보인 예는 HW처럼 알고리즘도 하나의 기술임을 보여준다. 전체 시스템의 성능은 빠른 HW뿐만 아니라 얼마나 효율적인 알고리즘을 선택하느냐에 따라서도 결정된다.
동시대에 다음과 같은 발전된 다른 기술들만큼 컴퓨터 분야에서 알고리즘은 매우 중요하다.
발전된 컴퓨터 구조와 제조 기술
사용하기 쉽고 직관적인 GUI
객체 지향 시스템
통합적인 웹 기술
빠른 유무선 네트워킹
"알고리즘에 대한 지식과 기술을 얼마나 알차게 학습했느냐"가 숙련된 프로그래머와 초보자를 구분하는 기준이 될 수 있다. 알고리즘에 대한 별다른 지식 없이도 최신 컴퓨터 기술을 통해 어떤 일을 할 수 있을지도 모른다. 하지만 알고리즘에 대한 훌륭한 배경 지식을 쌓으면 훨씬 더 많은 일을 할 수 있을 것이다.