어디에나 있고 무엇이든 하는 알고리즘 이야기
문병로(지음), 김영사
얇은 책이지만, 나같이 컴퓨터공학에 대해서 잘 알지 못하는 이들은 반드시 읽어야 하는 책이다. 업무로 인해 지금도 공학을 전공한 개발자와 이야기하고 데이터베이스 구조나 프로그램 로직 설계를 같이 검토하지만, 뭔가 제대로 알지 못한다는 느낌이 들어 최근에는 파이썬 책까지 샀다.
알고리즘Algorithm은 무함마드 이븐 무사 알 콰리즈미라는, 9세기 이란 아바스 왕조 시대 대수학의 고전을 쓴 학자 이름에서 유래했다고 한다. 이 때의 아랍은 정말이지, 넘사벽이었다. 이 책은 알고리즘의 학문적 배경을 이야기하면서 간단하게 어떤 식으로 동작하는가를 설명한다. 책을 읽으면서 노트한 걸 옮겨놓는다.
여행하는 세일즈맨 문제 traveling salesman problem
- 세일즈맨이 고객을 모두 방문하고 돌아오는 가장 짧은 경로를 찾는 것. (17쪽)
위 문제를 약자로 TSP라고 하는데, 극악의 난이도를 자랑한다. 고객이 거주하는 장소의 수가 늘어날 수록 가능한 경로의 수가 기하급수적으로 늘어난다. 가령 10개의 장소를 방문하고 돌아온다면 약 36만개의 경로가 생겨난다. 이를 해결하는 방식으로는 대체적으로 아래와 같다.
TSP는 NP-hard 문제이므로, 모든 가능한 경로를 탐색하는 완전 탐색 알고리즘은 도시 수가 조금만 늘어나도 현실적인 시간 내에 해를 구할 수 없습니다. 따라서 다양한 근사 알고리즘과 휴리스틱 알고리즘이 개발되어 사용됩니다.
완전 탐색 (Brute Force): 모든 가능한 경로를 생성하고 거리를 계산하여 최적 해를 찾습니다. 도시 수가 적을 때만 가능합니다.
동적 계획법 (Dynamic Programming): 부분 문제들을 해결하고 결과를 저장하여 중복 계산을 피하는 방법입니다. 완전 탐색보다는 효율적이지만, 여전히 도시 수가 많아지면 메모리 사용량이 크게 증가합니다. (예: Held-Karp 알고리즘)
근사 알고리즘 (Approximation Algorithms): 최적 해를 보장하지는 않지만, 비교적 짧은 시간 안에 최적 해에 가까운 해를 찾는 알고리즘입니다. 성능 보장(최적 해와의 오차 범위)이 있는 알고리즘도 있습니다. (예: Christofides 알고리즘)
휴리스틱 알고리즘 (Heuristic Algorithms): 경험적 지식을 바탕으로 좋은 해를 빠르게 찾는 알고리즘입니다. 최적 해를 보장하지 않으며, 성능 보장도 어렵지만 실제 문제에서 유용하게 사용됩니다. (예: Greedy 알고리즘, 유전 알고리즘, 시뮬레이티드 어닐링, 타부 탐색) (* Gemini의 답변 인용)
알고리즘은 데이터를 처리하기 위해서는 자료구조를 사용하게 되는데, 여기에는 배열, 리스트, 스택, 검색트리, 그래프 등으로 설명하고 있다.
배열은 연속된 공간을 점유해야 해서 사용하기 전에 미리 메모리공간을 할당받고 시작해야 한다. 문제는 리스트가 얼마나 커질지 사전에 알 수 없다는 것이다.
파이썬언어는 리스트 자료구조를 제공한다.
스택Stack - 데이터를 다루는 자료 구조.
큐queue - 작업을 차례대로 처리할 수 있도록 하는 자료구조
검색트리 - 이진검색트리, 다진검색트리, K진 검색트리
그래프 - 프로그램이 이해하려면 행렬, 리스트, 배열 등으로 표현
도널드 커누스Donald Knuth를 이야기하고 절차적 알고리즘, 재귀알고리즘 등을 이야기하는데, 읽을 때는 살짝 이해되다가도 지금 보니, 이해한 게 맞는지 모르겠다.
문제 해결 알고리즘을 찾는 과정에서 재귀적 구조물을 발견함으로써 간명하고 우아한 해법을 얻는 경우가 많다. 이 작업의 핵심은 문제를 보는 하나의 관점을 착상하고 이 관점과 일치하는 작은 문제를 찾는 것이다.
스티븐 레비의 <<인공생명Artificial Life>>에 대해t서 언급하고 있다. (*찾아보니 없어서 AI에게 물어보니, 번역된 게 있다고 알려준다. 오! 몇 달 사이에 엄청 발전했구나.)
세상이 너무 빠르게 변하고 있어서 나이 든다는 걸 실감하기 어려울 지경이다. 이젠 좀 쉬고 싶은데... 거참. 그리고 이 책은 얇고 단단하니, 읽기를 권한다. 초심자라도 반나절이면 다 읽을 수 있을 것이다.