[Algorithm]알고리즘 시간 복잡도 계산하기

요새 도서관에서 찾아서 읽고 있는 책이 있다. 바로 이 책이다. '알고리즘 도감' 알고리즘 과목을 다음학기에 배운다는 말을 듣고 미리 공부해보고 싶어서 찾아보게 된 책이었다. 사실, 이중에서 절반은 이미 배웠다고 할 수는 있긴 한데. 내가 이걸 완벽하게 이해했는지는 미지수이다. 이 책은 그래도 쉬운 설명과 그림들이 많은 덕분에 정확하게 이해할 수 있을 것 같아 이 책으로 공부해보려고 한다. 

 

이 책과 더불어 요즘 '나는 프로그래머다'라는 책을 시간날때마다 천천히 읽고 있다. 

후에 이 책에 대해서도 따로 리뷰를 할 예정이지만 정말이지 동기 부여가 되고 유용한 책이다. 그 중에서 '알고리즘이 프로그래머에게 꼭 필요한가요?'라는 대답에 글쓴이는 이렇게 말했다.

 

알고리즘은 꼭 필요합니다. 필요하지 않다는 이야기를 기대하신건지는 모르겠지만, 어쩌면 그렇게 알고리즘이 꼭 필요하다고 물어보는 것 자체가 컴퓨터에 대한 열정이 부족한게 아닐까요. 알고리즘은 프로그래머에게 일종의 기동력을 주기 위함입니다. 어떤 언어이던지 알고리즘 자체가 잘 기본이 되어있다면 금방 배우고 쓸 수 있는 능력을 갖출 수 있습니다.

 

대충 이러한 내용이었다. 여태 꼭 많이 중요한가, 라는 물음을 가끔씩 생각했던 나 자신에게 조금 반성한다.

나는 유연하고 창의적인 프로그래머가 되고싶다. 그렇기 때문에 알고리즘은 필수라고 생각하고, 정말 참된 기본기의 문제해결능력을 길러보려고 한다.

 

자, 이제 서론은 됐고. 오늘은 알고리즘의 기본에 대해서 알아보려고 한다.

 

우선, 앞으로 배워볼 알고리즘은 탐색, 정렬 이렇게 크게 두 가지가 있다. 

 

[탐색]

- 너비 우선 탐색

- 깊이 우선 탐색

- 벨만-포드 알고리즘

- 다익스트라 알고리즘

-  A*

 

[정렬]

- 버블정렬

- 선택정렬

- 삽입정렬

- 힙정렬

- 병합정렬

 

사실 반 이상은 들어봤거나 수업시간에 배운 내용이다. 하지만 책을 읽으면서 느끼고 있다. 내가 수업시간에 왜 배워야 했는지도 모르는 것들을 다시 보니 왜 배워야되겠는지 알겠고, 이것을 어떻게 활용해야 할지 보이기 시작한다.

 

알고리즘의 본질적인 뜻은. 계산이나 작업을 하기 위한 순서이다.

그래서 알고리즘 프로그램은 사람이 이해할 수 있도록 먼저 작성해야 한다.

 

오늘은 알고리즘 시간 복잡도를 계산하는 방법을 '선택정렬'에 예시를 들어 설명하려고 한다.

우선 정렬이라는 것은, 정수를 순서대로 나열하는 알고리즘이다. 어떤 입력값에서도 대응할 수 있는 일반적인 방법을 기술해야 하는 것이 알고리즘의 목표이다.

 

선택 정렬은, n개의 숫자 중에서 가장 작은 수를 찾아서 가장 왼쪽에 배치한다. 이 동작 하나가 1라운드라고 하자.

그리고 다음 해야할 동작은, 제일 작은 한 숫자를 찾아서 맨 왼쪽에 옮겼으니 다음은 n-1개의 숫자들 중에서 제일 작은 숫자를 찾아 왼쪽에 옮긴다. 그다음은 n-2, n-3... 계속 이렇게 반복하게 된다.

 

그러면 일반적인 방법은 이렇게 된다.

 

1. 현재 k라운드 일 때

2. 정렬되는 숫자는 왼쪽에서 k번째에 있을 것이고

3. 정렬되는 뒤의 숫자는 k개일 것이다.

 

이러한 일반화가 가능하다.

 

꼭 선택정렬만 써야하는 것이 아니다. 상황에 따라서 효율적인 알고리즘을 골라서 쓰면 된다.

간단히 예시를 든다면 이 책에서 예시를 든 것은 50개의 숫자를 정렬할 때 걸리는 시간에 대해서 말했다. 50개의 숫자를 정렬한다고 할 때, 하나씩 비교해서 정렬하는 완전 탐색 정렬을 사용한다고 하면 자칫하면 우주가 시작하고 지금까지 못 끝내는 상황이 발생하게 된다. 그러나 선택정렬을 사용하게 될 경우 n(n+I)/2 보다는 크고, n의 제곱보다는 작은 시간이 걸리게 된다. 이때 n제곱을 최악의 시간이라고 한다. 

 

그렇다면 이러한 알고리즘은 어떻게 설계해야 하는걸까?

 

컴퓨터는 기본적인 명령을 수행할줄 알지만, 알고리즘은 기본적인 것이 아니라 그것들을 조합해서 복잡한 명령을 만들어내어 처리하는 기술이다. 그렇기 때문에 효율적으로 설계하지 않으면 케이스별로 시간이 많이 걸리게 되는 알고리즘이 될 수도 있으니 유의해야한다. 

 

알고리즘을 선택할 때 가장 중요한 것은 계산시간이다. 계산 시간은 입력된 숫자의 크기에 따라서도 차이가 상이하다.

어느정도 시간차이가 나는지, 얼마만큼이 나는지 이 부분에 대해서 고려를 해야한다.

 

그렇다면 계산 시간을 구하는 방법은 무엇을까?

 

'스탭수'라는 것을 활용하면 된다. 스탭이란, 계산의 기본단위인데, 이것으로 계산을 종료하기까지 기본 단위를 몇 회 실행하였는가로 계산 시간을 측정하게 된다.

 

예를 들어 선택정렬의 계산 시간을 이러한 방법으로 측정해보자.

선택정렬은 다음과 같은 방법으로 계산이 진행된다.

 

1. 수열에서 최솟값을 찾는다.

2. 최솟값을 수열의 가장 왼쪽 숫자와 교환하고 정렬을 끝낸다. 다시 1로 돌아간다.

 

이때 우리는 이 정렬로 n개의 숫자를 확인해야 한다.

1의 과정에서, 하나의 숫자를 확인하는 것을 하나의 기본단위로 생각했을 때, 이 기본단위를 Tc라고 하자. 그러면 n개의 숫자를 확인하는데 걸리는 시간은 Tc*n이다.

2의 과정에서는 두개의 숫자를 교환하는 동작을 기본단위로 생각한다. 이 기본단위를 Ts라고 하자. 하지만 이 동작은 단순히 교환하는 동작 하나이므로 Ts 시간이 걸리게 된다.

그럼 한 라운드에 있어서 식은 Tc*n+Ts가 되게 된다. 그러면 총 계산시간은 아래와 같게 된다.

 

(n*Tc+Ts)+((n-1)*Tc+Ts)+((n-2)*Tc+Ts)...(2*Tc+Ts)+(1*Tc+Ts)

이 식을 등차수열 공식 n(n+I)/2로 계산하면 첫항인 n=(n*Tc+Ts)와 마지막 항인 I=(1*Tc+Ts)를 계산하면 식이

=1/2Tcn(n+1)+Tsn이 나오고 이 식을 간소화 한다면 1/2Tcn제곱+(1/2Tc+Ts)n이 되게 된다.

 

이 1/2Tcn제곱+(1/2Tc+Ts)n 식에서 계산시간을 표현하기에는 다소 복잡하다.

그래서 우리는 중요한 부분만 빼고 표현을 하겠다, 라는 뜻으로 O(Big-o)를 쓰게 된다. 이것을 사용해서 선택정렬의 시간 복잡도를 표현하면 최종적으로 시간 계산에 제일 영향을 미치는 n제곱을 상요하여, O(n제곱)으로 표현하게 된다.

 

여기까지가 알고리즘의 시간 복잡도를 계산하는 방법이었다. 

 

혹시 등차수열이나 이런 수학적 지식이 부족하다면 아래의 링크를 참고해서 이해를 했으면 좋겠다. 

나도 그렇게 수학을 잘하지는 않는 터라 이러한 곳에 쓰이는 수학들은 다시 찾아서 복습해가면서 이해한다. 

이해하면 알아가는 재미가 참 쏠쏠하다. 다른 사람들도 재밌게 같이 공부했으면 한다.

 

https://bhsmath.tistory.com/17