•
프로그래밍을 배우는 사람은 알고리즘을 학습하며 많은 것을 얻을 수 있다.
◦
알고리즘 코스를 학습하며 새로운 문제를 푸는데 필요한 중요한 작업과 기술을 익힐 수 있다.
◦
외에도 프로그래밍의 좀더 일반적인 수준에서 훨씬 더 중요한 영향을 끼친다.
1. 세 가지 문제
•
최대 40억 개의 32비트 정수가 랜덤한 순서로 들어있는 순차적 파일이 주어졌다. 이때 이 파일에 포함되지 않은 임의의 32비트 정수 하나를 찾아라.
◦
메모리를 넉넉히 쓸 수 있다면 이 문제를 어떻게 풀겠는가?
◦
메모리가 수백 바이트밖에 없고 너댓 개의 외부 임시 파일을 사용할 수 있는 상황이라면 어떻게 해결할 수 있을까?
•
n개의 원소를 가지는 1차원 벡터를 i만큼 왼쪽으로 회전시켜라.
◦
예를 들어 n=8, i=3일 경우, abcdefgh라는 벡터를 회전시키면 defghabc가 된다.
◦
여분의 메모리가 수십 바이트 밖에 안 되는 상황에서도 n에 비례하는 시간 내에 벡터를 회전시킬 수 있을까?
•
주어진 영단어 사전에서 전철어구의 집합을 모두 찾아내라.
◦
예를 들어 pots, stop, tops는 철자의 순서만 바꾸면 만들어지므로 서로 전철어구이다.
2. 여기저기에 쓰이는 이진 탐색
•
프로그래밍에서 이진 탐색이 가장 일반적으로 사용되는 예는 정렬된 배열 내의 한 요소를 찾아내는 것이다.
•
그러나 이진 탐색의 응용은 단순히 정렬된 배열을 빠르게 탐색하는 것에서 그치지 않는다.
◦
우리는 앞서 첫 번째 문제를 풀기 위해 이진 탐색을 응용해볼 수 있다.
•
40억개의 숫자 중, 가장 앞의 비트가 0인 숫자와 1인 숫자를 나눈다. 그럼 그 중 더 사이즈가 하나 더 작은 쪽에 우리가 찾는 빈 숫자가 있음을 알 수 있다.
◦
해당 파일을 선택하여 이번엔 두 번째 비트를 검사한다. 이렇게 점차 더 작은 쪽의 파일을 선택해나가다 보면 빠져있는 숫자를 찾을 수 있을 것이다.
3. 기초적인 조작의 위력
•
문제 B는 n개의 원소를 가지는 벡터 x를 i만큼 왼쪽으로 회전시키고자 하는 문제였다.
•
이때 회전에 드는 시간은 n에 비례해야 하고 수십 바이트 정도의 여분 메모리만을 사용할 수 있다.
•
여기서 우리가 아는 알고 있어야 하는 점은 회전이란 결국 서로 크기가 다른 인접한 메모리 블록의 자리를 바꾸는 작업이라는 것이다.
◦
x의 처음 i개 원소를 임시 배열에 복사하고 나머지 n-i개의 원소를 i만큼 이동시킨 후, x의 뒤쪽에 임시 벡터에 있던 i개의 원소를 다시 복사하는 방법으로 회전을 구현할 수도 있다.
▪
그러나 이는 정해진 조건 안에서 문제를 풀어내기엔 적합하지 않다. 위 기법 대신 적용시켜볼만한 기법으로 저글링 기법이 있다.
◦
저글링 조작이란 x[0]을 임시 저장소인 t로 옮긴 후 x[i]를 x[0]으로 x[2i]를 x[i]로 옮기는 식의 조작을 말한다.
▪
이 조작은 t로부터 원래의 x[0]을 가져오면서 끝난다. 한 번의 조작으로 모든 원소가 옮겨지지 않았다면 x[1]을 시작으로 조작을 가한다.
◦
이 문제를 보는 관점을 바꾸면 또 다른 알고리즘을 생각해낼 수 있다.
▪
벡터 x를 회전시키는 것은 결국 벡터 ab의 두 부분을 맞바꾸어서 벡터 ba로 바꾸는 것이다.
•
a는 x의 처음 i개의 원소를 나타낸다.
▪
a의 원소의 개수가 b보다 작다고 가정하면 b를 b의 뒤에서 a만큼의 길이와 a를 교환하고 나머지를 다시 바꾸는 문제에만 집중하면 된다.
4. 정렬
•
문제 C는 수 많은 접근방법이 존재하며 이들은 아주 비효율적이고 복잡하다. 어떤 단어에 포함되어 있는 모든 문자의 순열을 고려하는 방법은 당연히 실패할 것이다.
•
이 문제는 두 개의 작은 문제로 나눠 풀어낸다. 하나는 표시를 정하는 것이고 나머지는 같은 표시의 단어를 모으는 것이다.
◦
첫 번째 문제는 정렬을 기반으로 한 표시를 사용하면 된다. 단어에 있는 문자들을 알파벳 순서로 정렬하는 것이다.
◦
두 번째 문제는 단어들을 각각의 표시 순서에 따라 정렬하여 풀 수 있다.
5. 원리
•
정렬
◦
정렬을 사용하는 것은 당연하게도 정렬된 출력을 위한 것으로 시스템의 명세일 수도 있지만 다른 프로그램의 입력을 위한 단계일 수도 있다.
◦
전철어구를 찾는 문제에서의 관심사는 정렬 자체가 아니었다. 같은 종류의 원소를 모으기 위해 정렬을 시켰을 뿐이다.
•
이진 탐색
◦
정렬된 집합에서 원하는 원소를 찾아내는 알고리즘으로 매우 효율적이고 메모리나 디스크 상에서 사용될 수 있다.
◦
유일한 단점은 전체의 집합을 미리 알고 있어야 하며 탐색에 앞서 이미 정렬된 상태여야 한다는 점이다.
•
표시
◦
하나의 동치관계가 집합을 정의하는 경우, 그 집합에 포함되는 모든 원소가 같은 표시를 가지도록 정의하는 것이 도움이 된다.
◦
단어 내의 문자를 정렬하여 하나의 전철어구 집합에 대한 표시를 만들 수 있다.
•
문제 정의
◦
이 칼럼의 주제는 문제를 정의한 다음의 과정이다. 어떤 기초적인 조작을 이용해 문제를 해결할 것인가? 새로운 간단한 조작을 정의함으로써 어렵던 문제가 쉽게 해결되는 것을 앞의 예제들을 통해 알 수 있다.
•
문제 해결자의 관점
◦
훌륭한 프로그래머는 약간 게으른 면이 있다. 그들은 처음의 아이디어를 바로 적용하려 달려들기보다는 문제를 좀더 깊게 분석하여 어떤 영감을 얻으려고 한다.
◦
물론 분석만 하면 안되며 적당한 때에 구현을 시작할 수 있는 균형이 필요하다. 그 적당한 때를 아는 것이 진정한 능력이다.
