코딩 테스트 필수 개념: 시간 복잡도를 알면 문제 해결이 쉬워진다

최근에 코딩 테스트 합격자 되기 - C++ - 저자 박경록님 께서 스터디를 열어 주셨는데
좋은 기회라고 생각해서 스터디에 참여하게 되었습니다.  개발자로서 문제해결능력, 논리력을 키우고자 한다면 알고리즘만한게 없는거 같아요. 같이 공부하면서 알고리즘과 친해지는 시간이 되었으면 좋겠습니다.

 

INTRODUCTION TO ALGORITHMS

가장 유명한 알고리즘 입문서인 INTRODUCTION TO ALGORITHMS를 아시나요? 두께가 어마어마 하네요.

언젠가는... 읽어볼 수 있겠죠? ㅎㅎ

 

1. 알고리즘 이란?

위키피디아에서는 알고리즘을 수학과 컴퓨터과학에서 사용되는 문제 해결방법을 정의한 "일련의 단계적 절차" 이자 어떠한 문제를 해결하기 위한 "동작들의 모임" 이라고 합니다. 즉, 어떠한 문제를 풀기위한 처리과정 or 절차로 정리할 수 있겠네요.

 

wikipedia - 알고리즘의 정의

 

위키 피디아에서 말한 좋은 알고리즘의 특징 중 타당성을 언급하겠습니다.

타당성이라 함은 효율적이고 실용적인 알고리즘의 성능을 이야기합니다. 그렇다면 어떤게 효율적이고 실용적인 알고리즘일까요? 혹은 알고리즘의 성능은 어떻게 측정할까요?

 

2. 알고리즘의 성능은 어떻게 측정할까요?

입력 -> 동작 -> 출력

 

알고리즘의 성능은 어떠한 입력이 들어왔을때, 출력되기까지의 동작을 절대적인 시간으로 측정하느냐, 연산횟수로 측정하느냐로 나뉠 수 있습니다.

 

절대적인 시간으로 측정하는 방법은 컴퓨터의 성능이나 환경에 따라서 일정하지 않아 적절한 측정 방법이라고 볼 수 없습니다.

알고리즘 성능은 어떠한 환경에서도 달라지지 않는 기준이 필요합니다.

 

연산횟수로 측정하는 방법은 같은 입력값이라면 연산횟수가 동일하기 때문에 환경에 영향을 받지 않는 기준이 될 수 있을 것 같네요.

그러나 연산횟수 측정 방법도 다른 입력값이 들어온다고 한다면, 연산횟수 또한 계속 변경되지 않을까요?

예를들어 1부터 n까지 더하는 알고리즘이 있다고 할때, A의 입력값 n은 10, B의 입력값 n은 1000만이라고 한다면? 그차이가 많이 날 것 같네요. 그러므로 입력값이 달라지더라도 동일하게 표현할 어떠한 기준이 필요합니다.

 

3. 시간복잡도

컴퓨터 사이언스에서 알고리즘의 시간복잡도는 입력값과 연산횟수의 상관관계를 정량화하는 것이라고 합니다.

점근적 표기로 변화에 대한 추이를 나타내기 때문에 입력값이 달라지더라도 동일하게 표현할 어떠한 기준이 될 수 있습니다.

 

3.1. 빅 오 표기법 (Big - O)

Big-O 표기법

 

빅 오 표기법은 입력값이 커질 때 알고리즘의 성능이 가장 최악의 경우를 기준으로 표기하는 수학적인 표기 방법입니다.

 

입력값이 계속 달라질 수 있는데, 하나의 입력값 마다 알고리즘의 성능을 꼭 정밀하게 표기할 필요가 있을까요? 기준대로 대략적인 성능의 변화의 추이만 표현할 수만 있으면 되지 않을까요? 이러한 이유로 알고리즘의 성능은 주로 빅 오 표기법을 사용하여 표현합니다.

 

빅오 표기법을 표기하는 예를들어 보겠습니다. 어떠한 연산횟수가 3N^2 + 2N + 7라면 그래프는 다음과 같습니다.

desmos  3N^2 , 2N, 7 그래프

 

N은 커지면 커질수록 격차가 커지는게 보이시나요? 3N^2 + 2N + 7에서 +2N, +7은 무시할 정도로 작은 값이 되기 때문에

특정시점부터 의미가 없어지는 값이 됩니다. 또한 3N^2과 N^2도 N이 커질수록 비슷하게 증가하게 됩니다.

 

위에서 기준대로 대략적인 성능 변화의 추이만 표현한다고 이야기 했었죠.

그러므로, 빅오 표기법을 만드는 공식은 다음과 같습니다.

1. 가장 영향이 큰 최고차 항만 남긴다.
2. 남은 최고차 항의 계수를 버린다.

 

결국 의미가 작은 차, 포 다 떼고 결론적으로 빅오 표기법은 3N^2 + 2N + 7은 --> O(n^2)으로 표기하는 것 입니다.

 

3.2. Big-O Complexity Chart

Big O Complecity Chart

위의 그래프처럼 빅오 표기법의 기준은 느린 성능부터 나열하면 O(N!), O(2^N), O(N^2), O(NlogN), O(N), O(logN), O(1)로 순서로 정의 될 수 있습니다. 자세한 성능의 예가 궁금하시면 아래의 Big-O Complexity Chart 링크에 잘 정리되어있으니 참고하시면 좋을 것 같네요.

Big O Cheat Sheet – Time Complexity Chart

 

4. 그러면 코딩테스트에서 어떻게 활용하는데?

 

코딩테스트에서 문제를 풀기 위해서는 제한된 시간내에 알고리즘의 동작이 끝이 나야합니다.

컴퓨터가 초당 연산할 수 있는 최대 횟수는 대략 1억 번 정도입니다. 따라서 코딩 테스트의 경우 주요 로직의 연산 횟수를 초당 1,000~2,000만 정도로 고려해서 시간 복잡도를 생각하면 됩니다.

시간 복잡도	최대 연산 횟수
O(N!)	10
O(2^N)	20 ~ 25
O(N^3)	200 ~ 300
O(N^2)	3,000 ~ 5,000
O(NlogN)	100만
O(N)	1000 ~ 2000만
O(logN)	10억

 

대부분 문제는 입력값의 범위가 주어지는데, 이 입력값의 크기를 통해 어느정도의 시간 복잡도내에 해결해야 하는지 추측할 수 있습니다. 예를들면 입력값 N에 대하여 0 <= N <= 1,000,000 범위로 들어올 수 있고, 1초내에 풀어야 한다라는 조건이 있다면?

내가 작성해야 하는 알고리즘은 O(NlogN)의 시간내에 해결이 가능해야 한다는 것을 의미하게 되는거죠. ㅎㅎ

 

5. 마치며...

코딩테스트 합격자되기 c++편 강의와 시간복잡도에 대한 자료를 보면 정리했습니다.
부족한 글 읽어 주셔서 감사합니다. 또한 잘못된 내용 있으면 지적해주시면 감사하겠습니다.

하얀종이개발자

Reference

https://ko.wikipedia.org/wiki/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 - 위키피디아 알고리즘

https://ko.wikipedia.org/wiki/%EC%8B%9C%EA%B0%84_%EB%B3%B5%EC%9E%A1%EB%8F%84 - 위키피디아 시간복잡도

https://www.freecodecamp.org/news/big-o-cheat-sheet-time-complexity-chart/ - Big-O complexity chart

https://www.freecodecamp.org/korean/news/big-o-notation-why-it-matters-and-why-it-doesnt-1674cfa8a23c/ - Big-O 표기법
https://www.youtube.com/@dremdeveloper - 코딩테스트 합격자되기 c++편 (유튜브 강의)

https://www.youtube.com/watch?v=CLXFgptB81M - 코딩테스트 합격자되기 c++편 (책 소개)