정렬 알고리즘과 핵심 패러다임

버블·삽입·퀵 정렬, 검색 알고리즘, Brute Force·분할정복·백트래킹·DP·재귀

버블 정렬과 삽입 정렬의 동작 원리와 O(n²) 복잡도를 분석하고, 실무 표준인 퀵 정렬의 분할-정복 구조를 코드와 함께 이해한다. 선형/이진/해시 검색 알고리즘을 비교하고, Brute Force, 분할-정복, 백트래킹, 동적 계획법, 재귀 5가지 알고리즘 패러다임의 설계 철학과 적용 맥락을 심층 분석한다.

Engineering
Python
Algorithm
저자

Kwangmin Kim

공개

2025년 02월 21일

1 정렬 알고리즘이란

정렬 알고리즘: 주어진 데이터 목록을 정해진 순서(오름차순 또는 내림차순)로 재배열하는 알고리즘

  • 컴퓨터 과학에서 가장 기본적이면서도 중요한 연산 중 하나
  • 이진 탐색(O(log n))처럼 많은 효율적인 알고리즘들이 “데이터가 정렬되어 있다”는 전제 위에서 동작
  • 정렬이 되어 있지 않으면 O(log n) 탐색도, 효율적인 병합도 불가능

이번 파트에서 다루는 정렬 알고리즘:

알고리즘 시간 복잡도 특징
버블 정렬 O(n²) 구현 단순, 교육적 가치
삽입 정렬 O(n²) ~ O(n) 거의 정렬된 데이터에서 유리
퀵 정렬 (Part 5) O(n log n) 평균 실무 표준
합병 정렬 (참고) O(n log n) 안정 정렬

2 버블 정렬 (Bubble Sort)

2.1 동작 원리

버블 정렬: 무거운 거품이 수면 위로 떠오르듯, 큰 원소가 매 패스(pass)마다 배열의 오른쪽 끝으로 이동하는 정렬 방식

동작 단계:

  1. 배열의 첫 번째 원소부터 시작해 인접한 두 원소를 비교
  2. 앞의 원소가 뒤의 원소보다 크면 두 원소의 위치를 교환(swap)
  3. 이 비교-교환 과정을 배열 끝까지 반복 → 한 번의 전체 순회 = “1 패스(pass)”
  4. 1 패스 완료 시 배열에서 가장 큰 원소가 맨 오른쪽에 확정 → 다음 패스에서 제외
  5. 모든 원소가 정렬될 때까지 패스 반복

예시: [5, 3, 8, 1] 오름차순 정렬

패스 비교 결과 확정
1패스 (5,3)→교환, (5,8)→유지, (8,1)→교환 [3, 5, 1, 8] 8 확정
2패스 (3,5)→유지, (5,1)→교환 [3, 1, 5, 8] 5 확정
3패스 (3,1)→교환 [1, 3, 5, 8] 정렬 완성
노트

n개의 원소를 정렬하려면 최대 n-1번의 패스가 필요하다.

2.2 코드 분석

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):              # 패스 횟수: n번
        # 매 패스에서 가장 큰 원소가 맨 뒤로 이동하므로,
        # 마지막 i개의 원소는 이미 정렬되어 있음
        for j in range(0, n - i - 1):  # 비교 범위를 점점 줄임
            if arr[j] > arr[j + 1]:    # 앞이 뒤보다 크면
                arr[j], arr[j + 1] = arr[j + 1], arr[j]  # 교환

코드 포인트:

코드 설명
for i in range(n) n번의 패스 수행
range(0, n - i - 1) n-i-1이 핵심 — 이미 정렬된 오른쪽 원소들을 범위에서 제외해 점점 줄임
arr[j], arr[j+1] = arr[j+1], arr[j] Python 튜플 언패킹 교환 — 임시 변수 없이 동시 교환

2.3 복잡도 분석

총 비교 횟수:

\[ (n-1) + (n-2) + \cdots + 1 = \frac{n(n-1)}{2} = O(n^2) \]

경우 시간 복잡도 비고
최악/평균 O(n²) 역순 정렬 또는 일반적인 경우
최선 (기본) O(n²) 이미 정렬된 배열도 동일
최선 (최적화) O(n) 조기 종료 플래그(early termination) 추가 시
공간 복잡도 O(1) 제자리(in-place) 정렬, 추가 메모리 없음
실무에서는 사용하지 않는다

버블 정렬은 교육적 가치가 전부다. n = 100,000인 배열을 버블 정렬하면 약 50억 번의 비교가 필요하다. 실무에서는 O(n log n)인 퀵 정렬, 합병 정렬, 또는 언어 내장 정렬 함수를 사용한다.

3 삽입 정렬 (Insertion Sort)

3.1 동작 원리

삽입 정렬: 손에 든 카드를 정렬하듯, 현재 원소(키)를 이미 정렬된 앞부분의 올바른 위치에 삽입하는 방식

버블 정렬 vs 삽입 정렬 핵심 차이:

구분 버블 정렬 삽입 정렬
방식 인접한 원소를 교환하며 큰 값을 뒤로 밀어냄 현재 원소(키)를 정렬된 앞부분의 올바른 위치에 삽입
변화 방향 정렬된 구간이 오른쪽부터 확장 정렬된 구간이 왼쪽부터 확장

동작 단계:

  1. 두 번째 원소를 키(Key) 로 지정 (첫 원소는 정렬된 것으로 간주)
  2. 키의 왼쪽(정렬된 부분)에서 키가 삽입될 올바른 위치를 탐색
  3. 키보다 큰 원소들을 한 칸씩 오른쪽으로 밀어냄
  4. 빈자리에 키를 삽입
  5. 다음 원소를 키로 지정해 2~4단계 반복

예시: [5, 3, 8, 1] 정렬

키 정렬된 부분 동작 결과
3 (인덱스 1) [5] 5 > 3 → 5 오른쪽 이동, 3 삽입 [3, 5, 8, 1]
8 (인덱스 2) [3, 5] 5 < 8 → 이동 없음 [3, 5, 8, 1]
1 (인덱스 3) [3, 5, 8] 8, 5, 3 모두 오른쪽 이동, 1 맨앞 삽입 [1, 3, 5, 8]

3.2 코드 분석

def insertion_sort(arr):
    for i in range(1, len(arr)):   # 두 번째 원소부터 마지막까지 키로 순서대로 지정
        key = arr[i]               # 현재 삽입할 원소(키)를 저장
        print(key)                 # 현재 키 출력 (디버깅/학습용)
        j = i - 1                  # 정렬된 부분의 마지막 인덱스

        while j >= 0 and key < arr[j]:  # 키보다 큰 원소가 있는 동안 왼쪽으로 이동
            arr[j + 1] = arr[j]         # 해당 원소를 한 칸 오른쪽으로 이동
            j -= 1                      # 비교 위치를 한 칸 왼쪽으로
            print(arr)                  # 이동 과정 출력 (디버깅/학습용)

        arr[j + 1] = key           # 키를 올바른 위치에 삽입

코드 포인트:

코드 설명
key = arr[i] 키를 별도 변수에 저장 — 이후 원소들을 오른쪽으로 밀 때 덮어씌워지지 않도록 보호
j = i - 1 정렬된 부분의 가장 오른쪽 인덱스 — 키와 처음 비교할 원소의 위치
j >= 0 배열 왼쪽 경계를 벗어나지 않기 위한 안전장치
key < arr[j] 키보다 큰 원소를 만나는 동안 계속 이동
arr[j+1] = arr[j] 교환이 아니라 이동(복사) — 큰 값을 오른쪽으로 한 칸 복사, 빈자리는 나중에 키로 채움
arr[j+1] = key while 루프 종료 시점의 j+1이 키의 최종 위치

3.3 복잡도 분석

경우 시간 복잡도 이유
최악 (역순 배열) O(n²) 1 + 2 + … + (n-1) = n(n-1)/2
평균 O(n²)
최선 (정렬된 배열) O(n) key < arr[j]가 매번 즉시 false → 이동 전혀 없음, for 루프만 n-1번
공간 복잡도 O(1) 제자리 정렬, key 변수 하나만 추가
삽입 정렬이 실용적인 이유
  • 거의 정렬된 데이터(nearly sorted data) 에서 O(n)에 수렴
  • Python의 Timsort가 작은 배열 처리에 삽입 정렬을 혼합하는 이유
  • 실시간으로 데이터가 하나씩 추가되는 스트리밍 환경에 적합

4 버블 정렬 vs 삽입 정렬 비교

항목 버블 정렬 삽입 정렬
최악 시간 복잡도 O(n²) O(n²)
최선 시간 복잡도 O(n²) / O(n)* O(n)
공간 복잡도 O(1) O(1)
교환 방식 인접 원소 교환 (3번 할당) 원소 이동 후 삽입 (1번 할당)
실무 활용 없음 거의 정렬된 데이터, 소규모 데이터

*최적화된 버블 정렬(조기 종료 플래그 추가)의 경우 최선 O(n).

노트

두 알고리즘 모두 O(n²)이지만, 삽입 정렬이 실제 성능에서 일반적으로 더 빠르다. 이동 1회 = 1번의 할당 연산 vs 교환 1회 = 3번의 할당 연산 → 삽입 정렬이 상수 배 빠름.

5 정리

Part 4 핵심 요약
  • 버블 정렬: 인접 원소 비교-교환으로 큰 원소를 오른쪽으로 밀어냄 → 모든 경우 O(n²) → 실무 사용 없음
  • 삽입 정렬: 정렬된 앞부분에 현재 원소를 올바른 위치에 삽입 → 거의 정렬된 데이터에서 O(n) → 실용적

다음 파트에서는 실무에서 실제로 사용되는 퀵 정렬(Quick Sort) 과 검색 알고리즘의 전체 조감도를 다룬다.

6 퀵 정렬 (Quick Sort)

6.1 왜 퀵 정렬인가

  • 버블/삽입 정렬은 최악 O(n²) → 실무에서 거의 사용 안 함
  • 퀵 정렬의 평균 시간 복잡도: O(n log n)
  • n = 1,000,000일 때: O(n²)은 1조 번 vs O(n log n)은 약 2,000만 번 → 이것이 “Quick”이라는 이름의 이유
  • 분할-정복(Divide and Conquer) 패러다임을 기반으로 설계: “큰 문제를 작은 문제로 쪼개고, 작은 문제들을 해결한 다음 합친다”

6.2 피벗(Pivot)의 개념

피벗(pivot): 배열을 두 부분으로 나누는 기준값

3단계 동작 방식:

단계 명칭 동작
1 분할(Divide) 피벗보다 작은 값 → 왼쪽, 큰 값 → 오른쪽. 피벗은 최종 위치에 안착 (더 이상 이동 불필요)
2 정복(Conquer) 피벗 왼쪽 배열과 오른쪽 배열 각각에 동일한 과정을 재귀적으로 반복
3 결합(Combine) 왼쪽 배열 + 피벗 + 오른쪽 배열을 순서대로 이어붙이면 정렬 완성

예시: [3, 6, 8, 10, 1, 2, 1], 피벗 = 6

  • 6보다 작은 값: [3, 1, 2, 1] → 왼쪽
  • 피벗: [6]
  • 6보다 큰 값: [8, 10] → 오른쪽
  • 이후 [3, 1, 2, 1]과 [8, 10] 각각에 재귀 적용 → 세 부분 합쳐 완성

6.3 코드 분석

import random

def quick_sort(arr):
    if len(arr) <= 1:                    # 원소가 1개 이하면 이미 정렬된 상태 — 재귀 종료 조건
        return arr

    pivot = random.choice(arr)           # 배열에서 무작위로 피벗 선택
    less = []                            # 피벗보다 작은 원소 모음
    equal = []                           # 피벗과 같은 원소 모음
    greater = []                         # 피벗보다 큰 원소 모음

    for element in arr:
        if element < pivot:
            less.append(element)         # 피벗보다 작으면 less 배열
        elif element == pivot:
            equal.append(element)        # 피벗과 같으면 equal 배열
        else:
            greater.append(element)      # 피벗보다 크면 greater 배열

    return quick_sort(less) + equal + quick_sort(greater)  # 결합

코드 포인트:

코드 설명
if len(arr) <= 1: return arr 재귀 종료 조건 — 없으면 무한 재귀 → 스택 오버플로우
pivot = random.choice(arr) 무작위 피벗 선택 — 고정 시 이미 정렬된 배열에서 최악의 경우 O(n²) 유발 방지
equal = [] 별도 분리 피벗과 동일한 값이 여러 개일 때 불필요한 재귀 호출 방지
quick_sort(less) + equal + quick_sort(greater) 결합 단계 — 정렬된 왼쪽 + 피벗 + 정렬된 오른쪽

6.4 복잡도 분석

경우 시간 복잡도 이유
평균 O(n log n) 피벗이 절반으로 균등 분할 → 재귀 깊이 log n × 각 깊이 n번 비교
최악 O(n²) 피벗이 매번 최솟값/최댓값 → 1개와 n-1개로 불균등 분할 → 재귀 깊이 n
최선 O(n log n) 피벗이 매번 정확히 중앙값인 이상적인 경우
공간 (이 구현) O(n) less, equal, greater 배열을 매 재귀마다 새로 생성
공간 (in-place) O(log n) 포인터를 이용한 제자리 구현 시 재귀 스택 깊이만 사용

7 검색 알고리즘 개관

세 가지 검색 알고리즘 비교:

방식 시간 복잡도 전제 조건 공간 복잡도 특징
선형 검색 O(n) 없음 O(1) 정렬 불필요, 단순 순회
이진 검색 O(log n) 정렬된 배열 O(1) 매 단계 범위 절반 감소
해시 테이블 O(1) 평균 해시 함수 + 추가 메모리 O(n) 위치를 계산해 바로 접근

7.3 해시 테이블 (Hash Table)

  • 키(key) → 해시 함수 → 배열 인덱스로 변환 → 그 인덱스에 값 저장/검색
  • 탐색 범위를 줄이거나 순회하는 과정 자체가 없음 → “위치를 계산해서 바로 접근”
  • 평균 시간 복잡도: O(1)
  • Python의 dict, Java의 HashMap이 해시 테이블 기반
  • 주의: 해시 충돌(hash collision) 발생 시 O(1)보다 느려질 수 있음
시간-공간 트레이드오프의 전형적인 예

해시 테이블은 O(1)로 가장 빠르지만 데이터 저장을 위한 추가 메모리 O(n)이 필요하다. 메모리를 희생해서 탐색 속도를 극단적으로 높이는 전략이다.

8 알고리즘 패러다임 5가지 개관

5가지 패러다임과 상호 관계:

Brute Force          — 모든 경우 탐색 (기준선)
  └─ Back Tracking   — Brute Force + 가지치기(pruning)

Divide and Conquer   — 독립적 하위 문제로 분할 후 재귀
  └─ Dynamic Programming — 겹치는 하위 문제 + 메모이제이션

Recursion            — 위 패러다임들의 공통 구현 도구
패러다임 핵심 전략 복잡도 수준 대표 문제
Brute Force 모든 해를 생성해 하나씩 확인 O(n!), O(2ⁿ) 비밀번호 크래킹
Divide and Conquer 독립적 하위 문제로 분할 후 재귀적 해결 O(n log n) 퀵 정렬, 합병 정렬
Back Tracking Brute Force + 불가능한 경로 즉시 포기 Brute Force보다 빠름 스도쿠, N-Queens
Dynamic Programming 겹치는 하위 문제의 결과를 저장해 재사용 O(n) ~ O(n²) 피보나치, LCS, 배낭 문제
Recursion 함수가 자기 자신을 호출 패러다임 의존 트리 탐색, 분할-정복 구현

9 정리

Part 5 핵심 요약
  • 퀵 정렬: 피벗 기준 분할-정복, 평균 O(n log n), 무작위 피벗으로 최악의 경우 회피
  • 검색 알고리즘: 선형 O(n) → 이진 O(log n) → 해시 O(1)로 이어지는 성능-비용 트레이드오프
  • 5가지 패러다임: Brute Force를 출발점으로 점진적으로 정교해지는 문제 해결 전략의 스펙트럼

다음 파트에서는 각 패러다임의 설계 철학과 실제 구현을 심층 분석한다.

10 Brute Force — 무차별 대입

핵심 전략: “일단 다 해본다”

  • 모든 가능한 해(solution)를 생성하고 하나씩 정답 여부 확인
  • 수학적 통찰이나 알고리즘적 아이디어 불필요 → 문제를 이해하면 바로 적용 가능
  • 장점: 구현이 단순, 반드시 정답을 찾음 (탐색 공간이 유한하면)
  • 한계: “문제 구조를 전혀 활용하지 않음” → 탐색 공간이 커질수록 연산량 폭발적 증가
Brute Force가 실용적인 두 가지 경우
  1. 입력 크기가 충분히 작을 때 — n ≤ 10이면 O(n!) 알고리즘도 현실적으로 실행 가능 (n=10 → 10! = 3,628,800 → 현대 CPU가 0.004초 처리)
  2. 정확성 기준선(baseline)으로 사용할 때 — 복잡한 최적화 알고리즘 구현 전, Brute Force로 정답을 먼저 검증

대표 예시: 비밀번호 크래킹

조건 경우의 수 현실적 가능 여부
4자리 숫자 비밀번호 최대 10,000가지 가능
8자리 영문+숫자+특수문자 천문학적 수준 사실상 불가능

비밀번호 복잡도 요구사항의 알고리즘적 근거가 바로 이것이다.

11 Divide and Conquer — 분할 정복

핵심 아이디어: 문제의 자기 유사성(self-similarity) 활용

“전체 문제를 해결하는 방법”과 “부분 문제를 해결하는 방법”이 동일한 구조일 때, 재귀적으로 분할해서 해결한다.

3단계 동작:

단계 동작 퀵 정렬 예시
분할(Divide) 더 이상 분할 불가능할 때까지 재귀적으로 작은 하위 문제로 나눔 피벗 기준으로 less / equal / greater 분리
정복(Conquer) base case에 도달한 작은 문제 직접 해결 원소 1개 배열은 이미 정렬 → 즉시 반환
결합(Combine) 하위 문제의 해를 원래 문제의 해로 조합 quick_sort(less) + equal + quick_sort(greater)

분할-정복이 강력한 이유: 병렬화 가능성

  • 분할된 하위 문제들은 서로 독립적 → 왼쪽 배열 정렬이 오른쪽 배열에 영향 없음
  • 이 독립성 덕분에 두 하위 문제를 동시에(병렬로) 처리 가능
  • MapReduce, Apache Spark 같은 대규모 데이터 처리 프레임워크가 분할-정복 원리 기반
분할-정복 vs 동적 계획법
구분 하위 문제 관계 대표 예시
분할-정복 겹치지 않음 (non-overlapping) 퀵 정렬, 합병 정렬
동적 계획법 겹침 (overlapping) 피보나치, LCS

하위 문제가 독립적이면 분할-정복, 겹치면 동적 계획법을 선택한다.

12 Back Tracking — 백트래킹

핵심 전략: 가지치기(pruning)가 있는 완전 탐색

  • Brute Force처럼 모든 경우를 탐색하되, “이 경로는 정답이 될 수 없다”고 판단되는 순간 즉시 중단하고 이전 분기점으로 복귀
  • “답이 될 수 없는 상황”의 정의가 구체적이고 조기에 적용될수록 → 탐색 공간 더 많이 가지치기 → 알고리즘 더 빠르게 동작

미로 탐색으로 이해하기:

입구 → 전진 → 벽 부딪힘 (답이 될 수 없는 상황) → 되돌아가기 → 다른 방향 시도 → 출구 발견
  • Brute Force: 미로의 모든 칸 빠짐없이 방문
  • 백트래킹: 막힌 방향 즉시 포기 → 실제 탐색 경로 수가 훨씬 적음

대표 문제: N-Queens

접근법 N=8 기준 탐색 경우의 수 비고
Brute Force C(64, 8) ≈ 44억 가지 모든 배치 조합 확인
백트래킹 극히 일부 같은 열·대각선 → 즉시 가지치기

13 Dynamic Programming — 동적 계획법

DP 적용 필수 조건 2가지:

조건 설명
최적 부분 구조 (Optimal Substructure) 전체 문제의 최적해가 하위 문제의 최적해로 구성됨
겹치는 하위 문제 (Overlapping Subproblems) 동일한 하위 문제가 반복해서 등장

최적 부분 구조가 없으면 → 하위 문제 해를 합쳐도 전체 최적해가 안 됨 겹치는 하위 문제가 없으면 → 메모이제이션 이점 없음 → 그냥 분할-정복 사용

13.1 메모이제이션 (Memoization)

메모이제이션: “이미 계산한 결과를 저장해두고 재사용하는 기법” (memorization이 아니라 memo에서 유래한 별개의 용어)

피보나치 점화식:

\[F(n) = F(n-1) + F(n-2), \quad F(0) = 0, \; F(1) = 1\]

메모이제이션 없는 재귀의 문제 — F(5) 계산 추적:

F(5)
├── F(4)
│   ├── F(3)
│   │   ├── F(2) [F(1)+F(0)]
│   │   └── F(1)
│   └── F(2) [F(1)+F(0)]   ← F(2) 중복 계산
└── F(3)                    ← F(3) 중복 계산
    ├── F(2) [F(1)+F(0)]   ← F(2) 중복 계산
    └── F(1)
  • F(3): 2번 계산, F(2): 3번 계산, F(1): 5번 계산
  • n이 커질수록 중복 계산 기하급수적으로 증가
  • 시간 복잡도: O(2ⁿ) — n=50이면 약 1,125조 번 연산

메모이제이션 적용:

def fib_memo(n, memo={}):
    if n <= 1:
        return n
    if n in memo:               # 이미 계산한 값이 있으면 즉시 반환
        return memo[n]
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)  # 계산 후 저장
    return memo[n]
  • F(3)을 처음 계산할 때 결과를 memo에 저장 → 이후 모든 F(3) 요청은 즉시 반환
  • 실제로 계산되는 고유한 하위 문제: F(0), F(1), …, F(n) → 정확히 n+1개
  • 시간 복잡도: O(2ⁿ) → O(n) 으로 극적으로 감소

13.2 Top-Down vs Bottom-Up

방식 구현 기반 장점 단점
Top-Down (메모이제이션) 재귀 수학적 정의를 코드로 자연스럽게 표현 재귀 스택 오버플로우 위험
Bottom-Up (Tabulation) 반복문 스택 오버플로우 없음, 캐시 효율 높음 모든 하위 문제를 순서대로 계산

Bottom-Up 구현:

def fib_dp(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)   # 크기 n+1의 배열 초기화
    dp[0], dp[1] = 0, 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]  # 이전에 계산한 값을 그대로 참조
    return dp[n]
  • 시간 복잡도: O(n), 공간 복잡도: O(n)
  • 변수 두 개만으로 구현 시 공간 복잡도 O(1)로 최적화 가능

14 Recursion — 재귀

핵심: 함수가 자기 자신을 호출해서 문제를 해결하는 기법

  • 엄밀히 말하면 패러다임이라기보다 분할-정복·DP·백트래킹을 구현하는 공통 도구
  • 자기 유사한(self-similar) 문제 구조를 코드로 자연스럽게 표현 가능
    • “n번째 피보나치 수 = n-1번째 + n-2번째” → 재귀 함수로 그대로 표현

재귀 함수의 필수 구성 요소:

요소 설명 없으면?
종료 조건 (Base Case) 재귀를 멈추는 조건 무한 재귀 → 스택 오버플로우
재귀 호출 (Recursive Call) 더 작은 단위로 줄여 자기 자신 호출 반드시 매 호출마다 문제가 작아져야 함

콜 스택 동작 — fib(4) 추적:

fib(4) 호출 → push
  fib(3) 호출 → push
    fib(2) 호출 → push
      fib(1) → base case: 1 반환 → pop
      fib(0) → base case: 0 반환 → pop
    fib(2) = 1 반환 → pop
    fib(1) → base case: 1 반환 → pop
  fib(3) = 2 반환 → pop
  fib(2) 호출 → (위와 동일)
fib(4) = 3 반환 → pop
  • 각 함수 호출은 스택 프레임 하나씩 소비
  • 종료 조건 없이 재귀가 무한 반복 → 스택 메모리 고갈
  • Python 기본 재귀 깊이 제한: 1,000 (스택 오버플로우 방지)

재귀 vs 반복문 선택 기준:

상황 권장 방식
트리·그래프 탐색, 분할-정복처럼 문제 구조 자체가 재귀적 재귀 — 코드가 짧고 직관적
단순 선형 반복, 재귀 깊이가 매우 깊을 때 반복문 — 스택 사용 없음, 메모리 효율 높음

15 알고리즘 트레이닝 사이트 비교

플랫폼 URL 특징 추천 대상
백준 acmicpc.net 국내 최대 문제 저장소, 난이도 폭 넓음, 단계별 문제 풀기 제공 입문 ~ 고급 전체
프로그래머스 programmers.co.kr 카카오·네이버 기출 다수, 레벨 1~5 구분 국내 취업 준비
Codility app.codility.com 유럽 기업 채용 코딩 테스트, 복잡도 조건 명시 (O(n log n) 이내 등) 복잡도 분석 능력 필요
LeetCode leetcode.com 글로벌 빅테크 면접 표준, Easy/Medium/Hard 구분, 풀이 비교 가능 해외 취업, 빅테크 지망

16 시리즈 전체 정리

6개 파트 핵심 요약
파트 핵심 내용
Part 1 알고리즘 = 명확하고 유한하며 정확하고 효율적인 명령의 집합
Part 2 Big-O = 하드웨어 독립적 효율성 측정, 최악의 경우 성능 상한선
Part 3 O(n): 단일 순회, O(n²): 중첩 루프, O(log n): 범위 반감 → 알고리즘 선택이 수억 배 성능 차이 유발
Part 4 버블/삽입 정렬 O(n²), 삽입 정렬은 거의 정렬된 데이터에서 O(n) 수렴
Part 5 퀵 정렬 평균 O(n log n), 검색: 선형 O(n) → 이진 O(log n) → 해시 O(1) 트레이드오프
Part 6 5가지 패러다임은 Brute Force를 출발점으로 점진적으로 정교해지는 문제 해결 전략 스펙트럼
알고리즘 학습의 본질

알고리즘 학습의 본질은 코드 암기가 아니다. “이 문제의 구조가 무엇인가”를 파악하고, 그 구조에 맞는 도구를 선택하는 사고력을 기르는 것이다.

Subscribe

Enjoy this blog? Get notified of new posts by email: