모두의 알고리즘 : MISSION 3(유한성/정지성/조합적폭발/조합적확산)

모두의 알고리즘 with 자바스크립트에 담긴 내용을 기초로 하여 적는 글.

<모두의 알고리즘  with 자바스크립트 : MISSION 3>

알고리즘이 만족해야 하는 조건 두 번째 : 유한성, 정지성 그리고 알아두어야 할 조합적 확산
며칠 전 친구들이랑 존맛탱 곱창집에 갔다. 우리는 만남의 8할을 그곳에서 가지는데, 이를 알고리즘으로 표현하자면 다음과 같다.

1. 웨이팅 - 입장 및 주문 2. 육개장 후룹 마시기 3. 곱창에 소주 들이켜기 4. 적당히 먹었으면 볶음밥 볶기 5. 계산 및 해산

하지만 11월 26일, 4. 적당히 먹었으면 볶음밥 볶기 이후 5. 계산 및 해산 과정을 실행하지 않고 3. 곱창에 소주 들이켜기 를 재진행했다. 적당히 먹지 못했기 때문이다. 하지만 적당히라는 것은 정해진 기준이 없다. 이렇듯 적당히 라는 단어가 제공하는 판단 기준이 모호하기 때문에 곱창 - 볶음밥 과정이 계속 반복되고 만다.
그렇다면 이건 어떨까? 바로 '적당히 먹고 해산해야하는 기준'인 정지 판정 알고리즘을 만들어보는 것이다. 예를 들면 사장님의 퇴근시간 같은 것 말이다. 사장님도 사람인데 얼른 댁으로 돌아가서 쉬고 싶으실 것 아닌가! 이야기만 들었을 때는 그럴듯해 보이지만 이것 또한 알고리즘이 될 수 없다.
가령 우리가 곱창집에서 곱창 알고리즘을 열심히 실행하고 있을 때, 사장님의 퇴근시간이라는 정지 판정 알고리즘을 거친다고 전제해보자. 슬프게도 우리는 사장님의 퇴근 시간 때문에 하루 종일 곱창을 먹을 수 없을 것이다. 하지만! 사장님이 직접 곱창 알고리즘을 실행한다면? 그렇다! 정지를 판정하는 알고리즘이 실행 알고리즘과 같으면 판정이 불가능한 상태가 된다. 그러므로 정지 판정 알고리즘도 존재할 수 없다.

하지만 우리의 곱창 알고리즘은 아무리 좋게 포장하려고 노력해도 결국 말도 안되는 소리에 불과하다. 알고리즘에 있어서 '실행시간'이라는 것도 굉장히 중요한 요소이기 때문이다. 기상청에서 금주 날씨 정보 알고리즘을 실행하는데 한 달이나 걸리면 아무런 쓸모가 없는 것처럼 알고리즘이 거치는 스텝의 개수가 지나치게 많거나 실행시간이 너무 오래 걸린다면 실질적인 도움을 받을 수 없다. 이러한 스텝의 개수는 계산량이라고 통칭되고, 계산량은 시간 계산량과 공간 계산량으로 나뉜다. 시간 계산량은 말 그대로 실행시간, 공간 계산량은 얼마만큼의 메모리가 필요한지를 묻는 것이다. 대게 '계산량'은 시간 계산량을 의미하는데 환경에 따라 같은 알고리즘이어도 성능이 좋은 컴퓨터는 10초 만에 해결을 낼 수 있지만 그렇지 않은 경우도 있기 때문에 스텝의 개수를 계산한다. 스텝은 바뀌는 수가 아니기 때문이다.
추가적인 개념으로 말도 안되게 많은 연산을 해야 하는 문제에서 일어나는 조합적 폭발(Combinatorial Explosion)이 있다. 저자가 일본인이라 이렇게 번역된 건지 책에는 조합적 확산이라고 나와있다. 조합적 확산이라고 검색해도 관련 글 하나 안 나오길래 가져와 봤다.

n의 계승을 취한다고 가정해보자. 그럼 1! = 1, 2! = 2, 3! = 6, 4! = 24. 그러나 상대적으로 작은 n에 대해서도 매우 큰 수에 빠르게 도달한다 . 예를 들어 100! ≈  9.33262154×10157 는 너무 커서 대부분의 계산기에 표시할 수 없으며, 우주에서 추정되는 기본 입자 수보다 훨씬 크다. 출처 : wikipedia [Combinatorial explosion]

따라서 이런 조합적 폭발이 일어나는 문제에는 첫 번째 글에서 설명한 유전 알고리즘처럼 완벽한 답이 도출되지 않더라도 다른 알고리즘으로 해결해야만 한다.