[APP] 3일차: 알고리즘 기초 - 문제를 푸는 절차를 설계하다

Computational Thinking으로 “어떻게 생각할 것인가”를 배웠고, 자료구조로 “어떻게 담을 것인가”를 배웠다면, 오늘은 “어떻게 효율적으로 처리할 것인가”를 배우는 날이었다. 알고리즘은 단순한 ‘문제 푸는 방법’이 아니라 **“최적의 절차를 설계하는 능력”**이라는 걸 깨달았다.

오늘 다룬 범위

• 알고리즘의 정의와 중요성
• 정렬 알고리즘: 선택 정렬, 삽입 정렬, 버블 정렬, 퀵 정렬, 병합 정렬
• 시간 복잡도(Time Complexity): Big O 표기법
• 공간 복잡도(Space Complexity)
• Divide and Conquer 기법

핵심 개념 정리

알고리즘이란?

강사님은 이렇게 정의했다:

“문제를 풀기 위한 단계별 절차. 정확성도 중요하지만, 효율성이 더 중요하다.”

100개 숫자를 정렬하는 데 버블 정렬을 쓰나 퀵 정렬을 쓰나 결과는 같다. 하지만 1백만 개를 정렬한다면? 버블 정렬은 몇 시간이 걸리지만 퀵 정렬은 몇 초에 끝난다.

“정확한 답을 구하는 것”과 “정확하면서도 빠르게 구하는 것”은 완전히 다르다.

정렬 알고리즘 비교

1. 선택 정렬(Selection Sort)

• 가장 작은 값을 찾아서 앞으로 옮기는 방식
• 시간복잡도: O(n²)
• 가장 이해하기 쉽지만 가장 느리다

2. 삽입 정렬(Insertion Sort)

• 카드를 정렬하듯이 한 개씩 끼워 넣는 방식
• 시간복잡도: O(n²)
• 이미 정렬된 데이터에는 O(n)까지 빨라진다

3. 버블 정렬(Bubble Sort)

• 옆의 값과 비교해서 크면 자리를 바꾸기를 반복
• 시간복잡도: O(n²)
• 실제로는 잘 안 쓰인다

4. 퀵 정렬(Quick Sort)

• Pivot(기준값)을 정하고 작은 값들과 큰 값들로 분할
• 시간복잡도: O(n log n) (평균), O(n²) (최악)
• 가장 많이 쓰이는 정렬

5. 병합 정렬(Merge Sort)

• 반으로 계속 나눈 후 다시 병합하는 방식
• 시간복잡도: O(n log n) (항상)
• 안정적이지만 O(n) 추가 공간 필요

시간 복잡도 - Big O 표기법

이건 정말 중요한 개념이다. 코드를 짤 때마다 “이 코드는 몇 번 반복될까?”를 생각해야 한다.

O(1)       → 1번
O(log n)   → 로그 번
O(n)       → n번
O(n log n) → n * 로그 n번
O(n²)      → n * n번
O(2ⁿ)      → 지수적 (피해야 함)
O(n!)      → 팩토리얼 (절대 피해야 함)

n = 1,000,000일 때:

• O(n): 1백만 번
• O(n log n): 약 2천만 번
• O(n²): 1조 번 (컴퓨터가 수십 초 걸림)

작은 수에서는 차이가 안 보이지만, 데이터가 많아질수록 극적으로 차이가 난다.

헷갈렸던 점 / 실수 포인트

”왜 정렬 알고리즘을 이렇게 많이 배우나?”

처음엔 이 생각을 했다. “정렬은 라이브러리에서 제공하는데 왜 일일이 구현을 배우지?”

그런데 강사님이 하신 말이 깨달음을 줬다:

“정렬 알고리즘을 배우는 건 정렬이 목표가 아니라, ‘같은 문제를 푸는데 여러 방법이 있고, 각 방법의 장단점을 이해하는 연습’이기 때문이다.”

정렬뿐만 아니라 모든 알고리즘이 그렇다. 같은 문제를 푸는 여러 방법 중에 상황에 맞는 최선의 방법을 고를 수 있어야 한다.

”Divide and Conquer가 뭔 대단한 거야?”

퀵 정렬을 배우면서 처음 본 개념이 **“분할 정복(Divide and Conquer)“**이었다.

• 분할: 큰 문제를 작은 부분 문제로 나눈다
• 정복: 작은 문제를 푼다
• 결합: 작은 답들을 합쳐서 큰 답을 만든다

처음엔 단순해 보였지만, 강사님의 설명 후 깨달았다. 이건 “불가능해 보이는 큰 문제를 어떻게 풀 것인가”의 일반적인 전략이라는 뜻이다.

병합 정렬도, 퀵 정렬도, 이진 탐색도, 심지어 이진 트리 탐색도 모두 이 원리를 따른다. 패턴이 있다.

복습 Q&A

# O(n²)
for i in range(n):
    for j in range(n):
        print(i, j)  # n * n번 실행

# O(n log n)
# 퀵 정렬: 반으로 나누기(log n) × 각 단계마다 모든 원소 처리(n)

한 줄 정리

좋은 알고리즘은 결과가 같아도 훨씬 적은 단계로 도달한다. 데이터가 많을수록 이 차이는 초와 분의 차이, 나아가 가능과 불가능의 차이가 된다.

내일은 개발 도구를 배운다. 지금까지는 순수 논리(CT, 자료구조, 알고리즘)를 배웠다면, 내일부터는 이걸 코드로 구현하는 실전 도구들을 배우게 될 것 같다.