1. 시작하며
컴퓨터 알고리즘이란 어떠한 문제를 해결하는 방법을 컴퓨터의 입장에서 정리한 풀이이다. 일반적인 알고리즘에 대해서는 알고리즘을 참고하자. 컴퓨터에게 명령을 내리는 우리의 입장에서 알고리즘은 왜 필요할까?컴퓨터가 무한히 빠르고 메모리는 따로 비용이 들지 않는다고 생각해보자. 그런 경우에도 알고리즘을 공부할 이유가 있을까? 자신이 개발한 알고리즘이 타당한 답을 출력하면서 종료된다는 것만을 보여주고자 하는 경우라면 이 질문에 대한 답은 참일 것이다.
하지만 컴퓨터가 무한히 빠를 경우, 어떤 문제를 해결하는 타당한 알고리즘들 역시 모두 무한히 빠를 것이다. 따라서 자신이 구현한 방법이 훌륭한 소프트웨어 공학의 실현범위 안에 있음을 보이고 싶겠지만 사실 어떤 방법으로 구현하든 차이는 없다.
물론, 컴퓨터가 상당히 빠를수는 있다. 하지만 무한히 빠를 수는 없다. 메모리 역시 매우 값쌀 수는 있지만 비용이 전혀 들지 않을 수는 없다. 결국 계산 시간은 일종의 한정된 자원이며 메모리 공간도 마찬가지다. 이러한 자원들은 효율적으로 사용되어야 하며 시간과 공간의 측면에서 효율적인 알고리즘이 필요하게 된다.
Introduction to Algorithms중
위 인용문의 내용 그대로, 컴퓨터가 무한히 빠르게 명령을 처리할 수 있으면 우리는 알고리즘을 배울 필요가 없다. 하지만, 실제로는 그렇지 않으며 같은 문제도 풀이하는 방법에 따라 시간상, 메모리상 효율을 극명히 갈리는 경우가 많다.하지만 컴퓨터가 무한히 빠를 경우, 어떤 문제를 해결하는 타당한 알고리즘들 역시 모두 무한히 빠를 것이다. 따라서 자신이 구현한 방법이 훌륭한 소프트웨어 공학의 실현범위 안에 있음을 보이고 싶겠지만 사실 어떤 방법으로 구현하든 차이는 없다.
물론, 컴퓨터가 상당히 빠를수는 있다. 하지만 무한히 빠를 수는 없다. 메모리 역시 매우 값쌀 수는 있지만 비용이 전혀 들지 않을 수는 없다. 결국 계산 시간은 일종의 한정된 자원이며 메모리 공간도 마찬가지다. 이러한 자원들은 효율적으로 사용되어야 하며 시간과 공간의 측면에서 효율적인 알고리즘이 필요하게 된다.
Introduction to Algorithms중
그렇기 때문에, 우리는 컴퓨터를 보다 효율적으로(혹은 안정적으로[1]) 다루기 위해 알고리즘을 배워야 하는 것 이다.
구체적인 예를 들어보겠다. 다음 문제를 생각해 보자.
변수 A와 B가 있다. 이 둘의 값을 맞바꾸는 방법을 구하시오.
마땅한 답이 떠오르지 않을 수 있지만 대부분의 사람들은 이렇게 대답할 것이다.
A를 C[2]에 넣고, A에 B를 넣고, B에 C를 넣습니다.
맞다. 이렇게 문제를 풀 수 있다.[3] 하지만 진짜 이것이 문제를 푸는 최선의 방법일까?
위의 답의 시간적, 메모리적 자원 소모를 보면 3번의 대입을 3개의 변수로 수행했다. 하지만 조금 더 생각해보면 이보다 더 효율적인 풀이도 있음을 알 수 있다.
A=A+B, B=A-B, A=A-B
위의 방법이 이해가 되지 않을 수 있기에 계산에 사용되는 변수를 A, B 대신 다른 것을 써보겠다.
A, B을 바꿔보자.
C=A+B이다.
B=C-B=A+B-B=A이다.
A=C-B=A+B-A=B이다.
실제로는 C대신 A를 이용해도 무방하다.
위의 풀이도 1번 풀이와 같게 효율성을 따져보면 3번의 계산을 2개의 변수로 수행했다. 더 적은 메모리를 사용하는 셈이다.C=A+B이다.
B=C-B=A+B-B=A이다.
A=C-B=A+B-A=B이다.
실제로는 C대신 A를 이용해도 무방하다.
이처럼 아주 간단한 문제도 창의적인 아이디어를 통해 더 효율적인 방법으로 풀 수 있다. 이는 어려운 문제도 다름없이 적용된다. Tug of war만 보더라도 문제를 다르게 생각해서 나온 아이디어가 효율성을 얼마나 비약적으로 높여주는지 알 수 있다. 그리고, 이렇게 어떤 문제를 어떻게 효율적으로 풀지 연구하기 위해 공부하는 것이 컴퓨터의 알고리즘이다.
2. 기본 아이디어
컴퓨터의 많은 알고리즘들은 모두 기발한 아이디어에 기반하고 있지만 대부분의 알고리즘들은 다음 아이디어들에서 나왔다. 가령 정렬 알고리즘중 최고로 손꼽히는 퀵정렬과 탐색알고리즘의 하나인 이분검색은 분할정복에서 아이디어를 따왔으며 Tug of War는 동적계획법에서 아이디어를 따와 풀수 있는 문제이다.
[1]
불안정한 알고리즘은
반례가 있을 수 도 있다.
[2]
프로그래밍 언어에서는 이를 임시 변수(tmp)로 선언한다.
[3]
기초 프로그래밍 수업에서는 상황극을 시키기도 한다. 甲과 乙이라는 친구를 교실 앞으로 불러내어 각각 빨강 사과와 녹색 사과를 준 다음, 서로 바꾸기 위해서 자리에 앉아있는 丙이라는 친구를 불러내어, 丙이 甲에게 빨강 사과를 받고, 甲이 乙에게 녹색 사과를 받고, 乙이 丙에게 빨강 사과를 받으면 된다.