알고리즘 시간복잡도에 대해 많이 모르시고, 문제를 푸시는 것을 알게되어 이 기회에 되짚고 가면 좋겠다는 취지로 제대로 정리해보았습니다.
허접한 글이지만 미약하게나마 도움이 되면 좋겠습니다.

시간복잡도란 ?

코드의 실행시간이 어떤 요인으로 결정되는지 나타내는 시간과 입력 데이터의 함수 관계입니다.
코테에서는 자신이 짠 코드의 시간복잡도를 계산하여 문제에서 요구하는 입력을 제한 시간 내에 해결할 수 있는지 파악해야 합니다.

빅오표기법

알고리즘이 겪을 수 있는 최악의 경우에 걸리는 시간과 입력 간의 상관관계를 표기합니다.
입력크기가 N, 이에 비례하는 시간이 걸린다면 O(N)으로 표기합니다.

시간 복잡도 그래프

이진탐색 : O(logN)
선형탐색 : O(N)
정렬 : O(NlogN)
조합 : O(2^N)
순열 : O(N!)

최악의 경우를 시간 복잡도에 대입해보았을 때, 1억이 넘지 않는다면 실행 시간이 1초보다 빠른 충분히 효율적인 코드일 가능성이 높습니다.
즉, 코테에서는 대부분 1억 근처에서 계산되는 경우는 거의 없고, 대부분 1억보다 한참 아래 있거나, 1억을 훨씬 넘는 값으로 계산되기 때문에 필자는 1억을 일종의 커트라인으로 잡는 것입니다.
또한, 1억은 시간제한이 1초인 문제일 때의 기준입니다. 제한시간이 3초면 3억 번이겠죠?
이런식으로 시간복잡도를 생각하고 문제에 접근해야 정답을 유추할 수 있을 것입니다.
여기까지 잘 따라오셨죠 ? 그럼, 필자가 문제 하나 드리겠습니다.
만약 길이가 N이고 정수로 이루어진 배열에서 M개의 숫자 유무를 확인하는 문제라면?
문제 조건은 N은 최대 10000, M은 최대 100000입니다.
이 경우 시간복잡도는 O(NM)입니다.
왜? --> 하나의 숫자를 검사할 때마다 배열을 전부 순회한다면 M개의 숫자에서 각각 N번의 검사를 해야하기 때문입니다.
그럼 해당 문제의 시간복잡도는 최대값 입력시, 10억이 되겠죠? --> 시간초과 무조건 뜹니다.

만약, 이 문제를 '이진탐색'을 이용한다면 ?
O((N+M)logN)의 시간복잡도로 해결할 수 있으며,
HashSet 자료구조를 이용하면 O(N+M)의 시간 복잡도로 해결할 수 있게됩니다.

시간복잡도 계산하기

그렇다면 의문이 들 것입니다. 시간복잡도는 어떻게 계산하는 것인가 ?
--> 가장 기본이 되는 방법은 반복 횟수를 세어 보는 것입니다.
일반적으로 입력되는 값들을 순회하면서 처리하는 데 반복문이 사용됩니다.
이렇게 사용되는 반복문이 어떤 값에 비례해서 반복하는지 따져 보면 시간 복잡도를 계산할 수 있게 됩디다.

어림 짐작하기

여기서, 한 가지 말씀드리고 싶은 것은 시간복잡도는 정확한 실행 시간을 계산하는 용도가 아닙니다. 단지 실행 시간이 어떤 요인으로 결정되는지 나타내는 수식일 뿐입니다.
따라서, 시간 복잡도에서는 곱하거나 더해지는 상수 부분은 나타내지 않습니다.

만약, 길이 N짜리 배열을 순회하고 그 다음에 길이 M짜리 배열을 순회하는 것입니다.
이 경우에는 N번 반복한 후 M번 반복하므로 O(N+M)으로 표기합니다.
--> N과 M의 최대값을 구하여 시간복잡도에 대입해서 효율성을 판단해야 한다는 것입니다.

시간 복잡도를 줄이는 방법

만약, 정렬된 배열에서 특정 원소의 위치를 찾는 문제입니다.
배열의 모든 원소를 순회한다면 이 문제는 O(N)의 시간복잡도가 소요됩니다.
하지만 정렬되어 있다는 조건에 주목한다면 ? --> 이진탐색을 적용할 수 있습니다.
이진탐색의 시간복잡도는 O(logN)이므로 훨씬 효율적인 탐색이 가능하겠죠?

또한, 배여레서 중복을 제거한 원소들을 찾고 싶을 때 원소별로 배열 전체를 순회하면 O(N^2)의 시간복잡도가 소요됩니다.
이때, 자료구조의 Set 을 이용한다면 ? --> O(N)으로 해결할 수 있습니다.
참고로, O(N^2)과 O(N)은 엄청난 차이입니다. --> N의 크기가 커질수록 엄청난 효율차이가 발생합니다.

자, 감 잡으셨을까요?

결론

문제 조건에 맞는 적절한 알고리즘과 자료구조를 이용하는 것이 코테의 기본이자 핵심입니다.

문제를 보고 효율적인 풀이를 바로 떠올리기 쉽지않을 겁니다. 이럴때엔 문제에서 주어진 입력 조건을 이용하여 풀이의 시간 복잡도를 먼저 유추해보는 것도 풀이를 생각해내기에 좋은 힌트가 될 수도 있습니다.
필자가 시간 제한이 만약 1초일 경우 유추 가능한 시간복잡도를 알려드리겠습니다.

N 		| 유추가능한 시간복잡도 	| 유추가능한 알고리즘
10 		| O(N!) 			| 순열
20 		| O(2^N) 			| 조합
1,000~	| O(N^3),O(N^3logN)	| 완전탐색, 이진탐색
10,000~	| O(NlogN)			| 정렬, 이진탐색

• 위의 필자가 알려준 힌트는 말 그대로 힌트로서만 활용해야 한다는 것입니다.
  (무조건 적으로 해당 알고리즘을 이용해서 풀어라. --> 이 말뜻은 아니라는 것입니다.)

고생하셨습니다. 이 글을 읽은 당신은 이제 시가복잡도에 대해 다 배웠습니다.
코테 건승하십쇼 ! 🤜 👨🏻‍💻 🔥 🏆