🔎 Overview
매일 아침, 일어나서 컴퓨터에 앉자마자 반드시 진행 중인 루틴이 하나 있다. 코딩테스트를 적어도 한 문제 진행하는 것이다.
유명한 코딩테스트 사이트인 백준, 프로그래머스, 리트코드 중 프로그래머스에서 하루에 한 문제 이상씩 풀어보며 코딩테스트에 대한 감을 유지하는 중이다.
아직 너무 어려운 코딩테스트 풀이까지는 진입하지 않았다. 전체 문제를 정답률 높은 문제 순으로 필터링하여 차근차근 풀고 있다.
그러다보니 어느덧, 그렇게 많은 숫자는 아닐지 몰라도 432 문제를 풀었다. 매일마다 늘어나는 순위와 해결한 문제를 보며, 작은 성취감과 자존감을 채워나가고 있다.
코딩테스트를 진행하며, 시간 복잡도 문제로 골머리를 많이 앓고 있다. 내가 생각한 시간 복잡도와 내 풀이의 시간 복잡도가 다를 때도 가끔 있고, 시간 복잡도를 줄이지 못해 런타임 에러가 터지는 경우도 왕왕 있다.
이러한 문제들을 잘 해결하기 위해서는 당연히 시간 복잡도에 대해 잘 알고 있어야 한다. 그렇기에 시간 복잡도에 대해서 간략하게나마 정리해보았다.
📕 시간 복잡도
- 알고리즘이 수행되는 데 걸리는 시간을 데이터의 크기에 따라 분석하는 방법
- 실제 실행 시간 측정 대신, 입력 크기 n이 증가할 때 연산 횟수가 어떻게 변하는지에 따라 성능을 평가
- 일반적으로 Big-O 표기법으로 표현되며, 항상 최악의 경우의 알고리즘 성능을 나타냄
✒️ 코딩테스트에서의 시간 복잡도
- 코딩테스트에서는 이 시간 복잡도를 잘 처리하여, 주어진 시간 제한 내에 알고리즘이 동작하도록 해야 함
- 일반적으로 1초에
(10^8), 즉 1억 번의 연산을 처리할 수 있다고 가정
1️⃣ O(1) - 상수 시간
n의 크기와 상관없이, 실행 시간은 항상 일정n- 제한 없음- ex) 산술 연산, 조건문, 값 접근 ...
public int sum(int x, int y) {
return x + y;
}x와y의 값에 상관 없이 항상 한 번의 계산으로 실행이 종료됨- 따라서 시간 복잡도는
O(1)
2️⃣ O(logn) - 로그 시간
n의 크기에 따라 실행 시간이 로그 증가n-10^18이상도 가능, 매우 넉넉한 조건- ex) 이진 탐색, 균형 이진 트리 탐색 ...
public int binarySearch(int[] arr, int key) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == key) {
return mid;
} else if (arr[mid] <= key) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}while (left <= right)일 때, 배열을 반으로 나누는 작업 반복n을 반으로 나누는 횟수는logn에 비례- 따라서 시간 복잡도는
O(logn)
3️⃣ O(n) - 선형 시간
n의 값과 비례하여 실행 시간 증가n<=100,000,000~1,000,000,000- ex) 배열, 리스트 등 컬렉션 탐색, 반복문 ...
public int sumArr(int[] arr) {
return Arrays.stream(arr).sum();
}arr의 크기n을 모두 한 번씩 순회하며 값을 더함- 따라서 시간 복잡도는
O(n)
4️⃣ O(nlogn) - 선형 로그 시간
- (
n값 * 로그 증가) 만큼의 실행 시간 n<=1,000,000~10,000,000- ex) 합병 정렬, 힙 정렬 ...
public void mergeSort(int[] arr) {
if (arr.length < 2) {
return;
}
int mid = arr.length / 2;
int[] left = Arrays.copyOfRange(arr, 0, mid);
int[] right = Arrays.copyOfRange(arr, mid, arr.length);
mergeSort(left);
mergeSort(right);
merge(arr, left, right);
}
public void merge(int[] arr, int left, int right) {
// 두 배열을 합치는 알고리즘
// 생략
}mergeSort(left)와mergeSort(right)에서 배열을 반으로 나누므로,logn번 반복- 나눠진 배열을 병합하며 올라오므로
O(n) - 따라서 시간 복잡도는 둘을 곱한
O(nlogn)
5️⃣ O(n^2) - 이차 시간
- 값이
n일 때,n*n만큼 실행 n<=1,000~10,000- ex) 이중 반복문, 버블 정렬 ...
public void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}- 이중
for루프로 인해n*n번 실행 - 따라서 시간 복잡도는
O(n^2)
6️⃣ O(n^3) - 삼차 시간
- 값이
n일 때,n*n*n만큼 실행 n<=100~300- ex) 플로이드-워셜, 삼중 반복문 ...
public void flodWarshall(int[][] graph) {
int n = graph.length;
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
}
}
}
}- 삼중
for루프로 인해n*n*n번 실행 - 따라서 시간 복잡도는
O(n^3)
7️⃣ O(2^n) - 지수 시간
- 값이
n일 때,2의n제곱 만큼 실행 n<= 약20- ex) 완전 탐색 DFS, 모든 부분집합 탐색 ...
public class Solution {
List<Integer> list;
public static void main(String[] args) {
list = new ArrayList();
subsetSum(new int[]{1, 2, 3, 4, 5}, 0, 0);
}
public void subsetSum(int[] arr, int sum, int idx) {
if (idx == arr.length) {
list.add(sum);
return;
}
subsetSum(arr, sum + arr[idx], idx + 1);
subsetSum(arr, sum, idx + 1);
}
}arr의 요소를 더할 경우와 더하지 않을 경우 총 2가지 실행- 각
subsetSum호출시마다 2가지 경우의 수가 존재함 - 따라서 시간 복잡도는
O(2^n)
8️⃣ O(n!) - 팩토리얼 시간
n!만큼 실행n<= 약10- ex) 순열, Brute Force(완전 탐색) ...
public class Solution {
int result;
boolean[] visited;
public int solution(int k, int[][] dungeons) {
result = Integer.MIN_VALUE;
visited = new boolean[dungeons.length];
dfs(k, dungeons, 0, 0);
return result;
}
public void dfs(int k, int[][] dungeons, int depth, int count) {
if (depth == dungeons.length) {
result = Math.max(result, count);
return;
}
for (int i = 0; i < dungeons.length; i++) {
if (!visited[i]) {
if (k >= dungeons[i][0]) {
k -= dungeons[i][1];
visited[i] = true;
dfs(k, dungeons, depth + 1, count + 1);
visited[i] = false;
k += dungeons[i][1];
}
}
}
result = Math.max(result, count);
}
}- 값이
n일 경우, 재귀 호출 시마다n - 1개의 경우의 수 고려 - 즉,
n - 1씩 줄여가며 반복 - 따라서 시간 복잡도는
O(n!)
📚 시간 복잡도 정리
| 시간 복잡도 | 최대 ( n ) (1초 기준) | 설명 |
|---|---|---|
| O(1) | 제한 없음 | 상수 시간 연산은 항상 가능 |
| O(log n) | 매우 큼 ( 10^18 ) | 로그 시간은 큰 입력에서도 가능 |
| O(n) | 약 ( 10^8 ) | 선형 시간은 입력이 매우 클 때도 가능 |
| O(n log n) | 약 ( 10^6 ) ~ ( 10^7 ) | 병합 정렬, 힙 정렬 등에서 자주 사용 |
| O(n^2) | 약 ( 10^3 ) ~ ( 10^4 ) | 이중 루프 등에서 사용 가능 |
| O(n^3) | 약 ( 100 ) ~ ( 300 ) | 플로이드-워셜 등 |
| O(2^n) | 약 ( 20 ) | 부분집합 탐색, 완전 탐색에서 사용 |
| O(n!) | 약 ( 10 ) | 순열 생성, 최적화 문제에서 사용 |
참고) OpenAI. (2024).ChatGPT(4o)[Large language model].https://chatgpt.com/
기록