2008. 10. 16. 22:00 :: 알고리즘코딩기법
안녕하세요 SSM17.2기 (17-2기 라고 해야 맞는건가요?) 조일룡입니다.
온라인 개인형 맞춥시그 - 가칭 주제없는 시그 - 에서 제가 맡은 주제는 '알고리즘 코딩기법' 입니다.
주제는 뭐 저렇구요.. 코딩 얘기만 하는 것이 아니라 이것 저것 다양한 주제로 포스팅을 해 볼까 합니다.
주로 참고할 레퍼런스로는...
The Art of Computer Programming / Donald E. Knuth (ISBN:9788979144307)
Introduction to Algorithm / Cormen (ISBN:9788979143171)
생각하는 프로그래밍 / Jon Bentley (ISBN:9788995300930)
와 각종 인터넷을 참고하겠습니다.
우선 오늘은 첫 포스팅이니 만큼 가벼운 주제로 시작을 하겠습니다 ^^;
아마 앞으로도 계속 가벼운 주제로 포스팅을 하게 될 것 같습니다.
알고리즘
우선은 알고리즘(algorithm)이라는 단어에 대해서 대충 알아보도록 합시다
"알고리즘(algorithm)"이라는 단어는 그 자체로 상당히 흥미로운데, 언뜻 보면 로가리즘(logarithm)의 처음 네 글자를 뒤섞어놓은 것 같다. 이 단어는 1957년이 되어서야 Webster's New World Dictionary에 올랐다. 그 전까지는 알고리즘의 예전 형태인 algorism밖에 없었다. algorism의 고전적인 의미는 '아라비아 숫자를 이용한 산술'이었다. 중세에는 계산판을 이용해서 계산을 하는 계산판 사용자들과 아라비아 숫자를 이용해서 계산을 하는 알고리스트들이 있었다.
...
algorism의 형태와 의미는 점차 변질되었다. Oxford English Dictionary는 이 단어가 식자들이 arithmetic의 그리스어 어원과 혼동함으로써 "최근의 algorithm을 포함한, 여러 유사어원학적 왜곡을 거쳤다"고 설명한다. 사람들이 이 단어의 기원을 이미 잊었다는 점을 생각한다면, "algorism"이 "algorithm"으로 변한 것이 그리 이해 못할 일은 아니다.
- The Art of Computer Programming
자, 이제 알고리즘의 어원에 대해 알아봤으니 그 특징에 대해 알아봅시다.
위대한 학자 Knuth님 께서는 알고리즘의 중요한 다섯가지 특징을 다음과 같이 정리를 하셨습니다.
1. 유한성: 알고리즘은 단계들을 반드시 유한한 횟수로 거친 후에 종료해야 한다.
2. 명확성: 알고리즘의 각 단계는 반드시 명확하게 정의되어야 한다.
3. 입력: 알고리즘은 0또는 그 이상의 입력들을 가진다.
4. 출력: 알고리즘은 하나나 그 이상의 출력들을 가진다.
5. 효과성: 일반적으로 알고리즘은 효과적(effective)이어야 한다고 간주된다.
알고리즘의 중요성
그렇다면 알고리즘을 왜 공부해야 할까요?
컴퓨터의 성능은 하루가 다르게 발전하고 있고 프로그램은 나날히 거대하고 복잡한 괴물이 되고 있습니다. 공학적 측면에서 따져봤을 때 프로그램의 효율성보다 개발주기를 짧게하고 유지보수를 용이하게 하는 것에 중점을 둬야 하는건 당연한 이치입니다. 하지만 그렇다고 프로그램의 효율성을 완전히 무시할 수 있을까요?
컴퓨터가 무한히 빠르고 메모리는 따로 비용이 들지 않는다고 생각해보자. 그런 경우에도 알고리즘을 공부할 이유가 있을까? 자신이 개발한 알고리즘이 타당한 답을 출력하면서 종료된다는 것만을 보여주고자 하는 경우라면 이 질문에 대한 답은 참일 것이다.
하지만 컴퓨터가 무한히 빠를 경우, 어떤 문제를 해결하는 타당한 알고리즘들 역시 모두 무한히 빠를 것이다. 따라서 자신이 구현한 방법이 훌륭한 소프트웨어 공학의 실현범위 안에 있음을 보이고 싶겠지만 사실 어떤 방법으로 구현하든 차이는 없다.
물론, 컴퓨터가 상당히 빠를수는 있다. 하지만 무한히 빠를 수는 없다. 메모리 역시 매우 값쌀 수는 있지만 비용이 전혀 들지 않을 수는 없다. 결국 계산 시간은 일종의 한정된 자원이며 메모리 공간도 마찬가지다. 이러한 자원들은 효율적으로 사용되어야 하며 시간과 공간의 측면에서 효율적인 알고리즘이 필요하게 된다.
하지만 컴퓨터가 무한히 빠를 경우, 어떤 문제를 해결하는 타당한 알고리즘들 역시 모두 무한히 빠를 것이다. 따라서 자신이 구현한 방법이 훌륭한 소프트웨어 공학의 실현범위 안에 있음을 보이고 싶겠지만 사실 어떤 방법으로 구현하든 차이는 없다.
물론, 컴퓨터가 상당히 빠를수는 있다. 하지만 무한히 빠를 수는 없다. 메모리 역시 매우 값쌀 수는 있지만 비용이 전혀 들지 않을 수는 없다. 결국 계산 시간은 일종의 한정된 자원이며 메모리 공간도 마찬가지다. 이러한 자원들은 효율적으로 사용되어야 하며 시간과 공간의 측면에서 효율적인 알고리즘이 필요하게 된다.
- Introduction to Algorithm
컴퓨터가 빨라지고 있다고는 하지만 무한대로 빠를 수는 없습니다. 메모리도 마찬가지입니다. 알고리즘이 중요한 원인은 바로 여기에 있습니다. 위의 글과 같이 컴퓨터가 무한히 빠르다면 동일한 문제를 푸는데 1000번의 연산을 하든 100만번의 연산을 하든 10억번의 연산을 하든 상관없습니다. 컴퓨터가 무한히 빠르기 때문에 입력과 동시에 답이 나오겠지요. 하지만 현실적으로 엄청나게 빠른 컴퓨터는 있을 수 있지만 무한히 빠른 컴퓨터는 존재하지 않습니다. 엄청나게 빠른 컴퓨터에서 10억번의 연산을 하는 것과 1000번의 연산을 하는 시간차가 무시할 수 있는 수준이라면 당연히 공학적 측면에서 유리한 프로그램을 선택해야 합니다만 10억의 팩토리얼의 연산을 해야하는 알고리즘이라면 어떨까요..
효율성 외에도 잘 정리된 알고리즘을 사용해서 문제를 해결한 프로그램의 경우 테스트를 거치면서 case by case로 버그를 수정하면서 완성된 프로그램보다 훨씬 간결하고 버그나 tricky한 인풋에 대해 훨씬 견고한 특징을 보여줍니다. 물론 알고리즘이 어려워서 후임 개발자가 이해하지 못한다면 유지보수는 어렵게 되겠지만 그것은 어려운 알고리즘보다는 개발자의 능력의 부족합을 탓해야겠지요
무엇보다 중요한 것은 어떤 문제들은 알고리즘을 모르면 풀지 못한다는 것에 있습니다. 이런 문제와 마주쳤다고 했을 때 알고리즘을 안다면 몇 시간만에 해결할 수 있는 것을 모르는 경우 몇 달이 걸려도 해결하지 못할 수도 있습니다. 물론 그런 문제를 여러분의 회사에서 프로그래밍을 하면서 접하게 될 가능성이 매우 희박하겠지요.. ^^
알고리즘의 선택
예를 들어 256개의 원소를 가진 배열을 생각해봅시다.
이 원소들이 정렬이 안되어 있는 상태에서 하나의 원소를 찾으려면 처음부터 끝까지 찾으려는 원소를 발견할 때 까지 하나씩 검사를 해야합니다. 이를 순차검색이라 하고 평균적으로 n/2의 비교를 해야합니다.
반면 우리가 잘 알고있는 바이너리서치의 경우 log n 번만 비교하여 원하는 원소를 찾을 수 있습니다. 하지만 배열이 정렬이 되어있지 않기 때문에 우선 정렬을 해야합니다. 정렬은 n log n 번의 연산이 필요합니다. (비교 정렬의 경우 필요한 비교횟수의 하한이 Ω(n log n) 임이 증명되었습니다.) 그 후 바이너리서치를 해서 원소를 찾을 수 있으므로 총 연산은 n log n + log n 번이 됩니다.
순차검색과 정렬 후 바이너리 서치의 연산횟수를 비교해 보면 n/2 와 n log n + log n 으로 순차검색이 더 유리합니다. 하지만 한 번이 아니라 필요할 때마다 원소를 검색해야한다면 상황이 달라집니다. 가령 10000번의 검색을 해야한다고 하면 순차검색의 경우 10000 * n/2 번의 연산이 필요합니다. 반면 바이너리 서치의 경우 정렬은 한 번만 수행하면 되므로 n log n + 10000 * log n 번 만큼 연산을 해야 합니다.
원소가 256개 이므로 평균횟수는 다음과 같습니다.
효율성 외에도 잘 정리된 알고리즘을 사용해서 문제를 해결한 프로그램의 경우 테스트를 거치면서 case by case로 버그를 수정하면서 완성된 프로그램보다 훨씬 간결하고 버그나 tricky한 인풋에 대해 훨씬 견고한 특징을 보여줍니다. 물론 알고리즘이 어려워서 후임 개발자가 이해하지 못한다면 유지보수는 어렵게 되겠지만 그것은 어려운 알고리즘보다는 개발자의 능력의 부족합을 탓해야겠지요
무엇보다 중요한 것은 어떤 문제들은 알고리즘을 모르면 풀지 못한다는 것에 있습니다. 이런 문제와 마주쳤다고 했을 때 알고리즘을 안다면 몇 시간만에 해결할 수 있는 것을 모르는 경우 몇 달이 걸려도 해결하지 못할 수도 있습니다. 물론 그런 문제를 여러분의 회사에서 프로그래밍을 하면서 접하게 될 가능성이 매우 희박하겠지요.. ^^
알고리즘의 선택
예를 들어 256개의 원소를 가진 배열을 생각해봅시다.
이 원소들이 정렬이 안되어 있는 상태에서 하나의 원소를 찾으려면 처음부터 끝까지 찾으려는 원소를 발견할 때 까지 하나씩 검사를 해야합니다. 이를 순차검색이라 하고 평균적으로 n/2의 비교를 해야합니다.
반면 우리가 잘 알고있는 바이너리서치의 경우 log n 번만 비교하여 원하는 원소를 찾을 수 있습니다. 하지만 배열이 정렬이 되어있지 않기 때문에 우선 정렬을 해야합니다. 정렬은 n log n 번의 연산이 필요합니다. (비교 정렬의 경우 필요한 비교횟수의 하한이 Ω(n log n) 임이 증명되었습니다.) 그 후 바이너리서치를 해서 원소를 찾을 수 있으므로 총 연산은 n log n + log n 번이 됩니다.
순차검색과 정렬 후 바이너리 서치의 연산횟수를 비교해 보면 n/2 와 n log n + log n 으로 순차검색이 더 유리합니다. 하지만 한 번이 아니라 필요할 때마다 원소를 검색해야한다면 상황이 달라집니다. 가령 10000번의 검색을 해야한다고 하면 순차검색의 경우 10000 * n/2 번의 연산이 필요합니다. 반면 바이너리 서치의 경우 정렬은 한 번만 수행하면 되므로 n log n + 10000 * log n 번 만큼 연산을 해야 합니다.
원소가 256개 이므로 평균횟수는 다음과 같습니다.
순차검색: 10000 * 256/2 = 10000 * 128 = 128만
이분검색: 256 * lg 256(정렬) + 10000 * lg 256(검색) = 256 * 8 + 10000 * 8 = 82048
이분검색: 256 * lg 256(정렬) + 10000 * lg 256(검색) = 256 * 8 + 10000 * 8 = 82048
위와 같이 256개의 원소를 만번 검색해야하는 경우 정렬 후 이분검색이 10배 이상 빠르다는 것을 알 수 있습니다. 원소의 수가 더 많거나 검색 횟수가 많아질수록 이분검색이 더욱더 유리해집니다.
위의 예에서 보는바와 같이 효율적인 알고리즘의 선택은 매우 중요합니다. 어떤 경우 모든경우의 수를 다 따져봐야하는 것 처럼 보이는(이런 방법을 Brute Force라고 하고 문제에 따라 n에 대해 시간복잡도가 지수적으로 증가합니다)문제가 알고보면 리니어하게 풀리는 것도 볼 수 있습니다. 이 때에는 두 알고리즘의 속도차가 상상을 초월하게 됩니다.
tug of war라는 유명한 문제가 있습니다. 이 문제를 Brute Force로 풀면 아무리 빠른 컴퓨터라 할지라도 지구가 멸망할 때 까지 답을 구할 수 없습니다. 하지만 Dynamic Programming기법을 도입하여 풀면 0.1초 이내에 답을 구해냅니다.
지금까지 알고리즘의 기본개념과 효율적인 알고리즘의 중요성을 살펴봤습니다.
다음 포스팅은 '알고리즘 코딩기법'이라는 제목에 충실하게 위의 예에서 살펴봤던 바이너리서치를 구현하는 방법에 대해서 이야기하겠습니다.
부디, 작은 것들을 몸소 익히고,
그런 후에 더 큰 것으로 나아가라.
- 에픽테투스 Epictetus (Discourses IV.i)
그런 후에 더 큰 것으로 나아가라.
- 에픽테투스 Epictetus (Discourses IV.i)
