[Algorithm] 알고리즘은 왜 공부해야 하는가? (시간복잡도, 코딩테스트 준비)
오늘은 알고리즘에 대하여 글을 써보려고 한다. 알고리즘은 무엇인가? 알고리즘은 왜 공부해야 하는가?라는 질문에 대답이 될 것 같다. 나는 사실 대학 시절 알고리즘 개론 들을 때는 별 흥미가 없다가, 취업준비 및 자격증 준비를 위해 알고리즘 공부를 하며 조금 흥미가 붙게 되었다.
0. 알고리즘이란 무엇인가요?
'문제를 푸는 방법'이라고 대답하면 될 것 같다. 예를 들어서 1부터 100까지의 자연수를 모두 더한 값을 구하는 문제가 있을 때, ① 숫자를 하나하나 더하는 방법, ② 공식을 이용해 아래 수식을 계산하는 방법으로 풀 수 있을 것이다. ①, ② 각각이 하나의 알고리즘이라고 말할 수 있고, 어떤 알고리즘을 사용하느냐에 따라 계산에 걸리는 시간, 사용하는 데이터 공간 등 효율이 달라지기 때문에 문제에 따라 최적의 알고리즘을 사용하는 것이 중요하다.
특히, 프로그램을 개발할 때는 처리 속도가 가장 중요한 요소 중 하나이기 때문에, 문제 해결에 걸리는 처리 시간을 최대한 짧게 하는 것이 중요하다. (코딩 테스트 문제 풀 때 그렇다.) 그러면 아래와 같은 질문을 할 수 있을 것이다.
1. 각 알고리즘 별로 시간이 얼마나 걸리는지는 어떻게 측정(표기) 하나요?
여기서 시간 복잡도(영어로는 Time Complexity)라는 개념이 등장한다. 시간 복잡도는 알고리즘 별로 입력값에 따라 시간이 얼마나 걸리는지를 알려주는 척도이다. 예시가 있어야 설명도 쉽고 이해가 빠르기 때문에 위에 썼던 문제를 확장해서 예를 들어보겠다.
Q. 임의의 자연수 N이 주어졌을 때, 1부터 N까지 자연수의 합을 구하라.
그리고 문제에 대한 해답으로 아래와 같은 두 가지 풀이법(알고리즘)을 생각해냈다.
① 1부터 숫자를 1씩 증가시켜 N까지 모든 숫자를 더한다.
# 1. 1부터 N까지 모두 더하기
answer = 0
for i in [1, 2, ... , N] {
answer = answer + i
}
② 첫째항이 1이고 공차가 1인 등차수열의 합 공식을 이용한다.
# 2. 등차수열 공식 이용하기
answer = N * (N + 1) / 2
위 두 가지 알고리즘을 실행시켰을 때, 연산이 몇 번 일어나는지 살펴보자.
[알고리즘 ①]
- 3번 줄에서 answer에 0을 넣어주는 연산 1번
- 7번 줄에서 answer과 i를 더하는 연산 1번과 그 값을 answer에 넣어주는 연산 1번으로 총 2번. 그리고 이를 1부터 N까지 총 N번 실행하므로 2N번
※ 결과적으로 (1)과 (2)를 합쳐 총 2N + 1번 연산이 일어난다.
[알고리즘 ②]
- 3번 줄에서 (N + 1) 연산 1번, 이를 N과 곱하는 연산 1번, 그 결과를 2로 나누는 연산 1번으로 총 3번
※ 결과적으로 3번 연산이 일어난다.
이 시점에서 시간 복잡도의 표기법을 배워보자. 빅오 표기법(Big-O notation)이라는 것을 사용하는데, 아래와 같이 앞에 O를 쓰고 뒤에 괄호 안에 입력값에 따른 척도를 적는 방식으로 작성한다.
그러면 위에 사용한 두 가지 알고리즘 중 1번 알고리즘의 시간 복잡도는, 총 연산량이 2N + 1번이었으므로, O(2N + 1)로 적으면 정답일까?
반은 정답이다. 보통 개발자들이 알고리즘의 시간 복잡도를 봤을 때 알고 싶은 정보는, 세세한 연산량이 아니라 대략적으로 어느 정도 수준으로 연산량이 필요한지이다.(또, 구현 방식에 따라 세세한 연산량이 달라질 수도 있다.) 그렇기 때문에 가장 높은 차수의 항을 제외하고는 다 제거하고, 가장 높은 차수 항에서 상수 곱 또한 지워준다. 즉, 1번 알고리즘의 시간 복잡도는 O(2N + 1)라고 써도 되지만, 가장 높은 차수인 2N을 제외한 1은 제거하고, 2N에서 상수곱인 2를 제거해 O(N)으로 적는 것이 일반적이다.
그렇다면 2번 알고리즘의 시간 복잡도는 어떻게 표기해야 할까? 총 연산량이 3이므로 O(3)인데, 가장 높은 차수가 3이고, 이는 3 * 1로 상수 3이 곱해진 것으로 볼 수 있기 때문에 시간 복잡도는 O(1)이 된다.
시간 복잡도를 읽을 때도 마찬가지이다. 적혀있는 걸 보고, '아, 저 정도에 비례한 연산량이 필요하겠구나!'라고 생각하면 된다.
Big-O notation을 아주 간단하게 설명했는데, 수학적으로 더 깊게 들어갈 수도 있지만 알고리즘을 공부하는 수준에서는 이 정도만 알아도 충분하다고 생각되어 더 자세한 내용은 담지 않았다. 또, 시간 복잡도와 비슷한 개념으로 공간 복잡도라는 개념 또한 존재하는데, 알고리즘 문제를 풀어본 경험상 크게 고려할 대상이 아니었기 때문에 내용을 담지 않았다.
2. 그래서 우리는 알고리즘을 왜 알아야 하나요?
사실 몰라도 크게 무리는 없다고 생각한다. 본인이 Library를 개발하는 것이 아니라면 말이다. 실제로 개발하며 기본적인 기능, 또는 데이터 구조가 필요할 때(정렬 기능이라던가 priority queue라던가) 보통 만들어져 있는 것을 가져와서 쓰지, 직접 만들어서 쓰는 경우는 드물기 때문이다.
그렇지만 알고리즘을 알고 있는 사람과, 모르는 사람이 같은 기능을 가져와서 사용하더라도 생각의 차이는 있을 것이다.
- 개발자 A : 정렬 기능이 구현되어있으니 가져와서 써야겠다. 표준 라이브러리에 있는 기능이니까 속도 빠르게 알아서 잘 만들어놨겠지?
- 개발자 B : 정렬 기능이 구현되어있으니 가져와서 써야겠다. C++의 표준 라이브러리에서 제공하는 정렬 함수는 Quick Sort Algorithm을 기반으로 만들어서 시간 복잡도가 O(NlogN)이니, 다른 Sorting Algorithm에 비해 속도가 굉장히 빠르겠구나!
만약 본인이 Library를 개발하는 개발자라면 당연히 Algorithm 전문가가 되어야 할 것이고, 그렇지 않은 개발자더라도 위의 두 경우에서 개발자 B처럼 생각할 수 있는 것이 더 개발에 도움 될 것이다. (적어도 나는 개발자 A보다는 개발자 B가 되고 싶다.)
그렇지만 이 글을 보는 대부분의 사람들은 코딩 테스트를 준비하기 위해 알고리즘을 공부하는 사람들일 것이라고 생각한다. (나도 그렇다.) 코딩 테스트를 준비하는 경우라면 얘기가 좀 달라지는데, 시험을 준비하기 위해서는 문제 유형별 알고리즘을 정확히 알고 있어야 한다. 알고리즘의 아이디어, 구현법, 시간 복잡도 등을 정확하게 파악하고 직접 문제를 풀어보며 코드를 본인 손으로 적어보는 것이 중요하다는 얘기를 하고싶다.사실 이 얘기가 하고 싶어서 이번 포스팅 시작했다
이번 포스팅에서는 알고리즘에 대한 기본적인 개념을 담아보았다. 사실 회사에서 반강제적으로 알고리즘 자격시험(코딩 테스트)을 보라고 해서 알고리즘 공부를 정말 오랜만에 다시 하게 되었는데, 운이 좋게도 비교적 금방 통과했고 또 흥미가 생겨서 머릿속에 있는 내용을 조금 정리해봤다. 다음 포스팅으로는 코딩 테스트 준비하는 방법이나 유명한 알고리즘에 대한 내용, 또는 문제 풀이와 같은 내용을 담아볼 수 있을 것 같다.