[책을 읽고] 알고리즘 라이프 / 알리 알모사위
다양한 알고리즘을 간략하게 소개하는 책이다. 양말 더미에서 짝을 맞춰야 하는 상황이라든가, 미로에서 빠져나가야 하는 일상생활(?) 상황을 설정하여 '재미있게' 즐길 수 있도록 배려했다. (물론 재미없다.)
여러 개의 알고리즘을 간략히 둘러볼 수 있게 소개한 점, 그리고 문제풀이에 소요되는 시간의 종류를 쉽게 설명해주는 점이 좋다.
문제풀이에 소요되는 시간(의 증가율)은 다음과 같은 용어들로 설명할 수 있다.
상수시간 - (항목의 개수가 많지 않을 때) 항목의 수를 두 배로 늘려도 작업완료에 같은 시간이 소요된다.
로그시간 - (항목의 수가 충분히 많을 때) 항목의 수가 두 배가 되면 작업완료에 시간이 1 더 소요된다. (밑이 2인 로그)
선형시간 - (항목의 수가 충분히 많을 때) 항목의 수가 두 배가 되면 작업완료에 걸리는 시간도 두 배가 된다.
선형로그시간 - (항목의 수가 충분히 많을 때) 항목의 수가 두 배가 되면 작업완료에 걸리는 시간은 두 배 +1이 된다.
이차시간(quadratic time) - (항목의 수가 충분히 많을 때) 항목의 수가 두 배가 되면 작업완료에 걸리는 시간은 2^2=4배가 된다.
지수시간 - (항목의 수가 충분히 많을 때) 항목의 수가 겨우 1 늘어나는데 작업완료에 걸리는 시간은 두 배가 된다!
예컨대 크기별로 정렬되어 있는 셔츠 매대에서 맞는 셔츠를 찾으려고 할 때, 그냥 처음부터 순서대로 뒤지면 선형시간이 걸리지만, 중간부터 시작해서 내 사이즈보다 큰지 작은지에 따라 좌우로 움직이면 로그시간이 걸린다. 셔츠 1개를 확인하는 데 1초가 걸린다고 가정하자. 100개의 셔츠 중에서 골라야 한다면, 선형시간이 걸리는 방법은 최악의 경우 100초가 걸린다. 반면 이진검색이라 불리는 두 번째 방법은 최악의 경우, log2(100), 약 7초가 걸린다. 이진검색은 로그시간이 걸리기 때문에, 항목의 수가 많아지면 더 드라마틱한 결과를 낸다. 셔츠가 1,000개일 경우, 선형검색은 최대 1,000초가 걸리지만 이진검색은 log2(1000), 즉 10초 정도밖에 걸리지 않는다.
모든 비선형 방법에는 초기투자가 따른다. 예컨대 새로운 아이템을 정렬된 목록 가운데로 삽입하고자 하는 경우, 선형적 방법보다 빠른 것은 연결 목록(linked list)를 사용하는 것이다. 이 방법은 훨씬 빠른 대신 연결 목록 구성에 비용이 소모되며, 비용은 물론 시간을 포함한다. 이중 연결 목록(douubly linked list)이라면 더욱 그럴 것이다.
10장에 소개된, 층마다 설치된 분리수거함에서 쓸 만한 빈 상자를 구하는 사례의 경우, 그냥 1층부터 뒤지는 것보다는 CCTV를 한번 확인하고 빈 상자가 있는 층으로 가는 것이 훨씬 빠르다. 앞의 방법은 선형시간, 뒤의 방법은 상수 시간이 걸린다. 그러나 CCTV를 확인하는 데에도 시간이 소요된다. 만약 1층 분리수거함에 빈 상자가 있었다면, 앞의 방법은 1의 시간이 걸렸겠지만 뒤의 방법은 (CCTV 확인에도 1의 시간이 필요한 경우) 2의 시간이 걸린다. 그러나 아파트가 10층만 되어도 선형시간의 기대값은 5.5이고, 상수시간의 기대값은 2다.
문제풀이에 시간이 적게 걸리는 것이 좋아 보이지만, 그렇지 않은 경우도 있다. RSA 암호 체계가 그런 사례다. 두 개의 소수를 곱하는 것은 순식간에 뚝딱 되지만, 곱해진 수에서 그 두 개의 소수를 추측하는 것은 용인할 수 없는 수준의 시간이 걸린다. 덕분에 우리가 휴대폰으로 송금도 하고 주식도 살 수 있는 것이다.
물론, 누군가가 혜성처럼 나타나 P=NP라는 것을 증명하기라도 한다면, 은행들은 당장 다른 방법을 찾아야 할 것이지만.
