[코딩 테스트 합격자 되기 C++ 편] 03 알고리즘의 효율 분석

03-1 시간 복잡도란?

"시간 복잡도(time complexity)란, 알고리즘의 성능을 나타내는 지표로, 입력 크기에 따른 연산 횟수를 의미합니다. 시간 복잡도는 낮으면 낮을수록 좋습니다."

어떤 문제를 해결할 수 있는 알고리즘 A,B,C 세 가지가 있다면 이 중 시간 복잡도가 가장 낮은 알고리즘이 A라면 A를 사용하는게 좋다.

1차원 배열 검색하기

1차원 배열에 값이 있을 때, 특정 값을 찾고자 앞에서부터 순서대로 검색한다 가정한다.

연산 횟수가 가장 적은 경우

검색 시작 위치에 찾을 값이 바로 있는 경우.

연산 횟수가 가장 많은 경우

찾을 값이 아예 배열에 없거나 마지막 위치에 있는 경우. 연산 횟수가 최대가 된다.

 

알고리즘 수행 시간을 측정하는 방법

수행 시간을 측정하는 방법으로는 아래의 두 가지 방법이 존재한다.

절대 시간을 측정하는 방법

말 그대로 프로그램이 수행된 시간을 시작부터 끝까지 측정하면 된다.

시간 복잡도를 측정하는 방법

연산 횟수와 관련이 있다. 시간 복잡도는 알고리즘이 시작한 순간부터 결괏값이 나올 때까지의 연산 횟수를 나타낸다.

시간 복잡도를 측정한 결과는 다음과 같이 최선(Best), 보통(Normal), 최악(Worst)의 경우로 나눈다.

 

첫째, 최악의 경우를 고려해야 합니다.

코딩 테스트에서는 아주 다양한 조합으로 입력값을 넣어 코드를 평가한다. 그 중에는 최악의 입력값도 있게 된다. 그렇기에 우리는 최악의 경우를 기준으로 시간 복잡도를 분석해야 한다.

 

둘째, 알고리즘 성능은 정확한 연산 횟수가 아닌 추이를 활용합니다.

우리가 궁금한 것은 내 알고리즘이 제한 시간 안에 수행될 수 있을지 정도를 파악하면 충분하다.

따라서, 연산 횟수의 추이를 활용해서 성능을 측정한다.

 

ex) 친구와 10시에 만나기로 약속을 했다. 친구가 언제 도착하냐 물었을 때, 시/분/초를 고려해서 대답하지 않고 우리는 대부분 몇 분 정도로 근사치에 가깝게 대답을 한다.

 

이와 같이 코딩 테스트에서도 알고리즘의 성능을 측정할 때, 연산 횟수의 추이만 알고 있어도 성능을 충분히 가늠할 수 있다.

 

이러한 방식으로 충분히 큰 입력값 N에 따른 연산 횟수의 추이를 활용해서 시간 복잡도를 표현하는 방법을 점근적 표기법이라고 한다.

 

최악의 경우 시간 복잡도를 표현하는 빅오 표기법

최악의 경우에 대하여 시간 복잡도를 표현하고자 한다면 상한선을 활용하면 된다.

상한선을 활용한 점근적 표기법을 빅오 표기법(big-O notation)이라고 한다.

수식	빅오 표기	설명
3x^2 + 5x + 6	O(x^2)	최고차항인 x^2만 남는다.
x + logx	O(x)	증가폭이 더 낮은 로그함수는 사라지고 다항함수만 남는다.
2^x + 10x^5 + 5x^2	O(2^x)	지수함수의 증가폭이 다항함수보다 크므로 지수함수만 남는다.
5x^2 - 6x	O(x^2)	최고차항인 x^2만 남는다.

 

그나저나 왜 이렇게 표기할까?

입력으로 들어오는 값이 특정 시점부터는 해당 최고 차항의 값만이 유의미한 증가폭을 지니게 되기 때문에 빅오 표기에서 최고차항을 가진 값만이 남는다.

 

빅오 표기법을 쉽게 쓸 때는 왜 최고차항만 남기고 계수를 지울까?

우리가 구하려는 것은 상한의 정확한 값이 아니라 '이 정도 될 것이다'를 파악하는 추이이기 때문이다.

즉, 우리는 상한을 구한다. 단, '최소한의 상한'을 구해야하는데. 이는 다음의 예시를 통해 알 수 있다.

• 아직 중학교에 입학하기 전입니다.
• 아직 칠순 장치를 하지 않았습니다.

초등학교 3학년 학생을 대상으로 한 문장이다.

둘 다 학생의 나이에 대한 상한을 잡지만, 첫 번째 문장이 학생의 나이를 가늠하는데 더 좋은 정보이다.

이와 같이 상한을 구하되, '최소한의 상한'을 구해야 한다.

이를 적용하면 최고차항만 남기고 계수는 지우게 되는 것이다.

 

시간 복잡도를 코딩 테스트에 활용하는 방법

코딩 테스트 문제에는 제한 시간이 있으므로 문제를 분석한 후에 빅오 표기법을 활용해서 해당 알고리즘을 적용했을 때, 제한 시간 내에 출력값이 나올 수 있을지 확인해 볼 수 있다.

• 코딩테스트는 출제자가 의도한 로직을 구현했다면 대부분의 코드를 정답 처리할 수 있도록 채점 시간을 충분히 여유있게 지정한다. 따라서, 연산 횟수는 1,000 ~ 3,000 만 정도로 고려해서 시간 복잡도를 생각하면 된다.
  • 예를 들어, 제한 시간이 1초라면 문제는 연산 횟수가 3,000만이 넘어가는 알고리즘을 사용하면 안 된다.

시간 복잡도	최대 연산 횟수	예시
O(N!)	10	순열
O(2^N)	20 ~ 25	부분 집합의 수
O(N^3)	200 ~ 300	3차원 배열 순회
O(N^2)	3,000 ~ 5,000	N x N 배열 순회
O(NlogN)	100만	퀵 정렬의 평균 시간복잡도
O(N)	1,000 ~ 2,000만	크기가 N인 배열 순회
O(logN)	10억	이진 탐색
O(1)	초당 최대 연산 제한만큼	배열에 대한 임의 접근, 혹은 수학 공식

03-2 시간 복잡도 계산해보기

별 찍기 문제

숫자 N을 입력 받으면 N번째 줄까지 별을 1개부터 N개까지 늘려가며 출력하는 문제

푸는 과정

1. 연산 횟수를 구한다.
2. 1번째 줄은 1번, 2번째 줄은 2번, N번째 줄은 N번 연산
3. 최종적으로 구하는 연산 횟수 f(N)은 다음과 같다.

 

박테리아 수명 문제

초기 박테리아 세포 개수가 N일 때, 해마다 세포 개수가 이전 세포 개수의 반으로 준다면 언제 모든 박테리아가 죽을지 계산해야 한다. 입출력의 예는 아래의 표와 같다.

N = 16

5

푸는 과정

초기값	1년	2년	3년	4년	5년
16	8	4	2	1	0

현재 박테리아 수가 N이면 1년 뒤 박테리아 수는 1/2 * N 이라고 할 수 있다. Y년 후의 박테리아 수는 (1/2)^Y * N이다.

1. 박테리아의 소멸 시기는 해당 값이 1보다 작아지는 최초의 때이므로 수식으로 표현하면 다음과 같다.
2. (1/2)^Y * N <= 1
3. 양 변을 N으로 나누면 (1 / 2) * Y <= 1 / N이 된다.
4. 양변에 역수를 취하고 부등호를 바꾸면 2 * Y >= N이다
5. 양변에 최종적으로 로그를 취하면 Y >= logN이다.

최종적으로 이와 같은 알고리즘은 O(logN)의 시간 복잡도를 가진다는 것을 알 수 있다.