알고리즘입문

04학번 권정욱과 03 강희경이 함께 계획한 알고리즘의 정의 소개, 재귀 호출 시범(권정욱), 간단한 알고리즘 시연과 프로그래밍의 자세(강희경)이라는 내용으로 진행된 세미나.

실전 프로그래밍에서는 정렬 알고리즘이 대게 라이브러리나 API를 통해서 미리 주어저 있기 때문에 직접 작성하는 경우는 드물다. 하지만 정렬 알고리즘의 속에는 프로그래밍에서 마주치는 알고리즘 문제의 '피와 살'이 모두 녹아 있다. 알고리즘을 집대성한 "The Art Of Computer Programming"의 저자 도널드 카누스 교수는 정렬 알고리즘에 대해서 30여년 전에 다음과 같이 말했다.

~cpp "정렬은 전통적으로 비즈니스 데이터 처리의 과정에서 사용되어 왔지만 모든 프로그래머들이 다양한 상황에서 사용하기 위해서 반드시 기억해야 하는 기초적 도구이다."

정렬 알고리즘 중에서 가장 널리 알려져 있는 것 중 하나가 '퀵정렬(Quick Sort)'이다. 퀵정렬은 현재 옥스퍼드 대학의 명예교수인 토니호어가 60년대에 발명한 알고리즘으로 '재귀'를 이용한 매우 간단하고 아름다운 정렬기법이다.

~cpp 
QuickSort(list)
{
 if(length(list)<2){
  return list
 }
 X = PickPivot(list)
 list1 = {y in list where y < x}
 list2 = {x}
 list3 = {y in list where y > x}
 QuickSort(list1)
 QuickSort(list2)
 QuickSort(list3)
 return Concatenate(list1, list2, list3)
}

1.리스트에서 x를 잘 고른다.
2.x보다 작은 값들은 왼쪽 리스트, 큰 값들은 오른쪽 리스트에 속한다.
3.왼쪽 리스트에 대해서 (재귀적으로) 퀵정렬을 수행한다.
4.오른쪽 리스트에 대해서 (재귀적으로) 퀵정렬을 수행한다.
5.정렬이 끝난 왼쪽 리스트, x, 오른쪽 리스트를 모두 하나로 이어 붙인다.
주의: x를 잘 골라야한다. x가 리스트의 최대 또는 최소값이면 최악의 경우(Worst Case)이다. x를 고르는 방법에 따라서 알고리즘의 성능이 조금씩 달라지기 때문에 퀵정렬 알고리즘에는 여러가지 변형이 존재한다.

모든 알고리즘은 저마다 최적의 조건과 최악의 조건이 다르기 때문에 환경의 변황에 따라서 알고리즘의 수행방식이 조금씩 달라지는 변형된 모습을 가지고 있다.
'밀리세컨드(1/1000초)'를 다투는 정렬 알고리즘에서 간단한 명령어를 하나 더 더하거나 논리의 흐름을 조절하는 방식을 약간 바꾸는 행위만으로도 전체적으로 성능에 영향을 미칠 수 있다.
알고리즘을 공부할 때는 무슨 알고리즘이 이렇고 저렇고 하며 암기를 할 것이 아니라, 각 알고리즘이 구현하고 있는 핵심 방법론을 이해하는 것이 중요한다.

1.이것이 최선일까?
2.혹시 여기를 이렇게 바꾸면 더 낫지 않을까?
이런 의심과 실험은 컴퓨터 프로그래머에게 가장 소중한 덕목이다.

효율적인 검색은 정렬을 필요로 하고, 효율적인 정렬은 검색을 필요로 하는 경우가 많다.

63빌딩 문제
63빌딩의 옥상(64층)에서부터 x층까지는 사람이 뛰어내리면 죽지만 (x-1)층부터 1층까지는 사람이 뛰어 내려도 죽지는 않는다. 최다 몇명을 떨어뜨려야 x층을 알아낼 수 있을 까?
정답: 5명(Binary Search)

가독성(readability)이 알고리즘의 형식이라면 효율성(efficiency)은 알고리즘의 내용이다.
효율성은 끊임없이 의심하고 실험하는 프로그래머의 '최적화(Optimazing)'과정에 의해서 달성된다.

피보나치순열
F(n) = 1 (n<=2일때)
F(n) = F(n-1) + F(n-2)(n>2일때)

~cpp 
int Fibonacci(int n)
{
 if(n<=2){
  return 1;
 }
 else{
  return Fibonacci(n-1) + Fibonacci(n-2);
}

논리가 깔끔하여 군더더기가 전혀 없지만 성능면에서도 최적일까?
재귀가 진행될수록 호출이 폭발적으로 늘어난다.
만약 n=6이라면 1)Fibonacci(5), 2)Fibonacci(4)를 호출하고
1)Fibonacci(5)는 3)Fibonacci(4), 4)Fibonacci(3)을 호출하고,
2)Fibonacci(4)는 5)Fibonacci(3), 6)Fibonacci(2)를 호출하고...
여기선 재귀보다 for나 while 루프를 돌려가는 것이 더 빠르고 효율적이다.

대게의 경우 속도가 향상되면 공간(memory)의 소비는 증가하고 공간의 소비가 줄면 속도가 느려진다. 이 둘의 균형을 잘 맞춰야한다.
알고리즘의 속도를 분석하는 것은 결코 이론적이고 추상적인 일에 머물지 않는다. 평상시에 떠오르는 아이디어나 코드의 설계를 가볍게 스케치하기 위한 수첩을 하나쯤 들고 다니다가 자기가 작성한 알고리즘의 성능을 분석해 보는 것은 프로그래머가 가질만한 좋은 습관이다.

코딩: (별 생각없이)키보드에 손을 대면서 프로그래밍을 시작한다.
프로그래밍: 문제를 분석하고 해결방안을 생각해내고 프로그래밍을 시작한다.

제가 다룬 내용밖에 없어서 세미나 내용을 모두 적지 못했습니다. 위의 내용은 "누워서 읽는 알고리즘"이라는 책을 참고하였습니다. --강희경