[알고리즘] 불확실한 상황을 현명하게 사용하는 코드

 

이번글은 학교 알고리즘 수업 시간에 Randomized algorithm을 배우면서 느낀 점을 남기는 글입니다.

어떤 알고리즘을 설명한다기보다는, 제가 느낀 점을 남겨보는 글입니다.

 

1. 불확실한 상황을 이용해 볼 수 없을까?

우리가 코드를 작성할 때 모든 상황이 확실하게 결정된 상황에서만 진행하는 경우는 거의 없다, 어쩌면 이는 코드뿐만 아니라 대부분의 사람들이 하루를 살아가는 자연스러운 방법(?) 중 하나일지도 모른다.

 

물론 우리는 계획이라는 것을 만든다. 해당 계획을 통하여 시간이 얼마나 걸릴지 예측할 수도 있고, 얼마나 많은 리소스가 필요한지 또한 측정할 수 있다. 하지만 이는 어느 정도의 사전 정보가 있다는 가정 하에 가능할 것이며, 당장 첫 시도를 해야 하거나, 상황 자체가 너무나 불확실하다면 맨몸으로 시도해 보는 수밖에 없을 것 같다.

 

이러한 불확실한 상황에서 뭐를 이용해 볼 수 있을까? 모든 것이 불확실하다면 이용할 것이 있긴 할까?

 

하나 있다!, 바로 상황이 불확실하다는 그 사실 자체이다!

 

1-1) 확실함이 주는 코드의 한계 지점

확실한 코드들은 어느 정도 아키텍처가 정해져 있거나, 기존에 모범 사례를 기반으로 작성되며, 또한 이러한 확실성을 뒷받침해 주는 시간복잡도, 공간복잡도에 대한 식이 이미 계산되어 있을 것이다.

 

나 또한 모범사례나 기존에 사용되고 안정적인 방식을 학습하고 적용해 보는 개발자에 가까웠다.

스스로도 이게 가능한 최선이라 믿고 한 발자국 더 나아갈 생각을 안 했던 것은 아닐까?

 

알고리즘 통하여 비유해 보자.

 

예를 들어 오름차순으로 정렬되어 있는 LinkedList에서 특정값 X를 찾아야 한다고 해보자.

우리는 해당 값을 찾는데 O(N)이 걸린다는 사실은 조금만 컴퓨터를 공부해 보았다면 알 수 있는 사실이다.

나는 보통 이렇게 모든 경우 확실한 결론을 내려주는, 결정론 적인 알고리즘을 배우고 사용해 왔다.

 

그래서일까? 어떤 문제를 풀더라도 "지금의 상황하에서 다음상황을 선택하고, 이를 기반으로 해결" 하는 방식의 나의 기본 로직이었다.

하지만 이러한 알고리즘들은 명확하게 "한계점" 이하의 시간복잡도를 제공해주지 못한다.

 

위 LinkedList에서 내가 원하는 X값 찾는데 O(N), 정렬을 하는데 O(NlogN) 미만으로는 내려갈 수 없다는 등.... 분명한 "한계점"이 존재한다.

 

1-2) 불확실성 이용하기

용어 하나 먼저 알아보자!

Las Vegase
Always Correct, but Running time probabilistic

 

일명 "Las Vegase"라는 종류의 알고리즘이다. 이러한 알고리즘들은 불확실성을 사용하여 항상 정확한 답을 주지만, 실행시간이 왔다 갔다 한다. (반대되는 종류로 Monte Carlo라는 종류의 알고리즘도 있다)

 

실행시간이 왔다 갔다 해도, 기존의 한계점보다는 더 성능이 좋아지기 때문에 사용되는 방식이다.

이를 위 LinkedList에서 내가 원하는 X값 찾는 문제로 조금 더 알아보자.

 

1-2-1) 아무 곳이나 √n 개만큼 선택하기 

일단 √n개만큼 아무 곳이나 골라준다. 고른 값들 중, x보다 작은 것들 중 가장 큰 놈을 고른다.

그 지점부터 위로 순차 탐색하여 X까지 도달한다.

 

이게 끝이라고?? 이게 성능을 개선시켜 준다고??

√n 개 고른지점이 맨 처음지점이면 어차피 순차 탐색 아닌가???

 

어떻게 보면 진짜 단순 무식한 방법 같지만, 이러한 방식이 성능을 엄청나게 개선시켜 준다.

 

여기서 궁금한 점이 있다. 왜 √n 개만큼 고르는 것일까? 또 시간복잡도는 어떻게 될까?

 

1-2-2) √n 개 선택하는 이유

우선 √n개 즉, K개를 선택했다고 하자.

시간은 O(K + f(n, K)) 만큼 드는데, K는 √n개중 X보다 작으면서 가장 큰 놈을 찾는 시간이며 f(n, K)는 그 가장 큰 놈에서 순차탐색하여 X까지 도달하는 시간이다.

 

▶ f(n, K)을 계산해 보자!

우선 X보다 작으면서 가장 큰 놈이 X로부터 거리 d만큼 떨어져 있다 생각해 보자.

하나를 골랐을 때 초록색 지점에 떨어진 확률은 (N-d)/N이며, 총 K를 뽑으니 K승 해주면 된다.

이는 거리가 d이상일 확률이지, 딱 d일 확률은 아니다.

 

딱 d일 확률은 (d이상일 확률 - d-1 이상일 확률)이다.

 

이를 1부터 N가지 모두 구해보면 다음과 같다. 즉 기댓값을 구한 것이다.

 

근데 위의 식에서 빨간 부분을 잘 보면 거의 적분식이다!! 여기서 적분이??

 

따라서 f(n, K)는 n/(k+1) 정도가 나오며, 해당 k + f(n, K)가 최소가 되려면 두항이 동일할 때 가장 최소가 되어, 대략 √n 이 나오는 것이다. 여기서 왜 √n을 선택하는지 또한 알 수 있는 것 이다.

 

K + f(n,k)가 최소가 되는 경우는, 식을 k + 1 + n/(k+1) - 1이 최소가 되는 경우와 동일한데, 마지막 -1을 무시하고 k + 1 + n/(k+1)만 생각해보면, k + 1 와 n/(k+1) 의 곱이 항상 n으로 일정하며, 이때 가장 작아진다. k + 1 = n/(k+1) 로 두고 식을 풀면 k가 대략 √n이 나온다

즉 시간복잡도가 O(√n)이 된다. 이는 엄청난 단축이라 할 수 있다.

2. 결론 : 불확실한 상황을 현명하게 사용하는 코드의 유용함

어쩌면 나는 매 순간 답이 무조건 있다 믿으며, 즉 확실한 영역에서만 답을 구하려 하며 살아왔던 것이 아닐까?

하루하루 내가 짜온 코드 또한 확실한 상황에서 배워왔던 코드들이 아닐까? 물론 프로젝트 들을 여러 번 하면서 스스로를 불확실한 상황에 던지며 얻어온 경험이 있지만, 그 경험을 살펴보면 항상 확실함을 찾으려 노력해 왔다. 불확실성은 나에게 정신적으로 좋지 못하다 생각하였으며, 사용가치가 없다 생각한 것이 문제였던 것 같다. 지금 돌이켜 보면 내가 성장한 순간 또한 이러한 불확실한 상황을 경험하고 이용하였을 때인 것 같다. 프로그래머란 불확실한 상황에서 해엄쳐 나아갈 수 있는 존재여야 할것 같다.