오늘은 시간 복잡도와 공간 복잡도에 대해서 간단히 알아보고,
코테 문제를 풀 때 알아두면 좋을 내용을 정리해보려고 한다!
📌 시간 복잡도
알고리즘이 얼마나 오래 걸리는지 알 수 있는 척도로, 알고리즘을 위해 필요한 연산의 횟수를 의미한다.
코테 문제에는 '시간 제한'이라는 것이 있다. 여기서 말하는 시간 제한은 문제를 푸는 시간이 아니라, 작성한 프로그램이 모든 입력을 받아 이를 처리하고 실행 결과를 출력하는 데까지 걸리는 시간을 의미한다. 그래서, 프로그램을 비효율적으로 작성하면 '시간 초과' 메시지와 함께 오답 처리가 된다. 따라서, 문제를 풀 때 최악의 연산량을 계산해 내가 사용할 수 있는 알고리즘을 고르는 것이 좋다.
아래는 대표적인 시간 복잡도를 나타낸 것이다.
| 빅오 표기법 | 명칭 | N=1000일 때의 연산 횟수 | 예시 |
| O(1) | 상수 시간 | 1 | |
| O(logN) | 로그 시간 | ||
| O(N) | 선형 시간 | 1,000 | 1차원 loop |
| O(NlogN) | 로그 선형 시간 | 10,000 | 병합 정렬, 퀵 정렬 |
| O(N^2) | 이차 시간 | 1,000,000 | 2차 loop, 버블 정렬, 삽입 정렬 |
| O(N^3) | 삼차 시간 | 1,000,000,000 | |
| O(2^N) | 지수 시간 | 피보나치 수열, 역기능 재귀 |
시간 복잡도 분석은 문제 풀이의 핵심이다. 문제의 조건을 확인하면 문제를 풀기 위해 얼마나 효율적인 알고리즘을 작성해야 하는지 눈치챌 수 있다. 다음은 시간 제한이 1초인 문제에 대한 예시이다.
- N의 범위가 500인 경우: 시간 복잡도가 O(N^3)인 알고리즘
- N의 범위가 2,000인 경우: 시간 복잡도가 O(N^2)인 알고리즘
- N의 범위가 100,000인 경우: 시간 복잡도가 O(NlogN)인 알고리즘
- N의 범위가 10,000,000인 경우: 시간 복잡도가 O(N)인 알고리즘
📌 공간 복잡도
알고리즘이 얼마나 많은 메모리를 차지하는지 알 수 있는 척도로, 알고리즘을 위해 필요한 메모리의 양을 의미한다.
공간 복잡도 역시 메모리 사용량의 절대적인 제한이 있다. 일반적으로 메모리 사용량 기준은 MB단위로 제시된다. 코테 문제는 대부분 배열을 사용해서 풀어야 한다. 대부분의 문제는 다수의 데이터에 대한 효율적인 처리를 요구하기 때문이다. 그렇다면 int를 기준으로 배열 크기에 따른 메모리 사용량을 확인해보자. (단, 실제로 차지하는 메모리는 컴파일러에 따라 다를 수 있다.)
- int a[1000]: 4KB
- int a[1000000]: 4MB
- int a[2000][2000]: 16MB
코딩 테스트에서는 보통 메모리 사용량을 128MB ~ 512MB 정도로 제한한다. 다시 말하면, 일반적인 경우 데이터의 개수가 1000만 단위가 넘어가지 않도록 알고리즘을 설계해야 한다는 것이다. 만약 배열의 크기가 1000만 단위 이상이라면 알고리즘을 잘못 설계한 것이 아닌지 생각해봐야 한다.
❗️보통 시간 복잡도와 공간 복잡도는 Trade-Off 관계를 가진다.❗️
메모리를 조금 더 많이 사용하는 대신, 반복되는 연산을 생략하거나 더 많은 정보를 관리하면서 계산의 복잡도를 줄일 수 있다.
이때, 메모리를 더 소모하는 대신에 얻을 수 있는 시간적 이점이 매우 큰 경우가 종종 있다. 이렇게 메모리를 더 많이 사용해서 시간을 비약적으로 줄이는 방법으로 Memoization 기법이 있다.
(예를 들면 숫자와 관련한 문제에서, 복잡한 알고리즘을 쓰는 대신 가능한 최대 숫자만큼의 배열을 만들어버리는 것이 나을 때가 있다.)
📌 코딩 테스트 유형
기업에서 보는 코딩 테스트는 적게는 2개에서 많게는 7문제까지도 나오는 것 같다.
주요 문제 유형으로는 구현, 문자열, 자료구조, 완전 탐색, 시뮬레이션, DFS/BFS, DP, 이진탐색, 그리디 정도가 많이 나오는 것 같다.
문제 난이도에 따라 다르겠지만, 나는 반 정도 풀면 나름 선방한 거라고 생각하려 한다 *^^*
열심히, 꾸준히 공부해서 코테 합격하는 그날까지.. 파이팅이다💪🏻💪🏻
🔗 참고 링크
