알고리즘 소개

이 글은 Crash Course의 Computer Science를 보고 정리한 글입니다.

알고리즘(ALGORITHM)은 계산을 완성하는데 사용되는 특정 단계이다.

알고리즘은 같은 결과를 생산해낼 지라도 다른 알고리즘이 보다 우수할 수 있다. 일반적으로 계산에 소요되는 단계가 줄어들수록 더 좋은 결과를 얻을 수 있지만, 때로는 사용하는 메모리 양과 같은 다른 요인들을 고려해야 한다. 

 

알고리즘이라는 용어는 페르시아의 천재였던 Muhammad ibn Musa al-Khwarizmi라는 천년 전에 대수학의 아버지라 불리던 한 사람에게서 비롯된 것이다. 현대 컴퓨터 이전에 존재했던 효율적인 알고리즘의 제작 문제는 현재 과학 분야로 진화한 컴퓨팅을 둘러싼 전체 과학을 이끌어 냈다. 바로 컴퓨터 과학이다.

 

컴퓨터 과학에서 가장 중요한 알고리즘 문제 중 하나는 정렬(Sorting)이다. 예를들면, 이름을 정렬하거나 숫자를 정렬하는 것관 같은 것들을 말한다.

컴퓨터는 항상 정렬한다. 가장 저렴한 항공 요금을 찾고, 가장 최근에 받은 이메일을 정렬하거나, 성씨 순서로 정렬된 연락처를 스크롤하는 것 등 모두 정렬이 필요하다. 정렬된 결과를 생산해내는 알고리즘은 버블 정렬(Bubble sort), 스파게티 정렬(Spaghetti sort) 등 40개가 넘는 알고리즘이 존재한다.

[307, 239, 214, 250, 384, 299, 223, 312] (천원)

제주도에 가기 위한 항공 요금 한 셋트를 가지고 있다고 가정하자. 이와 같은 일련의 항목을 배열이라고 한다. 이 숫자들을 프로그래밍 방식으로 정렬하는 방법을 살펴보겠다.

일단 가장 간단한 알고리즘부터 보자. 먼저 배열을 훑어보면 가장 작은 숫자를 찾는다.

맨 앞에 307부터 시작한다. 유일하게 본 수이기 때문에 현재 가장 작은 수이다.

다음은 239이며 307보다 작으므로 새로운 가장 작은 숫자가 된다. 다음은 214, 새로운 가장 작은 수가 되고, 250, 384, 299, 223, 312 모두 가장 작은 숫자가 아니다. 그래서 모든 숫자를 훑어 보았을 때 214가 가장 작았다. 이것을 오름차순으로 놓기 위해 214를 맨 위에 있는 번호와 위치를 바꾼다. 이제 하나의 숫자가 정렬되었다.

다음 숫자를 정렬하기 위해 동일한 절차를 반복하지만 맨 위에부터 시작하는 대신 한 칸 아래에서 시작한다. 나머지 배열을 스캔하면 223이 두 번째 가장 작은 수이므로 2번째 자리에 있는 숫자와 자리를 바꾼다. 나머지도 계속 스캔하고 바꾸고를 반복한다. 이 과정은 마지막 숫자에 도달할 때까지 계속된다.

그럼 배열이 정렬되었고 제주행 항공편을 예약할 준비가 가능한다. 위와 같은 방법을 선택 정렬(Selection sort)이라고 부르면 기본적인 정렬법이다.

의사 코드를 살펴보자.

선택 정렬의 의사 코드

이 함수는 아무리 많은 숫자라고 하더라도 정렬을 수행할 수 있다. 또한 한 번 함수를 쓰면 계속해서 다시 쓸 수 있다.

이 정렬 알고리즘으로 배열 안의 각 위치를 맨 위부터 맨 아래까지 순환한다. 그런 다음 각 위치에 대해 배열에서 위치를 바꿀 가장 작은 수를 찾을때까지 반복실행한다. 이 코드에서 FOR 루프가 다른 FOR 루프 안에 포함되어 있는 것을 볼 수 있다. 이것은 매우 간단히, 우리가 N개의 항목을 정렬하고 싶다면 N번 반복해야 한다는 것을 의미한다. 그 안에서 루프를 N번 반복하면 총합은 대략 N*N루프 또는 N제곱이 된다.

 

입력하는 수의 크기와 실행되는 단계 수 사이의 관계는 알고리즘의 복잡도를 특징화한다. 그것은 얼마나 빨리 또는 느리게 알고리즘이 실행될지 근사치를 제공한다. 컴퓨터 과학자들은 이러한 성장 순서를 빅오표기법(Big-O notation)으로 기록한

다.

 

선택 정렬 알고리즘을 빅오표기법으로 표기하면 $O(n^2)$이 된다. $n^2$은 특별하게 효율적이 않다. 위의 예제 배열은 n=8개인 항목이므로 8의 제곱은 64의 실행시간이 나온다. 배열의 크기를 8에서 80으로 늘리면 실행 시간은 이제 80의 제곱인 6400이 된다. 배열은 단지 8에서 80으로 10배 증가했지만 실행시간은 100배 증가한다. 이런 영향은 배열이 커질수록 확대된다. 만약 Google과 같은 회사에서 수백만개 또는 수십억개의 검색결과 배열을 정렬해야 한다고 한다면 이것은 큰 문제가 된다.

 

[307, 239, 214, 250, 384, 299, 223, 312] (천원)

다시 이전 예제로 돌아가서 이번에는 다른 정렬 알고리즘인 합병정렬(Merge sort)을 해보자. 합병정렬은 첫 번째 작업으로 배열의 크기가 1보다 큰지 확인한다. 1보다 큰 경우 배열을 두 개로 나눈다. 배열의 크기가 8이므로 크기가 4인 두개의 배열로 쪼개진다. 이들은 크기가 1보다 여전히 크기 때문에 다시 크기가 2인 배열로 나뉜다. 마지막에 각각 1개의 항목인 8개의 배열로 분해된다. 이제 합병이라는 이름을 얻게 된 합병정렬을 할 준비다 된것이다.

처음 두 배열을 시작으로 첫 번째 값이자 유일한 값인 307과 239를 읽는다. 239가 더 작으므로 먼저 그 값을 가져온다. 남은 번호는 307뿐이므로 두 번째 값으로 집어넣는다. 두 개의 배열이 성공적으로 병합됐다. 이제 남겨진 쌍들에 대해서 이 과정을 반복하며 그들을 정렬된 순서로 놓는다. 이제 2개의 항목인 4개의 배열이 되었다.

[239, 307], [214, 250], [299, 384], [223, 312]

이제 다음 합병 과정이 반복된다. 다시, 첫 번째 두 배열을 취해서 그안에 있는 첫 번째 숫자를 비교한다. 239와 214 중 214가 제일 작기 때문에 숫자를 첫 번째로 가져온다. 이제 두 배열에서 처음 두 숫자를 다시 살펴본다. 239와 250 중 239가 더 작으므로 그 숫자를 다음으로 가져온다. 다음 307과 250 중 250이 더 작으니 이걸 가져오고, 마지막으로 307만 남았으므로 끝부분에 추가한다.

모든 경우에서 두 개의 배열로 시작하여 개별적으로 정렬하고 이들을 합병하여 더 크게 정렬된 배열로 만든다. 이렇게 남아있는 배열들에 대하여 똑같은 합병 과정을 반복한다. 모든 숫자가 합병될 때까지 이 작업을 반복하면 배열은 완전히 다시 정렬된다.

합병정렬의 계산 복잡도는 빅오표기법으로 $O(nlogn)$이다. N은 비교하고 합병하는 데에 필요한 횟수만큼 발생한다. 이 횟수는 정렬 안의 배열 항목 수와 직접 비례한다. logN은 병합 단계의 수에서 나온다. 위의 예에서는 8개의 항목인 배열을 4개로, 2개로, 1개로 총 3번 쪼개었다. 이런 식으로 반으로 나누는 것은 항목 수 사이에 로그관계를 가지고 있다. ($log_28=3$)

배열의 크기가 두배인 16으로하면 정렬할 항목 수는 두 배가 늘어난다. $log_16=4$이므로, 분할 단계 횟수는 1이 증가하여 총 전체적으로 약 2.7배 정도(24->64) 늘어난다. 배열의 크기를 8에서 8000으로 늘려도 분할 단계 수는 꽤 낮다. ($log_28000 \approx 13$)

이러한 이유로 병합 정렬이 선택 정렬보다 훨씬 효율적이다.

 

이렇게 알고리즘의 빙산의 일각만을 다루었지만, 컴퓨터 과학자가 되는 핵심 부분은 기존 알고리즘을 사용해서 필요에 따라 새로운 알고리즘을 작성하는 데에 있다. 이 글을 통해 알고리즘에 흥미를 갖고 더 찾아보길 바란다.