1. 컴퓨팅에서 알고리듬의 역할
1.1. 알고리듬
알고리듬 algorithm은 어떠한 값 혹은 값의 집합을 입력 input으로 받아 어떤 값 혹은 값의 집합을 출력 output으로 내놓는 잘 정의된 계산 과정. 즉, 알고리듬이란 입력을 출력으로 만드는 순차적 계산 과정.
알고리듬은 잘 정의된 계산 문제 computational problem을 해결하는 도구로 볼 수도 있음.
정렬 문제 sorting problem의 정의를 예로 들자:
입력: n 개의 순차적 숫자 <a1, a2, …, an>.
출력: 입력에 대해 a'1 ≤ a'2 ≤ … ≤ a'n을 만족하는 (재배열한) 순열 <a'1, a'2, …, a'n>.
이런 입력의 구체적인 예시를 정렬 문제의 한 사례 instance라 부름. 일반적으로 한 문제의 사례 instance of a problem란 문제에 해답을 계산하기 위해 필요한 (문제가 제시한 제약을 만족하는) 입력으로 구성됨.
주어진 상황에서 어떤 알고리듬이 젤 나은지는 정렬로 예를 들면 정렬할 원소의 개수, 이미 정렬되어있을 수도 있는 범위, 원소 값에 있을 수도 있는 제한 사항, 컴퓨터의 구조, 사용하는 기억 장치 등에 따라 다름.
모든 입력 사례에 대해 올바른 출력을 언제나 내는 알고리듬은 올바른 correct 알고리듬. 올바른 알고리듬은 주어진 계산 문제를 해결 solve한다고 함. 물론 오류율이 제어 가능하다면 올바르지 않은 알고리듬도 사용할 수도 있음.
알고리듬으로 해결할 수 있는 문제들의 종류
실제 예시:
- 인간 유전체 사업
- 인터넷
- 전자상거래
- 제조업 및 상업 회사
특정 문제:
- 서로 인접한 교차점 간의 거리가 주어진 로드맵이 있을 때 한 교차점에서 다른 교차점까지의 최단 경로를 찾을 때. 그래프를 사용하여 해결.
- 두 개의 정렬된 순차적 기호 X = <x1, x2, …, xm> , Y = <y1, y2, …, yn>가 주어졌을 때, 둘 사이의 최장공부분열 구하기. 최장공부분열의 길이를 통해 X와 Y가 얼마나 유사한지 파악 가능. X와 Y는 각각 2m과 2n 개의 부분열이 존재함.
- 다른 부품을 자신의 부품으로 가질 수도 있는 부품의 집합이 있는 기계적 설계의 경우 자기 자신을 사용하는 부품 이전에 자신이 우선 오도록 순서를 뽑는 방법. n 개의 부품이 있다면 n! 개의 순서가 가능함.
- 평면에 n 개의 점이 있을 때 이 점들의 볼록 껍질 구하기. 볼록 껍질이란 이 점들을 포함하는 최소 볼록 다각형. n 개의 못이 박혀있고 이걸 하나의 고무줄이 전부 지난다고 생각하면 됨. 2n 개의 경우의 수가 존재.
이러한 알고리듬 문제들은 공통적으로 두 가지 특성을 가짐:
- 여러 해법 후보가 존재함. 대부분의 경우 당장 문제를 해결해주지는 못 함. 이 중 가장 "잘" 처리하는 걸 찾는 게 문제임.
- 실무적 용도가 있어야함
알고리듬이 해결하는 모든 문제가 손쉽게 해법 후보를 구할 수 있는 건 아님. 푸리에 변환 사용하는 경우 등이 있음.
자료 구조
자료 구조 data structure란 자료를 저장하고 구조화하여 접근과 수정을 용이하게 만드는 방법.
기법
이 책은 마치 "레시피 책"임. 현존하지 않은 알고리듬이 필요할 땐 직접 알고리듬 개발할 수 있게 설계하고 분석할 수 있게 해줌.
난제
이 책에서는 대부분의 경우 효율적인 알고리듬을 다룸. 여기서 효율적이라는 건 시간을 의미. 근데 효율적인 해법이 없을 경우, 즉 NP-완전일 경우가 있음.
- NP-완전 문제에 대한 효율적인 알고리듬이 아직까진 없더라도 존재하지 않는다는 건 아님
- NP-완전 문제들 중 하나라도 효율적인 해법 찾는 순간 나머지도 전부 효율적인 해법이 존재함.
- 몇몇 NP-완전 문제들은 우리가 효율적인 알고리듬을 알고 있는 문제들과 비슷함.
이런 문제 가끔 실무에서도 나옴. 이 경우엔 효율적인 해법 찾는 데 시간 낭비하지 말고 차라리 적당히 좋은 결과를 주는 알고리듬 찾는 게 나음.
병렬화
최고 성능을 위해 다중 코어 나와 일종의 "병렬 컴퓨터" 나옴. 이런 다중 코어에서 최고 성능 내려면 병렬화를 고려한 알고리듬 설계해야 함.
1.2 기술로서 알고리듬
만약 컴퓨터 성능이 미치도록 빠르고 메모리가 무한대라면 알고리듬 공부할 이유가 없음.
물론 현실은 그렇지 않음. 시간과 공간을 효율적으로 사용해야 함.
효율성
같은 문제를 해결해도 알고리듬끼리 성능 엄청 차이날 수 있음.
예를 들어 삽입 정렬 insertion sort은 n 개의 원소를 정렬하는 데 약 c1n2 만큼의 시간이 걸림. 이때 c1은 n에 의존하지 않는 상수이므로 전체적으로 n2에 비례하여 시간이 증가함. 병합 정렬 merge sort은 약 c2n log n 만큼의 시간이 걸림. c2 또한 n에 의존하지 않는 상수임. 삽입 정렬이 병합 정렬보다는 보통 더 작은 상수 계수를 가지므로 c1 < c2임. 근데 나중에 n의 값이 거치면 이 상수의 대소관계는 무의미해짐. 결국 n log n보다는 n2의 증가율이 훨씬 높아서 병합 정렬이 삽입 정렬보다 더 빠름.
알고리듬과 다른 기술
컴퓨터 하드웨어처럼 알고리듬도 기술 technology로서 대해야 함 빠른 하드웨어만큼이나 알고리듬에 따라 전체 시스템 성능이 결정됨.
- 고급 컴퓨터 구조와 제작 기술
- 사용하기 편하고, 직관적인 그래픽 사용자 인터페이스 (GUI)
- 개체지향 시스템
- 통합 웹 기술
- 빠른 유무선 네트워크
여기에 알고리듬 영향 많이 줌.
어플리케이션 수준에서 알고리듬적인 부분 없는 어플리케이션도 알고리듬에 상당히 의존함. 모든 것이 알고리듬에 의존함.
이제 컴퓨터도 많아져서 알고리듬이 해결할 문제의 규모도 커짐. 그래서 효율성이 더욱 중요함.
알고리듬에 대한 기본 기초가 잘하는 프로그래머와 못하는 프로그래머를 나눔.
