알고리즘과 시간 복잡도

알고리즘

알고리즘은 문제를 해결하기 위한 절차 또는 방법을 의미합니다.

이해를 돕기 위해 1부터 100까지의 숫자 카드 중 출제자가 생각한 숫자를 맞추는 게임을 한다고 해봅시다.

이 게임은 정답이 아닐 경우 더 큰지 또는 더 작은지 알려주는 규칙을 가지고 있습니다.

이 때 1에서 시작해서 100까지 순서대로 정답을 맞추는 방법도 있고

50에서 시작해서 더 큰지, 더 작은지 확인 후 반 씩 추려나가는 방법도 있습니다.

이때 위 두 방법 모두 숫자 맞추기 게임에서 정답을 찾기 위한 알고리즘으로 볼 수 있습니다. 이 외에도 100부터 역순으로 말하기, 짝수 다 부르고 홀수 부르기 등 전부 나열할 수 없을 만큼 많은 알고리즘이 존재할 것이라는 것을 예상할 수 있습니다.

어떤 알고리즘을 사용해야할까?

이제 알고리즘이라는 게 뭔지는 알 것 같습니다. 그런데 많은 알고리즘 중에 어떤 알고리즘을 사용할지 어떻게 결정할까요? 여기서 시간 복잡도라는 개념이 등장합니다.

시간 복잡도

시간 복잡도란 입력(데이터의 크기)에 따른 연산 수행 시간(알고리즘으로 문제를 해결하는 데 걸리는 시간)의 변화를 일반화하여 나타낸 것으로 주로 bigO 표기법을 사용해서 나타냅니다.

지금은 O(1), O(n), O(log n), O(n^2)이 무엇인지는 알 필요 없습니다. 시간 복잡도는 입력-연산수행시간의 변화율과 관련이 있구나! 정도만 이해하고 넘어가시면 됩니다.

다시 말해, 한 알고리즘(i.g. 1부터 마지막 숫자까지 순서대로 시도하기)을 사용해서 숫자 게임을 100개, 1,000개, 10,000개, ... 이런 식으로 늘려가면서 진행했을 때 정답을 맞출 때까지 걸리는 시간이 어떻게 변화되는가를 나타내는 것입니다.

그럼 이제 위에서 소개했던 두 방법의 시간 복잡도를 알아보겠습니다.

순서대로 시도하는 알고리즘의 시간 복잡도

1부터 100까지의 숫자로 게임을 진행하면 정답을 맞추기 까지 얼마나 많은 시간이 필요할까요? 정답이 무엇이냐에 따라 다를 것입니다. 정답이 1이라면 단 한 번의 시도로도 맞출 수 있고 정답이 100이라면 100번의 시도 끝에 정답을 맞출 수 있습니다. 이렇게 정답이 그때그때 다를 텐데 문제 해결에 걸리는 시간을 어떻게 알 수 있을까요?

그래서 시간 복잡도를 나타낼 때는 주로 최악의 시나리오를 가정합니다. 최악의 시나리오일 때 정답은 100이고 100번의 시도를 해야 정답을 맞출 수 있으므로 편의상 1번 시도할 때 마다 1이라는 시간이 걸린다고 가정하면 100만큼의 시간이 걸리게 됩니다.

또 1부터 1,000까지 숫자로 게임을 진행하고 순서대로 맞추기 알고리즘을 사용하면 최악의 경우 정답이 1,000일 테니 1,000만큼의 시간이 걸릴 것입니다.

마찬가지로 1부터 n까지의 숫자로 게임을 진행하면 n 만큼의 시간이 걸릴 것을 예상할 수 있습니다.

이를 BigO 표기법을 활용하여 O(n)으로 나타낼 수 있습니다. 즉, 1부터 순서대로 맞추기 알고리즘은 O(n)의 시간 복잡도를 갖는 알고리즘이며 다음과 같이 그래프로 나타낼 수 있습니다.

시간 복잡도가 O(n)인 알고리즘은 그래프에서 볼 수 있듯이 입력(데이터 크기)이 증가했을 때 연산 수행 시간(문제를 해결하는 데 걸리는 시간)이 선형적으로 증가하는 알고리즘입니다.

오답을 반씩 제거해나가며 시도하는 알고리즘의 시간 복잡도

이번에는 50부터 시작해서 출제자의 힌트를 듣고 오답을 반씩 제거해나가는 알고리즘의 시간 복잡도를 알아보겠습니다. 이 알고리즘의 시간 복잡도는 어떻게 나타낼 수 있을까요?

정답을 맞추는 사람의 입장이 되어 숫자 하나씩 시도를 해보겠습니다.

첫 번째 시도: 정답이 아니더라도 업인지 다운인지 알려주기 때문에 오답이었을 때 50%를 제거할 수 있도록 50을 시도

두 번째 시도: 1부터 49까지 숫자 중 정답이 있음을 알 수 있습니다. 이번에는 (1 + 49) / 2 = 25를 시도

세 번째 시도: 1부터 24까지 숫자 중 정답이 있고 (1 + 24) / 2 = 12.5이므로 내림해서 12를 시도

네 번째 시도: 1부터 11까지 숫자 중 정답이 있고 (1 + 11) / 2 = 6을 시도

다섯 번째 시도: 1부터 5까지 숫자 중 정답 존재, (1 + 5) / 2 = 3 시도

여섯 번째 시도: 1부터 2까지 숫자 중 (1 + 2) / 2 = 1.5이므로 내림해서 1시도

일곱 번째 시도: 남은 숫자는 2이므로 2 시도

최악의 시나리오를 가정하기 위해 정답을 2로 설정해 봤고 이 때 7번의 시도 끝에 정답을 맞힐 수 있었습니다. 과연 이 알고리즘의 시간 복잡도는 어떻게 구할까요?

조금 더 쉽게 생각할 수 있도록 문제를 다음과 같이 변경해 보겠습니다. 100을 반씩 줄여나갈 때 1이 될 때까지 몇 번의 시도가 필요할까요? 100 > 50 > 25 > 13 > 7 > 4 > 2 > 1이므로 7번의 시도 끝에 1이 됩니다.

만약에 400일 경우 어떨까요? 400 > 200 > 100 > 50 > 25 > 13 > 7 > 4 > 2 > 1 이므로 9번의 시도 끝에 1이 됩니다.

어떤 숫자 n이 있을 때 그 숫자를 1/2로 계속 나눴을 때 몇 번 만에 1이 될까?라는 문제는 1에서 2를 계속 곱할 때 몇 번 만에 N이 될까?로 반대로 생각해 볼 수 있습니다.

이를 수식으로 나타내보면 1*2^X = n 즉, 2^X = n입니다. 여기서 N은 데이터의 크기, X은 연산 수행 시간입니다. 지수 함수의 역함수는 로그 함수이므로 X = log n(밑이 2인 로그 함수)이며 따라서 시간 복잡도는 O(log n)으로 나타낼 수 있습니다.

이를 그래프로 나타내면 다음과 같습니다.

시간 복잡도가 갖는 의미

이 그래프를 통해 알 수 있는 사실은 O(log n)의 시간 복잡도를 갖는 알고리즘의 경우 입력의 크기가 엄청 커졌을 경우에도 그에 따른 연산 수행 시간의 증가율이 가파르지 않다는 것입니다.

따라서 O(n)의 시간 복잡도를 갖는 알고리즘과 비교했을 때, 입력이 매우 큰 경우에도 빠른 시간 안에 문제를 해결할 수 있습니다. 예를 들어, 1조 개의 카드로 게임을 진행할 때 최악의 경우(1번 시도마다 1초가 걸린다고 가정했을 때)

• O(n) 알고리즘: 31,710 년 소요
• O(log n) 알고리즘: 40초 소요

위와 같이 데이터 사이즈가 클 때 O(log n)의 힘을 체감할 수 있습니다.

데이터 사이즈가 작을 때는 차이가 크지 않기 때문에 이 점 또한 항상 생각해야합니다.

마치면서

이제 시간 복잡도라는 개념을 알게 되었으니 다음과 같은 생각을 할 수 있게 되었습니다.

• 데이터 사이즈가 너무 커서 O(n) 알고리즘으로는 이 문제를 해결하기 어려울 것 같아. O(log n) 알고리즘으로 개선해보자
• 이 문제는 데이터 사이즈가 크지 않기 때문에 굳이 복잡한 O(log n)의 알고리즘을 사용하기 보다 이해하기 쉽고 빠르게 작성할 수 있는 O(n) 알고리즘을 활용하는게 더 좋아보여

다음에는 오늘 배운 알고리즘을 코드로 구현해 보면서 더 깊게 이해하는 시간을 가져보겠습니다.