코딩테스트 시간복잡도 & 빅오표기법 의 모든것

 

1. 시간복잡도란?

코딩테스트 문제들은 다양한 방법으로 풀 수 있지만,
그 중 '가장 효율적으로 해결하는 알고리즘'이 있다.
이것은 알고리즘이 실행되는 제한 시간과 관련이 있다. 
 
시간 복잡도는 알고리즘의 성능을 나타내는 지표로,
입력 크기에 대한 연산 횟수의 상한이다. 
시간 복잡도가 낮은 알고리즘이 좋은 알고리즘이다. 
 
*입력크기 = 알고리즘이 처리해야 할 데이터 양
 

---

2. 빅오 표기법

최악의 경우 시간 복잡도를 표현하는 표기법을 '빅오표기법'이라고 한다.
빅오표기법을 이해해야만 코딩테스트에서 최적의 알고리즘을 찾을 수 있다.
 
어떤 프로그램의 연산 횟수를 f(x)라고 할 때 함수의 최고차항을 남기고 계수를 지워서 O( ) 형식으로 표기하는 것이 빅오표기법이다. 
예를 들어 어떤 프로그램의 연산 횟수가
f(x) = 2x² + 3x + 5 라면 시간복잡도는
최고차항을 따라 O(x²)이다. 
 

수식	빅오 표기법	설명
3x² + 5x + 6	O(x²)	다항함수로 구성되어 있으므로 최고차항인 x²만 남음
x + logx	O(x)	다항함수 + 로그함수는 증가폭이 더 낮은 로그함수가 사라짐
2ˣ + 10x⁵ + 5x²	O(2ˣ)	지수함수는 다항함수보다 빠르게 증가하므로 지수함수만 남음
5x² - 5x	O(x²)	최고차항 x²만 남음

 

public static void main(String[] args) {
	solution(6);
}

public static void solution(int n) {
	int count = 0;
    
    for (int i = 0; i < n; i++) { // N^2 연산
    	for (int j = 0; j < n; j++) {
        	count++;
        }
    }
    
    for (int i = 0; i < n; i++) { // N 연산
    	count++;
    }
    
    for (int i = 0; i < n * 2; i++) { // N*2 연산
    	count++;
    }
    
    for ( int i = 0; i < 5; i++) { // 5 연산
    	count++;
    }
    
    System.out.println(count);
}

 
위 코드에서 solution() 함수는 n^2번, n번, 2n번, 5번의 증가 연산을 하고, 결과값 count는 연산 횟수이다.
6^2 + 6 + 2*6 + 5 를 하면 연산횟수는 59이다.
 
이것을 식으로 표현하면 n = x일 때, f(x) = x^2 + 3x + 5 이고,
시간복잡도는 최고차항은 O(x^2)이다.

---

3. 시간복잡도 계산

코딩테스트에서는 제한 시간이 있는데, 빅오표기법을 통해 어떤 알고리즘을 써야 해당 시간 안에 출력할 수 있을 지 예측할 수 있다. 빅오표기법을 활용하지 않고, 조건에 맞지 않는 알고리즘을 짜면 런타임에러로 시간을 낭비할 수 있다. 
 

컴퓨터가 1초당 연산할 수 있는 최대 횟수는 1억번이다.
1s = 100,000,000 회

 
하지만 채점 시간을 충분히 여유 있게 지정하기 위해 연산 횟수를 3분의 1로 줄여 1000만 ~ 3000만 정도로 생각해서 시간복잡도를 판단하면 가장 좋다. 즉, 제한 시간이 1초인 문제는 연산횟수가 3,000만이 넘는 알고리즘은 사용하면 안 된다.
 

N의 가용 범위

시간복잡도	N의 가용 범위
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)	1,000~2,000만
O(logN)	10억

 
예를 들어, 배열의 요소들을 하나 하나 짚어가면서 순회하는 방식은 시간 복잡도가 O(N)이다. O(N)이 허용하는 연산 횟수는 2,000만이다. 따라서 데이터의 개수가 2,000만 개 이하이면 이 알고리즘은 사용할 수 있다. 이런식으로 불필요한 알고리즘은 제외하고 코드를 짜면 된다. 
 

시간 복잡도 참고 기준

 

1. 문제 정의
2. 연산횟수 측정
3. 시간복잡도 분석

 

---

별찍기

우리가 이중for문으로 잘 알고 있는 별찍기의 연산횟수를 계산 해 보자.
1번째 줄은 1번 연산, 2번째 줄은 2번 연산, ... N번째 줄은 N번 연산한다.

위키독스, 코딩테스트 합격자 되기 [JAVA편]

 

 
따라서 연산횟수 f(N)은 빅오표기법으로 O(N^2)이다. 

---

박테리아 수명 문제

초기 박테리아 세포 개수가 N일 때 해마다 세포 개수가 이전 세포 개수의 반으로 준다면 언제 모든 박테리아가 죽을지 계산해야 한다. 입출력 예를 표를 통해 살펴 보자.
 
예를 들어 N이 16인 경우, 모든 박테리아는 5년이면 소멸한다.

위키독스, 코딩테스트 합격자 되기 [JAVA편]

현재 박테리아의 수가 N이라면 1년 뒤의 박테리아 수는 ½N이다.
Y년 후의 박테리아의 수는 (½)YN이다.
 

위키독스, 코딩테스트 합격자 되기 [JAVA편]

 
그러면 박테리아의 소멸 시기는 (½)YN의 값이 최초로 1보다 작아질 때이다.  
즉, (½)YN <= 1인 Y를 찾으면 된다. 
 

위키독스, 코딩테스트 합격자 되기 [JAVA편]

 
이 계산 과정으로 이 알고리즘은 O(logN)의 시간 복잡도를 가진다는 것을 알 수 있다. 
 

---

4. 코딩테스트 문제 유형별 알고리즘

 

1. 완전 탐색 (Brute Force)

• 특징: 가능한 모든 경우의 수를 시도하는 방식입니다.
• 시간 복잡도: O(n^k) 또는 O(2^n) 형태가 많습니다.
  • 예: 배열에서 두 수를 더해서 목표값을 찾는 문제에서는 두 개의 이중 반복문이 필요한 경우가 많아 O(n^2)가 됩니다.
• 적용: 입력 크기가 작거나 최대 몇백 ~ 몇천 수준일 때 적합합니다.
• 예시 문제: 순열, 조합을 사용한 경우의 수 계산.

[프로그래머스]완전탐색 문제, '모음 사전'

---

2. 정렬 (Sorting)

• 특징: 정렬을 통해 문제를 단순화하거나, 이후 작업을 쉽게 합니다.
• 시간 복잡도: 일반적으로 O(n log n) (퀵 정렬, 합병 정렬, 힙 정렬 등).
• 적용: 입력 크기가 10^6 정도일 때도 유효합니다.
• 예시 문제: 정렬 후 이웃한 요소 비교, 특정 기준에 따라 정렬 후 최댓값, 최솟값 찾기.

---

3. 이분 탐색 (Binary Search)

• 특징: 정렬된 배열에서 특정 값을 찾을 때 절반씩 탐색하는 방식입니다.
• 시간 복잡도: O(log n).
• 적용: 데이터가 정렬되어 있거나, 정렬이 가능한 경우.
• 예시 문제: 정렬된 배열에서 특정 요소의 위치 찾기, 범위를 좁혀가며 최적화하는 문제.

[프로그래머스] 이분탐색 문제, '입국심사'

---

4. 투 포인터 (Two Pointers) 및 슬라이딩 윈도우 (Sliding Window)

• 특징: 배열이나 리스트에서 두 개의 포인터(인덱스)를 사용하여 원하는 조건을 찾습니다.
• 시간 복잡도: 일반적으로 O(n).
• 적용: 정렬된 배열이나 리스트에서 특정 합을 구할 때, 부분 배열의 최적화된 합을 찾을 때 등.
• 예시 문제: 특정 합이 되는 두 수 찾기, 연속된 부분 수열의 합 찾기.

[프로그래머스] 투포인터 문제, '연속된 부분 수열의 합'

---

5. 해시 맵 / 딕셔너리 (Hash Map / Dictionary)

• 특징: 키-값 쌍을 저장하고, 검색과 삽입을 평균 O(1) 시간에 수행합니다.
• 시간 복잡도: 평균 O(1), 최악의 경우 O(n) (해시 충돌 발생 시).
• 적용: 빈도 수 계산, 특정 키 존재 여부 확인 등.
• 예시 문제: 배열 내 중복 요소 찾기, 주어진 값의 빈도 찾기.

[프로그래머스] 해시 문제, '완주하지 못한 선수'

---

6. 그래프 탐색 (DFS / BFS)

• 특징: 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)를 통해 그래프의 모든 노드를 방문합니다.
• 시간 복잡도: O(V + E) (노드 수 V와 간선 수 E의 합).
• 적용: 그래프나 트리 구조에서 경로 찾기, 연결 요소 찾기.
• 예시 문제: 미로 탐색, 섬의 개수 세기, 최단 경로 찾기.

[프로그래머스] DFS/BFS 문제, '네트워크'

---

7. 다이나믹 프로그래밍 (Dynamic Programming)

• 특징: 큰 문제를 작은 하위 문제로 나누어 해결하고, 결과를 저장하여 중복 계산을 피합니다.
• 시간 복잡도: 문제에 따라 다르며, 일반적으로 O(n) 또는 O(n^2) 정도.
• 적용: 최적 부분 구조와 중복 부분 문제의 성질을 가진 문제.
• 예시 문제: 피보나치 수열, 최대 부분 수열 합, 최소 비용 경로.

---

8. 그리디 알고리즘 (Greedy Algorithm)

• 특징: 매 단계에서 최선의 선택을 하여 전체 최적해를 구합니다.
• 시간 복잡도: 문제에 따라 다르지만, 일반적으로 정렬(O(n log n)) 후 선택할 수 있습니다.
• 적용: 매 선택이 이후 선택에 영향을 주지 않는 경우.
• 예시 문제: 동전 거스름돈 문제, 회의실 배정, 배낭 문제(근사 해법).

[프로그래머스] 그리디 문제, '큰 수 만들기'

---

9. 조합론 (Combinatorics)

• 특징: 가능한 모든 조합이나 순열을 계산하는 방식.
• 시간 복잡도: 조합은 O(nCm), 순열은 O(nPm)로 대개 매우 큰 값이 됩니다.
• 적용: 제한된 크기의 조합이나 순열을 구할 때 사용.
• 예시 문제: 부분 집합의 합 구하기, 모든 가능한 경로 탐색.

---

10. 백트래킹 (Backtracking)

• 특징: 해를 찾다가 조건에 맞지 않으면 되돌아가는 방식으로 최적해를 찾습니다.
• 시간 복잡도: 경우에 따라 달라지며, 최악의 경우 O(n!)이 될 수 있습니다.
• 적용: 모든 가능성을 탐색하면서도, 조건에 맞지 않는 경우 가지치기를 통해 효율적으로 탐색할 때.
• 예시 문제: N-Queen 문제, 부분 집합 합 문제, 순열 및 조합 생성.

[프로그래머스] 백트래킹 문제, N-Queen'

---

11. 트리 탐색 (Tree Traversal)

• 특징: 트리의 각 노드를 방문하는 방법으로, 전위, 중위, 후위 순회 방식이 있습니다.
• 시간 복잡도: O(n) (노드 수 n).
• 적용: 트리에서 특정 경로 찾기, 모든 노드 방문.
• 예시 문제: 이진 트리 경로 탐색, 이진 검색 트리 탐색.