[전산직(데이터) 공무원 대비] 알고리즘 기초부터 파헤치기 1

전공자에게도 익숙하지만, 막상 시험 문제로 마주하면 헷갈리고 자꾸 잊어버리는 게 바로 '기초'인 것 같다.

오늘부터 공무원 시험(전산직)을 준비하면서 기초를 탄탄하게 다시 정리해 보는 시간을 가지려 한다.

 

빠르게 제미나이의 도움을 받아 이론을 요약하고, 기초부터 심화 문제까지 풀어보며

이론을 머리 속에 콕 박아놓고 시험장까지 가져가자.

 

오늘은 그 첫 번째 순서, 알고리즘의 기초 중의 기초인 '알고리즘 분석(Algorithm Analysis)'이다.

실제 시험에서는 코드를 보고 실행 시간을 예측하거나, 점근적 표기법의 수학적 정의를 묻는 문제로 출제된다.

 

1. 알고리즘 특성

(1) 알고리즘의 5대 특성 (암기)

1. 입력(Input): 0개 이상의 외부 입력이 있어야 함. (꼭 1개 이상일 필요 없음, 0개여도 됨!)
2. 출력 (Output): 적어도 1개 이상의 결과가 나와야 함.
3. 명확성 (Definiteness): 각 명령어는 모호하지 않고 명확해야 함.
4. 유한성 (Finiteness): 한정된 단계를 거친 후에는 반드시 종료해야 함. (무한 루프는 알고리즘이 아님)
5. 유효성 (Effectiveness): 모든 명령은 실행 가능해야 함.

(2) 알고리즘 기술 방법

 

• 순서도(Flowchart), 의사 코드(Pseudo-code), 자연어 등은 사용 가능.
• 주의: 추상 데이터 타입(Abstract Data Type)은 데이터의 '구조와 연산'을 정의하는 논리적 개념이지, 알고리즘(문제 해결 절차)을 기술하는 방법이 아닙니다.

 

2. 알고리즘 분석 (Time Complexity)

알고리즘의 성능은 단순한 '실행 시간(초, sec)'이 아니다.

입력 크기($n$)가 커질 때 연산 횟수가 어떻게 증가하는가를 측정하는 것이 핵심이다.

(1) 점근적 표기법 (Asymptotic Notation) - 3대장

시험에 단골로 등장하는 3가지 표기법의 정의와 의미를 정확히 구분해야 한다.

1. 빅오 표기법 ($O$, Big-O): 최악의 경우 (상한선)
   • 실무와 시험에서 가장 많이 사용
   • 정의: $n \ge n_0$인 모든 $n$에 대해 $f(n) \le c \cdot g(n)$을 만족하는 양의 상수 $c, n_0$가 존재하면 $f(n) = O(g(n))$이다.
   • 의미: "아무리 운이 나빠도, 즉 최악의 경우라도 $g(n)$ 정도의 속도는 보장한다." ($\le$)
2. 빅오메가 표기법 ($\Omega$, Big-Omega): 최선의 경우 (하한선)
   • 정의: $f(n) \ge c \cdot g(n)$
   • 의미: "아무리 운이 좋아도, 최소한 $g(n)$ 시간은 걸린다." ($\ge$)
3. 빅세타 표기법 ($\Theta$, Big-Theta): 평균 (정확한 구간)
   • 정의: $c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n)$
   • 의미: $f(n)$이 $g(n)$과 동일한 증가율을 보인다. (상한과 하한이 맞물릴 때)

(2) 시간 복잡도 계산 요령 (시험용 Speed Up)

복잡한 수식이 나와도 당황하지 말자. 다음 3가지 규칙만 기억하면 문제의 90%는 풀린다.

1. 최고차항만 남긴다: $3n^2 + 100n + 5 \rightarrow$ $O(n^2)$
2. 계수(상수)는 무시한다: $O(2n) \rightarrow$ $O(n)$
3. 로그의 밑은 무시한다: $log_2 n$이든 $log_{10} n$이든 그냥 $O(\log n)$으로 통일.

(3) 반드시 암기해야 할 성능 순서 📌 (빠름 $\rightarrow$ 느림)

시험 직전 1초 컷을 위해 이 순서는 머리에 콕 박아두자.

$$O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)$$

표기	대표 예시	비고
$O(1)$	배열 인덱스 접근, 스택 Push/Pop	상수 시간 (즉시)
$O(\log n)$	이진 탐색 (Binary Search)	반씩 쪼개기
$O(n)$	for문 1개 (순차 탐색)	선형 시간
$O(n \log n)$	퀵, 병합, 힙 정렬	고급 정렬 알고리즘
$O(n^2)$	이중 for문, 버블/삽입/선택 정렬	제곱 시간
$O(2^n)$	피보나치(재귀), 하노이 탑	지수 시간 (비효울의 끝판왕

(4) [비교 심화] 재귀 vs 반복 (피보나치 수열)

같은 문제라도 구현 방식에 따라 천지 차이가 난다.

• 단순 재귀 (Naive Recursion): $O(2^n)$
  • 동일한 하위 문제를 끊임없이 중복 호출함. ($fib(3)$을 구하기 위해 $fib(2)$를 또 계산...)
• 반복문 / 동적계획법 (DP): $O(n)$
  • 계산한 값을 배열에 저장(Memoization)하거나, for문을 사용하여 중복을 제거함. 성능이 대폭 개선됨.

 

3. 복잡도 종류 (Complexity Classes: P vs NP)

(1) 핵심 정의

• P (Polynomial): 다항 시간($O(n^k)$) 내에 해를 '구할(Solve)' 수 있는 문제. (쉬운 문제)
  • 예: 정렬, 검색, 최단 경로(다익스트라)
• NP (Non-deterministic Polynomial): 다항 시간 내에 주어진 해가 맞는지 '검증(Verify)'할 수 있는 문제.
  • 주의: '못 푸는 문제'가 아님! 답을 찍어서 주면 확인은 빨리 할 수 있다는 뜻.
• NP-Complete (NP-완전): NP 중에서 가장 어려운 문제들.
  • 모든 NP 문제는 다항 시간 내에 NP-완전 문제로 환원(Reduction) 가능하다.
• NP-Hard (NP-하드): NP-완전보다 같거나 더 어려운 문제. (NP에 포함될 수도, 안 될 수도 있음)

(2) 포함 관계 (벤 다이어그램 암기)

• $P \subseteq NP$ (P는 NP의 부분집합이다)
• $NP\text{-Complete} = NP \cap NP\text{-Hard}$ (교집합)

(3) [심화] 대표적인 NP-Complete 문제 (암기)

시험에서 "다음 중 성격이 다른 문제는?" 하고 P 문제들 사이에 끼워 냅니다.

• TSP (Traveling Salesperson Problem, 외판원 순회 문제)
  • 여러 도시와 각 도시간 이동 비용이 주어졌을 때, 모든 도시를 한 번씩 방문하고 돌아오는 최단 경로 찾기. ($O(n!)$)
  • 최적해(가장 짧은 거리)를 구하는 문제는 NP-하드 문제이고,
    거리 K이하인 경로가 있는가?라고 묻는 문제는 NP-완전 문제다.
• SAT (Boolean Satisfiability Problem, 충족 가능성 문제)
  • 논리식을 True로 만드는 변수 조합 찾기. (최초의 NP-Complete 문제, 쿡의 정리로 증명됨)
  • 모든 NP 문제는 이 SAT 문제로 환원(변형)될 수 있다.
• Knapsack (배낭 문제): 가방 무게 제한 내에서 가치 최대화하기. (0/1 배낭 문제)
• Hamiltonian Cycle: 그래프의 모든 정점을 한 번씩 방문하는 경로 찾기.
• 반면, '최단 경로', '최소 신장 트리(MST)', '정렬'은 P 문제임.

 

4. 실전 코드 분석 (기출 패턴)

단순한 for문은 누구나 푼다. 가장 많이 실수하는 함정 유형 2가지를 정리했다.

Case A: 반복문 변수가 배수로 증가할 때 ($+1$이 아님)

// i가 1부터 시작해서 2배씩 커짐 (1, 2, 4, 8 ...)
for (int i = 1; i < n; i = i * 2) {
    sum++;
}

• 분석: $i$가 $1, 2, 4, 8, \dots, 2^k$ 형태로 증가하여 $n$에 도달한다.
• 계산: $2^k \approx n$ 이므로, 횟수 $k \approx \log_2 n$이다.
• 정답: $O(\log n)$

Case B: 종속적인 이중 반복문

for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) { // j가 n이 아니라 i까지 반복
        sum++;
    }
}

• 분석: 바깥 루프는 $0$부터 $n-1$까지, 안쪽 루프는 $i$번($0, 1, 2, \dots, n-1$) 실행된다.
• 계산: 총 횟수는 $1 + 2 + \dots + (n-1) = \frac{n(n-1)}{2}$ (등차수열의 합)
• 정답: $O(n^2)$ (최고차항 기준)

5. 최신 기출 맛보기

문제 1. 점근적 표기법의 정의

다음 설명의 (가), (나)에 들어갈 내용은?

"모든 $n \ge n_0$에 대해 $0 \le c_1 g(n) \le f(n) \le c_2 g(n)$을 만족하는 양의 상수가 존재하면, $f(n) = ( \text{가} )$이다. 이를 $( \text{나} )$ 표기법이라 한다."

1. (가) $\Theta(g(n))$  (나) 빅세타
2. (가) $O(g(n))$  (나) 빅오
3. (가) $\Omega(g(n))$  (나) 빅오메가
4. (가) $o(g(n))$  (나) 리틀오

정답: 1번

$c_1 g(n)$(하한)과 $c_2 g(n)$(상한) 사이에 끼어있는 '샌드위치($\le f(n) \le$)' 형태는 빅세타($\Theta$)의 정의이다.

문제 2. 재귀 함수의 시간 복잡도 (하노이 탑)

다음 하노이 탑(Tower of Hanoi) 알고리즘의 시간 복잡도는? (원판 개수: $n$)

void hanoi(int n, char from, char to, char aux) {
    if (n == 1) { move(from, to); return; }
    hanoi(n - 1, from, aux, to);
    move(from, to);
    hanoi(n - 1, aux, to, from);
}

1. $O(\log n)$
2. $O(n)$
3. $O(n \log n)$
4. $O(2^n)$

정답: 4번

하노이 탑은 대표적인 지수 시간(Exponential Time) 알고리즘이다.

• 점화식: $T(n) = 2T(n-1) + 1$ (원판 $n$개를 옮기려면, $n-1$개를 2번 옮겨야 함)
• 결과: $2^n - 1$회 이동 $\rightarrow$ $O(2^n)$
• 🚨 [오답 노트] 병합 정렬과 헷갈리지 말 것! (또 틀림..)
  • 병합 정렬: $T(n) = 2T(n/2) + n$ $\rightarrow$ 문제를 절반($n/2$)으로 쪼갬 $\rightarrow$ $O(n \log n)$
  • 하노이 탑: $T(n) = 2T(n-1) + 1$ $\rightarrow$ 문제를 하나($n-1$)만 줄여서 2번 호출 $\rightarrow$ $O(2^n)$
  • (절반으로 줄어드는 것과 하나씩 줄어드는 것은 천지 차이다!)

•  

[특별 보충] 점화식 완전 정복 (마스터 정리)

심화 문제를 위해 재귀 알고리즘 시간 복잡도 $T(n)$을 구하는 3가지 패턴을 정리했다. 이것만 알면 복잡한 점화식도 3초 만에 풀 수 있다.

1. 마스터 정리 (Master Theorem)

• 형태: $T(n) = aT(n/b) + f(n)$
  • 문제를 $b$등분 하고, $a$번 호출하며, 합치는 비용이 $f(n)$일 때
• 비교: $\bf n^{\log_b a}$ (재귀 비용) vs $\bf f(n)$ (병합 비용)

Case	상황	시간 복잡도	예시
Case 1	재귀 비용이 클 때 ($>$)	$O(n^{\log_b a})$	$T(n) = 4T(n/2) + n \rightarrow O(n^2)$
Case 2	둘이 비등할 때 ($=$)	$O(n^{\log_b a} \log n)$	$T(n) = 2T(n/2) + n \rightarrow O(n \log n)$
Case 3	병합 비용이 클 때 ($<$)	$O(f(n))$	$T(n) = T(n/2) + n^2 \rightarrow O(n^2)$

2. 감소하는 점화식 (Decrease & Conquer)

• 형태: $T(n) = T(n-1) + C$
• 매번 1씩 줄어들면서 반복 $\rightarrow$ $O(n)$
• 예: $T(n) = T(n-1) + n \rightarrow O(n^2)$ (1부터 $n$까지의 합)

3. 지수적 증가

• 형태: $T(n) = 2T(n-1) + 1$
• 문제가 줄지 않고 2배로 증식 $\rightarrow$ $O(2^n)$ (하노이 탑, 피보나치)

 

👉 더 많은 문제를 풀어보고 싶다면?

제미나이가 만든 [점화식 집중 훈련 퀴즈 풀어보기](https://gemini.google.com/share/6e71fbe6b0f5))

다음 포스팅에서는 배열(Array)과 연결 리스트(Linked List), 스택(Stack)과 큐(Queue)를 정리해 보겠다.