Hee's Blog

4주간 논산 육군 훈련소를 가게되었다.

한달정도 글을 쓰지 못한다.

아직도 써야할 포스트 목록이 산더미다.

다녀와서 천천히 써야지.

이전 포스트를 이어서 퀵정렬의 pivot을 설정하는 방법에 대해 이야기 하도록 하겠다.

먼저 퀵정렬이 빠른 이유에 대해 알아야 한다.

전제 조건은 랜덤하게 정렬된 배열을 퀵정렬 알고리즘으로 정렬하는 것으로 한다.

퀵정렬의 구동 원리를 자세히 생각해보면 퀵정렬이 빠른 이유를 알 수 있다.

구동원리는 다음과 같다.

1. 피벗을 설정한다.

2. 피벗보다 큰 수는 오른쪽 작은 수는 왼쪽에 배치한다. 

3. 피벗을 기준으로 두개의 배열로 나눈다.

4. 각각의 배열을 1번부터 재귀적으로 반복한다.

만약 위의 방법만으로 정렬이 되는 것을 믿지 못하겠다면 [ 10. QuickSort ] 포스트를 참조하여 직접 따라가면서 컴파일 해보는 것을 추천한다.

힌트를 주자면 위의 단계처럼 두개의 배열로 나누다 보면 언젠가 하나의 배열이 3개 혹은 2개 혹은 1개가 되는데  

상식적으로 생각해보면 3개중 하나의 요소를 기준으로 좌우로 정렬한다면 오름차순으로 정렬될 수 밖에 없다는 것을 생각해보기 바란다.

다시 돌아와서 내가 생각한 퀵정렬이 빠른 가장 큰 이유는 바로 먼 거리 처리 능력 이다.

다음과 같은 두개의 배열을 두 가지 방법으로 정렬한다고 가정하자.

[2,  3,  4,  5,  6,  7,  8,  …  N,  1] => 1과 N, 1과 (N - 1), 1과 (N - 2), 1과 (N - 3), ... 1과 (N - (N - 1)) 비교 후 제자리를 찾음 (총 N - 1번 비교) 

[2,  3,  4,  5,  6,  7,  8,  …  N,  1] => 1과 2를 비교 후 작다면 1앞에 배치 (1번 비교) 

( 극단적인 상황이지만 먼거리 처리 능력을 보여주는 좋은 예 인것 같다. )

정렬 알고리즘의 수행시간을 결정짓는 모든 근원은 비교연산의 횟수와 교환연산의 횟수이다. 

그리고 똑같은 코드를 얼마나 반복하는지이다.

(상식적으로 for문을 아무런 처리 없이 n^2 번 반복시킨다고 해도 그렇게 오랜시간이 걸리지 않는다.)

결국 빠른 알고리즘은 코드를 얼마나 적게 수행하는 지에 따라 결정된다. 

코드를 적게 수행하는 방법은 비교연산을 통해 코드를 스킵하는 것이다.

이 모든 것이 비교를 하는 방법에 따라 결정되며 곧 먼거리를 한번에 이동할 수 있는 알고리즘이냐 아니냐의 문제라고 생각한다.

기존 알고리즘의 문제점

그렇다면 퀵정렬의 먼거리 처리능력이 소용없어지게 된다면 퀵정렬이 느려질까? 

퀵정렬의 먼거리 처리 능력을 없애는 방법은 이미 정렬된 배열을 정렬 시키거나 역순으로 정렬된 배열을 정렬시키는 것이다.

위 두가지의 경우 퀵정렬 역시 순차적으로 모두 비교를 하게 되기 때문이다.

그 이유는 앞서 구현하였던 퀵정렬이 피봇을 선택하는 방법에서 찾을 수 있다. 

무조건 left의 값을 피봇으로 설정 하기 때문에 피봇이 항상 가장 크거나 가장 작은 값이된다.

때문에 모든 요소와 비교를 하며 먼거리 처리능력도 소용이 없게 된다.

실제로 앞선 [ 10. QuickSort ]의 알고리즘으로 역순 배열이나 정렬된 배열을 정렬하면 n^2의 시간이 걸린다.

해결방안

어떻게 하면 퀵정렬이 랜덤인 상황이 아니더라도 빠른속도를 유지 할 수 있을까?

사실 이부분에서 나는 굉장히 많은 시간을 보냈다. 알고리즘을 새로운 방법으로 짜보기도 하는 등 여러가지 시도를 해보았다. 

여러가지 시도를 하면서 중점을 맞춘 내용은 어떤 상황이더라도 Pivot을 기준으로 최대한 동등하게 배열을 나누는 것 이었다.

생각하기까지 매우 오랜시간이 걸렸지만 결과적으로는 매우 간단하게 해결할 수 있었다.

바로 배열의 가운데값을 피봇으로 설정하는 것이다.

물론 실제 가운데 값을 피봇으로 설정한 후 알고리즘을 실행시키면 제대로 정렬되지않을 뿐더러 데이터가 엉망이된다.

그래서 조금만 비껴생각해낸 것이 배열의 가운데 값을 left값과 교환하는 것이다. 그 이후의 방법은 기존알고리즘과 동일하다.

바뀐 코드는 아래와 같다.

이 아래로는 이전의 코드와 동일하다.

핵심적인 부분은 바로 median을 설정하는 부분과 그것을 left(원래의 피벗)과 교환하는 부분이다.

median을 배열의 가운데 요소로 선택하고 이것을 다시 피벗과 교환함으로써 피벗이 가장 큰값이나 작은 값이 아닌 중간값으로 설정된다.

때문에 오름차순이나 내림차순으로 미리 정렬된 배열의 경우에도 동등한 2개의 배열을 만들어 낼수 있으며 

이는 곧 퀵정렬의 강점을 살릴 수 있게 된다는 것이다.

위의 코드를 이용하여 실제로 테스트를 해본 결과는 아래와 같다.

기존의 알고리즘 

요소 수 :           100,000                  100,000,000   

랜덤 배열 :         0.017                        23
역순 배열 :         12.89            너무 오래걸려서 측정 불가
순열 배열 :         13.21             너무 오래걸려서 측정 불가

Median피벗 알고리즘

요소 수 :           100,000                  100,000,000   

랜덤 배열 :         0.017                           23
역순 배열 :         0.0076                      8.98
순열 배열 :         0.0072                      8.46

이전 알고리즘에 비해서 매우 빠른 속도를 보여준다.

자동적 에이전트 (Autonomous Agent)란?

자동으로 움직이며(행동하며) 현재 혹은 미래의 상황을 감지하고 그에 따른 적절한 반응을 보여주는 AI객체라고 생각한다.

AI 프로그래머가 디자인 하기에 따라 무엇을 찾는 다거나 무엇으로 부터 숨는다거나, 집단적인 행동을 한다거나 독자적으로 배회하는 등의 행동을 할 수 있다.

앞으로의 포스트에서 여러가지 행동으로 디자인된 에이전트들의 모습과 구현 방법에 대해 이야기 하겠다.

본 내용은 "실용적 예제로 본 게임 인공지능 프로그램하기"라는 책을 읽은 후 배운 내용을 바탕으로 정리하는 것이다.

Seek - 찾기

가장 먼저 이야기할 행동은 목표 타겟을 찾는 행동인 Seek이다.

결과를 먼저 보자면 위의 그림처럼 진행하던 방향에서 목표지점을 향해 점차적으로 방향을 틀어 이동하는 모습을 볼 수 있다.

원리를 설명하기에 앞서 조종행동에서 중요하게 사용되는 벡터에 대해 설명하겠다.

조종행동에서 빠질 수 없는 것이 바로 벡터(Vector)이다. 

벡터는 스칼라와 동일하게 ( X, Y )으로 표현하지만 의미는 매우 다르다. 

스칼라 포인트 ( 3 , 3 )의 경우 ( 0, 0 )을 기준으로 하는 좌표계에서 아래와 같은 점으로 표시된다.

하지만 벡터의 경우 ( 0, 0 )을 기준으로 ( 3, 3 )을 표현하면 아래와 같다.

이렇게 화살표로 표현되는 이유는 스칼라는 단순히 좌표 즉, 위치에 대한 정보만 가지고 있지만 벡터의 경우 위치와 방향의 정보를 가지고 있기 때문이다.

때문에 같은 ( 3, 3 )의 정보라도 벡터값인지 스칼라 값인지에 따라 의미하는 것은 다를 수 있다.

간단하게나마 벡터에 대한 설명을 했고 본격적으로 찾기 조종행동에 대해 알아 보겠다.

원리는 다음의 그림과 같다.

첫번째 그림에서 보이듯이 에이전트는 C의 속도(방향)로 이동 중 이었다. 그러던 중 Goal을 찾게 되었고 목표지점으로 설정한 후 도달하길 원하고 있다.

Goal에 도달하기 위한 원하는 속도(T)는 다음의 공식으로 구할 수 있다.

G(Goal) - 현재위치(P) = 원하는 속도(T)  => T = G - P

G라는 포인트, 스칼라값에서 P라는 포인트, 스칼라값을 빼면 바로 T라는 벡터를 얻을 수 있다. 스칼라 - 스칼라 = 벡터이기 때문이다.

원하는 속도는 구하였다. 그렇다면 어떻게 C에서 T로 속도를 바꿀 수 있을까?

간단하게는 그냥 현재 P의 속도를 T로 바꿔만 주면 해결될 것이다.

하지만 그렇게 하면 Goal을 향해서 직선으로 이동할 뿐 내가 원하는 느낌인 커브를 도는것을 볼 수 없다.

답은 두번째 그림에서 찾을 수 있다. 

바로 조종힘인 D를 구하고 그것을 현재 속도에 점차적으로 더해주면 된다.

조정힘을 구하는 공식은 다음과 같다.

원하는 속도(T) - 현재속도(C) = 조종힘(D)   =>  D = T - C

이제 계산되어 나온 D를 현재 속도에 더해주면 에이전트가 점차적으로 방향을 트는 것을 확인 할 수있다.

코드

+ 후에 동영상을 올릴 수 있으면 추가하겠다.