Part 1. 알고리즘과 시간 복잡도
코딩테스트를 위한 알고리즘 스터디 — 알고리즘 개념, 복잡도 분석, Big-O 표기법
📌 목차
1. 알고리즘이란?
알고리즘(Algorithm) 은 문제를 해결하는 절차/방법입니다.
- 자주 쓰이는 문제 해결 방법은 패턴화되어 있습니다.
- 코딩테스트에서는 이 패턴을 파악하고 적용하는 능력이 중요합니다.
대표적인 알고리즘 패턴
| 패턴 | 설명 | 대표 문제 |
|---|---|---|
| 완전 탐색 (Brute Force) | 모든 경우의 수를 확인 | 순열, 조합 |
| 그리디 (Greedy) | 매 순간 최선의 선택 | 거스름돈, 회의실 배정 |
| 분할 정복 (Divide & Conquer) | 문제를 작게 나눠서 해결 | 병합 정렬, 퀵 정렬 |
| 동적 프로그래밍 (DP) | 하위 문제의 결과를 저장하여 재활용 | 피보나치, 배낭 문제 |
| BFS / DFS | 그래프/트리 탐색 | 미로 탐색, 연결 요소 |
| 이진 탐색 | 정렬된 데이터에서 절반씩 줄여가며 탐색 | 특정 값 찾기, 파라메트릭 서치 |
| 투 포인터 | 두 개의 포인터로 범위를 좁혀가며 탐색 | 부분합, 정렬된 배열에서의 쌍 찾기 |
알고리즘의 평가 기준
- 시간 복잡도 (Time Complexity): 실행 시간이 얼마나 걸리는가?
- 공간 복잡도 (Space Complexity): 메모리를 얼마나 사용하는가?
5. 시간 복잡도
어떤 문제를 해결할 때, 입력 크기(n)에 따라 연산 횟수가 어떻게 변하는지 나타내는 척도
왜 중요한가?
코딩테스트에서는 보통 시간 제한이 있습니다 (1~2초).
일반적으로 1초에 약 1억(10^8)번의 연산이 가능하다고 가정합니다.🔑 10⁸ ≈ 1초 법칙
코딩테스트에서 가장 중요한 감각 중 하나!
내 알고리즘의 연산 횟수가 약 10⁸(1억)을 넘으면 1초를 초과할 가능성이 높다는 뜻입니다.
이걸 어디에 쓰나요?
코드를 짜기 전에 시간 초과 여부를 미리 예측할 수 있습니다.
실전 예시
문제 조건: n ≤ 100,000 (10만), 시간 제한: 1초
❌ O(n²) 풀이 → 100,000² = 10,000,000,000 (100억) → 10⁸ 초과 → 시간 초과!
✅ O(n log n) 풀이 → 100,000 × 17 ≈ 1,700,000 (170만) → 10⁸ 이하 → 여유롭게 통과!판단하는 방법 (3단계)
1단계: 문제에서 n의 범위를 확인한다
2단계: 내 알고리즘의 Big-O에 n을 대입하여 연산 횟수를 계산한다
3단계: 연산 횟수가 10⁸ 이하인지 확인한다
→ 이하면 ✅ 통과 가능
→ 초과면 ❌ 더 빠른 알고리즘 필요언어별 속도 차이
실제로는 프로그래밍 언어에 따라 속도가 다릅니다:
| 언어 | 1초에 가능한 연산 수 | 비고 |
|---|---|---|
| C / C++ | 약 10⁸ ~ 10⁹ | 가장 빠름 |
| Java | 약 10⁷ ~ 10⁸ | C++보다 2~3배 느림 |
| Python | 약 10⁶ ~ 10⁷ | 가장 느림 |
⚠️ 그래서 같은 문제라도 Java는 C++보다 시간 제한을 2~3배 더 주는 경우가 많습니다!
Java로 코딩테스트를 볼 때는 이 점을 고려해야 합니다.
코딩테스트를 위한 시간 복잡도 — 제약조건을 보고 알고리즘 예측하기
코딩테스트 문제의 절반은 제약조건(입력값의 범위) 만 보고도 어떤 시간 복잡도로 풀어야 하는지 힌트를 얻을 수 있습니다!
| 입력 크기 (N) | 시간 복잡도 | 대표 알고리즘 | 연산 횟수 예시 |
|---|---|---|---|
| N ≤ 10 | O(N!) |
순열 완전 탐색 | 10! = 360만 ✅ |
| N ≤ 20 | O(2^N) |
재귀 완전 탐색, 비트마스킹 DP | 2²⁰ ≈ 100만 ✅ |
| N ≤ 500 | O(N³) |
3중 반복문, 플로이드-워셜 | 500³ = 1.25억 ✅ |
| N ≤ 2,000 | O(N²) |
2중 반복문(완전 탐색), 2차원 DP | 2000² = 400만 ✅ |
| N ≤ 100,000 | O(N log N) |
정렬, 우선순위 큐(Heap), 다익스트라, 이분 탐색 | 10⁵ × 17 ≈ 170만 ✅ |
| N ≤ 10,000,000 | O(N) |
1중 반복문, 해시 테이블, 투 포인터, DFS/BFS | 10⁷ ✅ |
| N ≥ 10억 | O(log N) / O(1) |
이진 탐색(탐색 범위), 수학 공식 | 30번 이하 ✅ |
보충 설명
- 플로이드-워셜
O(N³): 모든 정점 간 최단 경로. N ≤ 500일 때만 사용 가능 - 비트마스킹 DP
O(2^N): 집합의 부분집합을 비트로 표현. N ≤ 20이면 2²⁰ ≈ 100만이라 가능 - 다익스트라
O(E log V): 우선순위 큐를 사용한 최단 경로 - N ≥ 10억: 반복문 자체가 불가능 → 수학 공식이나 이진 탐색처럼 범위를 절반씩 줄이는 접근 필요
실전 사용법
1. 문제를 읽는다
2. 제약조건에서 N의 범위를 확인한다
3. 위 표에서 허용 가능한 시간 복잡도를 찾는다
4. 불가능한 알고리즘을 먼저 제거한다 ← 핵심!
5. 남은 복잡도에 맞는 알고리즘 중 문제에 적합한 것을 선택한다실전 예시: 마라톤 문제
💡 제약조건: "마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다."
Step 1 — N = 100,000 (10⁵) 확인!
Step 2 — 불가능한 알고리즘 제거:
❌ O(N²) → (10⁵)² = 10¹⁰ (100억) → TLE! 절대 안 됨
❌ O(N³) → (10⁵)³ = 10¹⁵ → TLE! 말도 안 됨
❌ O(2^N) → 2^100000 → TLE! 우주가 멸망해도 안 끝남Step 3 — 가능한 알고리즘만 남김:
✅ O(N log N) → 10⁵ × 17 ≈ 170만 → 통과! (정렬, 힙, 이분탐색)
✅ O(N) → 10⁵ = 10만 → 통과! (해시, 투포인터)
✅ O(log N) → 약 17 → 통과! (이진탐색)Step 4 — 문제 유형에 맞는 알고리즘 선택:
| 문제 유형 | 추천 알고리즘 | Big-O |
|---|---|---|
| 완주하지 못한 선수 찾기 | 해시 테이블 (HashMap) | O(N) |
| 정렬 후 비교 | 정렬 (Arrays.sort) | O(N log N) |
🎯 핵심: 제약조건을 보면 "이건 절대 안 되겠다" 를 먼저 판단하는 것이 중요합니다!
N = 100,000이면 이중 for문(O(N²))은 무조건 TLE → 다른 방법을 찾아야 합니다.
⚠️ 이 표는 절대적인 기준이 아닌 대략적인 가이드입니다. 실제로는 상수 계수나 구현 방식에 따라 달라질 수 있습니다.
6. 공간 복잡도
입력값에 따른 메모리 할당량을 계산하는 것
- 메모리는 한정적이기 때문에 최대한 적은 용량의 메모리를 사용하는 것이 좋습니다.
- 일반적으로 코딩테스트 메모리 제한은 128MB ~ 512MB 정도입니다.
- 공간 복잡도가 중요하지만, 이것까지 보는 회사는 많이 없습니다.
메모리 사용량 감 잡기
int 배열 1,000,000개 ≈ 4MB
int 배열 10,000,000개 ≈ 40MB
2차원 배열 1000 × 1000 ≈ 4MB
2차원 배열 10000 × 10000 ≈ 400MB → 💥 메모리 초과 가능!
💡 실전에서는: 공간 복잡도보다 시간 복잡도가 더 중요하게 평가되는 경우가 많습니다. 하지만 메모리 초과(MLE)로 틀리는 경우도 있으니 기본적인 감각은 필요합니다.
7. 시간 vs 공간 Trade-off
시간과 공간은 보통 trade-off(상충 관계) 입니다.
실행시간 ↓ (줄이려면) → 메모리 사용량 ↑ (늘어남)
메모리 사용량 ↓ (줄이려면) → 실행시간 ↑ (늘어남)대표적인 예시
| 상황 | 시간 우선 (메모리 더 사용) | 공간 우선 (시간 더 사용) |
|---|---|---|
| 중복 검사 | HashSet에 저장 후 검사 O(1) |
매번 리스트 순회 O(n) |
| DP | 메모이제이션 테이블 사용 | 재귀로만 계산 (중복 연산) |
| 그래프 표현 | 인접 행렬 O(V²) 공간 |
인접 리스트 O(V+E) 공간 |
8. Big-O 표기법
Big-O란?
알고리즘의 최악의 경우 성능을 표현하는 점근적 표기법입니다.
핵심 규칙
- 최고차항만 남긴다 (작은 차수 무시)
- 계수(상수)를 무시한다
Input
n의 크기가 커지면 작은 차수의 항들이 runtime에 미치는 영향이 미미해지기 때문입니다.
예제
| 원래 식 | Big-O |
|---|---|
T(n) = 2n³ + 4n² + 3n + 1 |
O(n³) |
T(n) = 17n⁴ + 4n³ + 3n + 8 |
O(n⁴) |
T(n) = 16n + log₂n |
O(n) |
T(n) = 2ⁿ + 12n⁷ + 3n |
O(2ⁿ) |
T(n) = 2n + 4n² + 3n! + 1 |
O(n!) |
Big-O 이외의 표기법 (참고)
| 표기법 | 의미 | 설명 |
|---|---|---|
Big-O O(f(n)) |
상한 (최악의 경우) | "최대 이만큼 걸린다" |
Big-Ω Ω(f(n)) |
하한 (최선의 경우) | "최소 이만큼 걸린다" |
Big-Θ Θ(f(n)) |
평균 (정확한 차수) | "대략 이만큼 걸린다" |
코딩테스트에서는 Big-O (최악의 경우) 만 사용하면 됩니다. 최악의 경우를 기준으로 시간 안에 들어오는지 판단해야 하기 때문입니다.
9. Big-O 코드 예제
O(1) — 상수 시간
입력 크기에 관계없이 항상 같은 시간
int a = 5;
a += 1;
System.out.println(a);- 배열에서 인덱스로 접근:
arr[3] - 해시 테이블에서 키로 접근:
map.get("key")
O(log n) — 로그 시간
탐색해야 되는 데이터가 절반씩 줄어드는 경우
int binarySearch(int[] data, int target) {
int start = 0;
int end = data.length - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (data[mid] == target) {
return mid; // 찾음!
} else if (data[mid] > target) {
end = mid - 1; // 왼쪽 절반만 탐색
} else {
start = mid + 1; // 오른쪽 절반만 탐색
}
}
return -1; // 못 찾음
}n = 1,000,000 일 때
→ 약 20번의 비교만으로 답을 찾을 수 있다! (log₂(1,000,000) ≈ 20)O(n) — 선형 시간
입력 크기에 비례하여 시간이 증가
for (int i = 0; i < n; i++) {
System.out.println("hi");
}- 전체 데이터를 한 번 순회하는 경우
O(n log n) — 선형 로그 시간
효율적인 정렬 알고리즘의 시간 복잡도
int[] arr = {5, 3, 8, 1, 2};
Arrays.sort(arr); // Java의 내장 정렬 = Dual-Pivot Quicksort = O(n log n)- 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort - 평균), 힙 정렬(Heap Sort)
O(n²) — 이차 시간
이중 반복문
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.println("hi");
}
}- 버블 정렬, 선택 정렬, 삽입 정렬
- 2차원 배열 전체 순회
O(2ⁿ) — 지수 시간
재귀로 모든 경우를 탐색하는 경우
int fibo(int n) {
if (n <= 1) return n;
return fibo(n - 1) + fibo(n - 2);
} fibo(5)
/ \
fibo(4) fibo(3)
/ \ / \
fibo(3) fibo(2) fibo(2) fibo(1)
/ \
fibo(2) fibo(1)
⚠️ 같은 값이 반복 계산됩니다! → DP(메모이제이션)로
O(n)으로 최적화 가능
// DP로 최적화한 피보나치 → O(n)
int fiboDp(int n) {
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}O(n!) — 팩토리얼 시간
모든 순열을 구하는 경우
// 백트래킹으로 순열 구하기 → n!
void permutation(int[] arr, int depth, int n) {
if (depth == n) {
System.out.println(Arrays.toString(arr));
return;
}
for (int i = depth; i < n; i++) {
swap(arr, depth, i);
permutation(arr, depth + 1, n);
swap(arr, depth, i); // 원상 복구
}
}
// 4! = 24개10. 복잡도 비교 & 실전 감각
🏆 복잡도 순위 (빠른 순)
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)
↑ ↑
최고 최악📈 n에 따른 연산 횟수 비교
| Big-O | n=10 | n=100 | n=1,000 | n=10,000 |
|---|---|---|---|---|
O(1) |
1 | 1 | 1 | 1 |
O(log n) |
3 | 7 | 10 | 13 |
O(n) |
10 | 100 | 1,000 | 10,000 |
O(n log n) |
30 | 700 | 10,000 | 130,000 |
O(n²) |
100 | 10,000 | 1,000,000 | 100,000,000 |
O(2ⁿ) |
1,024 | 1.27 × 10³⁰ | 💥 | 💥 |
O(n!) |
3,628,800 | 💥 | 💥 | 💥 |
💡
n=20정도만 되어도2ⁿ은 약 100만,20!은 약 2.4 × 10¹⁸ → 사실상 계산 불가능
실전 판단 요령
문제를 읽고 n의 범위를 확인한다
→ 위 표를 참고하여 허용 가능한 시간 복잡도를 추정한다
→ 해당 복잡도에 맞는 알고리즘을 선택한다예시:
n ≤ 1,000,000→O(n log n)이하 알고리즘 필요 → 정렬, 이진 탐색 등n ≤ 10,000→O(n²)가능 → 이중 루프 OKn ≤ 20→O(2ⁿ)가능 → 완전 탐색(백트래킹) 고려
11. 코딩테스트에서 자주 쓰이는 자료구조-알고리즘 맵핑
| 문제 유형 | 자료구조 | 알고리즘 | 시간 복잡도 |
|---|---|---|---|
| 최단 경로 (가중치 有) | 우선순위 큐 | 다익스트라 | O(E log V) |
| 최단 경로 (가중치 無) | 큐 | BFS | O(V + E) |
| 연결 요소 / 경로 탐색 | 스택 / 재귀 | DFS | O(V + E) |
| 정렬 | 배열 | 정렬 알고리즘 | O(n log n) |
| 빠른 검색 / 중복 확인 | 해시 테이블 | 해싱 | O(1) 평균 |
| 구간 합 / 최적 부분 구조 | 배열 / 테이블 | DP | 문제마다 다름 |
| 부분합 / 연속 구간 | 배열 | 투 포인터 / 슬라이딩 윈도우 | O(n) |
| 서로소 집합 / 사이클 판별 | 배열 (부모) | Union-Find | O(α(n)) ≈ O(1) |
12. 실전 팁 & 자주 하는 실수
✅ 꼭 기억할 것
ArrayList.remove(0)은O(n)이다! → 큐가 필요하면LinkedList또는ArrayDeque사용List.contains()는O(n)→ 빠른 검색이 필요하면HashSet이나HashMap사용O(1)- 입력 속도:
Scanner대신BufferedReader사용 (대량 입력 시 필수!) String연결은StringBuilder사용 → 반복문에서+연산은O(n²)이 될 수 있음int범위 주의:int는 약 21억까지 → 더 큰 수는long사용
// Scanner (느림)
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
// BufferedReader (빠름) ← 코딩테스트에서 추천!
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());❌ 자주 하는 실수
| 실수 | 결과 | 해결 |
|---|---|---|
List.contains() 반복 사용 |
시간 초과 (TLE) | HashSet으로 변환 후 사용 |
Scanner 사용 (대량 입력) |
시간 초과 (TLE) | BufferedReader 사용 |
반복문에서 String + 연결 |
시간 초과 (TLE) | StringBuilder 사용 |
int 오버플로우 |
오답 (WA) | long 타입 사용 |
O(n²) 풀이로 큰 n 처리 |
시간 초과 (TLE) | 더 효율적인 알고리즘 탐색 |
🔧 Java 코딩테스트 기본 템플릿
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
// 여기서부터 풀이 시작
// 한 줄에 하나의 값 읽기
int n = Integer.parseInt(br.readLine());
// 공백으로 구분된 여러 값 읽기
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
// 출력 (StringBuilder에 모아서 한번에 출력)
sb.append(a + b).append("\n");
System.out.print(sb);
}
}🧩 QUIZ 1 — Big-O 판별 & 시간 초과 예측
📋 문제
다음 코드의 Big-O 표기법은 무엇일까요?
그리고 제약조건이 1 ≤ n ≤ 10⁵ 일 때, 시간 초과가 날까요?
int solution(int n) {
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
count++;
}
}
return count;
}🔍 정답 보기 (클릭)
① Big-O 분석
안쪽 루프가 j = i 부터 시작하므로, 반복 횟수는 다음과 같습니다:
i=0 → n번
i=1 → n-1번
i=2 → n-2번
...
i=n-1 → 1번
합계 = n + (n-1) + (n-2) + ... + 1 = n(n+1)/2n(n+1)/2 = (n² + n) / 2
Big-O 규칙 적용:
- 최고차항만 남긴다 → n²
- 계수
/2무시
✅ 정답: O(n²)
② 시간 초과 여부
제약조건: 1 ≤ n ≤ 10⁵
Worst Case: n = 10⁵
→ n² = (10⁵)² = 10¹⁰ (100억)
→ 10¹⁰ >> 10⁸ (1억)
→ 약 100초 소요 예상
❌ 시간 초과 (TLE) 발생! 100억 연산은 10⁸ 기준의 100배이므로 시간 제한 안에 절대 통과할 수 없습니다.
③ 그렇다면 어떻게 풀어야 할까?
사실 이 코드의 count 값은 수학 공식으로 바로 구할 수 있습니다:
int solution(int n) {
return n * (n + 1) / 2; // O(1) — 상수 시간!
}| 풀이 | Big-O | n=10⁵ 연산 횟수 | 결과 |
|---|---|---|---|
| 이중 for문 | O(n²) |
10¹⁰ (100억) | ❌ TLE |
| 수학 공식 | O(1) |
1 | ✅ 통과 |
💡 교훈: 같은 문제라도 접근 방식에 따라
O(n²)→O(1)까지 줄일 수 있습니다!
🧩 QUIZ 2 — 상수 루프 vs 입력 의존 루프
📋 문제
다음 코드의 Big-O 표기법은 무엇일까요?
제약조건:
- 배열
arr의 길이m:1 ≤ m ≤ 10⁴ - 배열 각 원소
arr[i]의 크기n:1 ≤ n ≤ 10⁵
int solution(int arr[]) {
for (int i = 0; i < 10; i++) {
for (int num : arr) {
System.out.println(num);
}
}
}🔍 정답 보기 (클릭)
① Big-O 분석
| 루프 | 반복 횟수 | 입력에 의존? |
|---|---|---|
바깥 for (i < 10) |
10번 | ❌ 고정값 (상수) |
안쪽 for-each |
m번 | ✅ arr 길이에 의존 |
총 연산 = 10 × m = 10m
Big-O 규칙: 계수 무시 → 10m → O(m)
✅ 정답: O(m)
② "n은 어디 갔지?"
제약조건에 n(원소의 크기)이 있지만, 이 코드에서는 값을 출력만 하고 있습니다.
원소의 값이 크든 작든 System.out.println(num) 은 O(1) 이므로 n은 시간 복잡도에 영향을 주지 않습니다.
만약 n이 영향을 주려면 이런 식이어야 합니다:
// 이 경우는 O(m × n)
for (int num : arr) { // m번
for (int j = 0; j < num; j++) { // 최대 n번 (원소 값만큼 반복)
System.out.println(j);
}
}③ 시간 초과 여부
m = 10⁴, O(m) → 10⁴ (1만) → 10⁸보다 훨씬 작음 → ✅ 여유롭게 통과!
💡 교훈: 고정된 숫자(상수)로 도는 루프는 Big-O에서 무시합니다!
제약조건에 있는 변수가 실제 코드에서 어떻게 사용되는지 잘 확인해야 합니다.
🧩 QUIZ 3 — for문 안의 while문
� 문제
다음 코드의 Big-O 표기법은? 그리고 제약조건 1 ≤ n ≤ 10⁵ 에서 시간 초과가 날까요?
int solution(int n) {
for (int i = 0; i < n; i++) {
int j = 0;
while (j < n) {
j++;
}
}
}🔍 정답 보기 (클릭)
① Big-O 분석
핵심은 int j = 0; 이 for문 안에 있다는 점입니다!
for (int i = 0; i < n; i++) { // n번 반복
int j = 0; // ⚠️ 매번 j를 0으로 초기화!
while (j < n) { // → 매번 n번 반복
j++;
}
}| 루프 | 반복 횟수 | 설명 |
|---|---|---|
바깥 for |
n번 | i가 0부터 n-1까지 |
안쪽 while |
n번 | 매번 j=0에서 시작하므로 항상 n번 |
총 연산 = n × n = n²
✅ 정답: O(n²)
② 만약 j가 바깥에 선언되어 있다면?
int solution(int n) {
int j = 0; // ⚠️ 바깥에서 한 번만 초기화
for (int i = 0; i < n; i++) {
while (j < n) {
j++;
}
}
}이 경우 while문은 i=0일 때 한 번만 실행되고, 이후로는 j가 이미 n이라 실행되지 않습니다.
→ 총 연산 = n(for) + n(while) = 2n → O(n)
💡 교훈: 변수의 선언 위치(초기화 위치) 하나로
O(n²)↔O(n)이 바뀔 수 있습니다!
③ 시간 초과 여부
n = 10⁵, O(n²) → (10⁵)² = 10¹⁰ (100억) → 10⁸ 초과 → ❌ 시간 초과!🧩 QUIZ 4 — Quiz 3의 함정 변형! j의 선언 위치
📋 문제
Quiz 3과 거의 같은 코드인데, 딱 한 줄이 다릅니다. Big-O는 무엇일까요?
제약조건: 1 ≤ n ≤ 10⁵
int solution(int n) {
int j = 0; // ⚠️ 여기!
for (int i = 0; i < n; i++) {
while (j < n) {
j++;
}
}
}🔍 정답 보기 (클릭)
① Big-O 분석
Quiz 3과의 차이: int j = 0;이 for문 바깥에 있습니다!
i=0일 때: j가 0 → while문 실행 → j가 0에서 n까지 증가 (n번 실행)
i=1일 때: j가 이미 n → while 조건 불만족 → 실행 안 됨 (0번)
i=2일 때: j가 이미 n → 실행 안 됨 (0번)
...
i=n-1일 때: 실행 안 됨 (0번)| 루프 | 총 실행 횟수 |
|---|---|
for |
n번 (i를 증가시키는 것) |
while |
전체에서 딱 n번 (j는 0→n까지 한 번만 증가) |
총 연산 = n(for) + n(while) = 2n
Big-O: 계수 무시 → O(n)
✅ 정답: O(n)
② Quiz 3 vs Quiz 4 비교
// Quiz 3: O(n²) — j가 매번 초기화됨
for (int i = 0; i < n; i++) {
int j = 0; // ← 안쪽에서 매번 초기화
while (j < n) { j++; }
}
// Quiz 4: O(n) — j가 한 번만 초기화됨
int j = 0; // ← 바깥에서 한 번만 초기화
for (int i = 0; i < n; i++) {
while (j < n) { j++; }
}| 항목 | Quiz 3 | Quiz 4 |
|---|---|---|
j 선언 위치 |
for문 안 | for문 밖 |
| while 실행 횟수 | 매번 n번 | 전체에서 n번 |
| Big-O | O(n²) | O(n) |
③ 시간 초과 여부
n = 10⁵, O(n) → 10⁵ (10만) → 10⁸보다 훨씬 작음 → ✅ 여유롭게 통과!
💡 교훈: 코드가 비슷해 보여도 변수 초기화 위치 하나로 시간 복잡도가 완전히 달라집니다. 코딩테스트에서 자주 나오는 함정이니 꼭 주의하세요!
🧩 QUIZ 5 — j *= 2 는 무엇을 의미할까?
📋 문제
다음 코드의 Big-O 표기법은? 제약조건 1 ≤ n ≤ 10³ 에서 시간 초과가 날까요?
int solution(int n) {
for (int i = 0; i < n; i++) {
int j = 1;
while (j < n) {
j *= 2;
}
}
}🔍 정답 보기 (클릭)
① Big-O 분석
핵심은 j *= 2 — j가 1씩 증가가 아니라 2배씩 커진다는 점!
j의 변화: 1 → 2 → 4 → 8 → 16 → 32 → ... → n 이상이 되면 종료j = 2^k 이고, 2^k ≥ n 일 때 멈추므로 → k = log₂(n)번 반복
예시) n = 1000일 때:
1 → 2 → 4 → 8 → 16 → 32 → 64 → 128 → 256 → 512 → 1024 (종료)
→ 약 10번만에 끝! (log₂(1000) ≈ 10)| 루프 | 반복 횟수 |
|---|---|
바깥 for |
n번 |
안쪽 while |
log₂(n)번 (2배씩 증가하니까) |
총 연산 = n × log n
✅ 정답: O(n log n)
② j++ vs j *= 2 비교
| 코드 | while 반복 횟수 | Big-O (for문 포함) |
|---|---|---|
j++ (1씩 증가) |
n번 | O(n²) |
j *= 2 (2배씩 증가) |
log n번 | O(n log n) |
j *= 3 (3배씩 증가) |
log₃n번 | O(n log n) |
💡 곱하기로 증가하면 log, 더하기로 증가하면 선형!
③ 시간 초과 여부
n = 10³, O(n log n) → 1000 × 10 = 10,000 → 10⁸보다 훨씬 작음 → ✅ 여유롭게 통과!
💡 교훈:
j *= 2처럼 배수로 증가/감소하는 패턴은log n입니다.
이것이 바로 이진 탐색이 O(log n)인 이유와 같습니다! (탐색 범위가 절반씩 줄어들기 때문)
🧩 QUIZ 6 — Quiz 5의 함정 변형! j *= 2 + 바깥 선언
📋 문제
Quiz 5와 거의 같은 코드인데, j의 선언 위치가 다릅니다. Big-O는?
제약조건: 1 ≤ n ≤ 10³
int solution(int n) {
int j = 1; // ⚠️ 바깥에서 선언!
for (int i = 0; i < n; i++) {
while (j < n) {
j *= 2;
}
}
}🔍 정답 보기 (클릭)
① Big-O 분석
Quiz 3→4와 같은 원리! j가 for문 바깥에 선언되어 있으므로:
i=0일 때: j=1 → while 실행 → j가 1→2→4→8→...→n 이상 (log n번 실행)
i=1일 때: j가 이미 n 이상 → while 실행 안 됨 (0번)
i=2일 때: 실행 안 됨 (0번)
...
i=n-1일 때: 실행 안 됨 (0번)| 루프 | 총 실행 횟수 |
|---|---|
for |
n번 |
while |
전체에서 딱 log n번 (첫 번째 i에서만) |
총 연산 = n + log n
Big-O: n > log n 이므로 → O(n)
✅ 정답: O(n)
② Quiz 5 vs Quiz 6 비교
| 항목 | Quiz 5 | Quiz 6 |
|---|---|---|
j 선언 위치 |
for문 안 (int j = 1;) |
for문 밖 (int j = 1;) |
| while 실행 | 매번 log n번 | 전체에서 log n번 (1회만) |
| Big-O | O(n log n) | O(n) |
③ 시간 초과 여부
n = 10³, O(n) → 1,000 → 10⁸보다 훨씬 작음 → ✅ 여유롭게 통과!
💡 교훈: Quiz 3→4, Quiz 5→6 모두 같은 패턴! 변수 초기화 위치가 복잡도를 결정합니다.
📝 Part 1 핵심 정리
1. 자료구조 = 데이터를 저장/관리하는 방식 → 알고리즘 선택에 직결
2. 선형(배열, 스택, 큐, 리스트) vs 비선형(트리, 그래프, 해시)
3. 시간 복잡도 > 공간 복잡도 (중요도)
4. Big-O = 최고차항만, 계수 무시
5. O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
6. 문제의 n 범위를 보고 허용 가능한 복잡도를 역산한다!
📚 다음 파트 예고: 주요 알고리즘 패턴 (완전 탐색, 정렬, 재귀, BFS/DFS) 상세 학습