알고리즘 핵심 정리

wayhope Computer Science

알고리즘은 결국 문제를 해결하는 절차다.

같은 문제라도 어떤 방법으로 해결하느냐에 따라 필요한 시간과 메모리가 크게 달라진다. 입력이 몇 개 안 될 때는 별 차이가 없지만, 데이터가 수십만 개, 수백만 개로 늘어나면 알고리즘 선택 하나가 프로그램의 성능을 결정한다.

그래서 알고리즘을 공부할 때는 특정 문제의 풀이법을 외우는 것보다 문제를 어떤 구조로 바라보고, 어떤 자료구조와 알고리즘을 선택할 것인지를 익히는 쪽에 가깝다.

알고리즘의 기본 구조

알고리즘을 작성할 때 가장 먼저 봐야 하는 것은 입력과 출력이다.

Input  -> Problem  -> Algorithm  -> Output

여기에 실제로 필요한 것은 두 가지다.

  • 문제를 정확하게 정의하는 것
  • 입력 크기에 맞는 해결 방법을 선택하는 것

예를 들어 숫자 배열에서 특정 값을 찾는 문제를 생각해보자.

[10, 42, 7, 31, 25]

그냥 처음부터 끝까지 비교하면 된다.

10 비교
42 비교
7 비교
31 비교
25 비교

이것도 하나의 알고리즘이다.

하지만 데이터가 정렬되어 있다면 이야기가 달라진다.

[7, 10, 25, 31, 42, 53, 68, ...]

중간 값을 확인하면서 탐색 범위를 절반씩 줄일 수 있다.

같은 “값 찾기” 문제지만 데이터의 조건에 따라 적절한 알고리즘이 달라진다.

시간 복잡도

알고리즘의 성능을 이야기할 때 가장 많이 사용하는 것이 시간 복잡도(Time Complexity)다.

입력 크기 N이 증가할 때 연산량이 어떻게 증가하는지를 나타낸다.

대표적인 형태는 다음과 같다.

O(1)
O(log N)
O(N)
O(N log N)
O(N²)
O(2^N)
O(N!)

대략적인 증가 속도를 보면 다음과 같다.

O(1) < O(log N) < O(N) < O(N log N) < O(N²) < O(2^N) < O(N!)

실제 실행 시간이 정확하게 이 식과 일치한다는 의미는 아니다.

입력 크기가 커질수록 연산량이 어떤 비율로 증가하는지를 보는 것이다.

예를 들어 배열에서 값을 순차적으로 찾는다면 최악의 경우 모든 원소를 확인해야 한다.

for (int i = 0; i < N; ++i)
{
    if (array[i] == target)
        return i;
}

최악의 경우 N번 비교하므로 O(N)이다.

반면 이진 탐색은 매번 탐색 범위를 절반으로 줄인다.

N
N / 2
N / 4
N / 8
...

그래서 O(log N)이 된다.

Big-O에서 중요한 것

Big-O에서는 보통 가장 크게 증가하는 항을 남긴다.

예를 들어 다음과 같은 연산이 있다고 하자.

N² + N + 10

N이 충분히 커지면 N²의 영향이 압도적이다.

따라서 시간 복잡도는 O(N²)로 표현한다.

상수도 일반적으로 제거한다.

3N + 100 은 O(N) 이다.

Big-O는 실제 성능을 정확하게 측정하는 도구가 아니라 입력 크기에 따른 성장률을 비교하기 위한 표기법이다.

실제 성능에서는 캐시, 메모리 접근 패턴, CPU, 언어 런타임, 상수 비용 등도 영향을 준다.

공간 복잡도

시간만 보는 것은 부족하다.

알고리즘이 추가로 사용하는 메모리도 고려해야 한다.

이를 공간 복잡도(Space Complexity)라고 한다.

예를 들어 입력 배열을 그대로 사용하면서 몇 개의 변수만 추가로 사용한다면 추가 공간은 O(1)로 볼 수 있다.

int sum = 0;

for (int value : values)
    sum += value;

반대로 입력 크기 N에 비례하는 별도의 배열을 만든다면 O(N)의 추가 공간이 필요하다.

시간과 메모리는 서로 트레이드오프가 될 수도 있다.

메모리를 더 사용해서 계산 시간을 줄이는 방식도 흔하다.

자료구조와 알고리즘

알고리즘을 공부하다 보면 자료구조와 분리해서 생각하기 어렵다.

자료구조는 데이터를 어떻게 저장하고 관리할지 결정하고, 알고리즘은 그 데이터를 어떻게 처리할지 결정한다.

예를 들어 특정 값을 빠르게 찾고 싶다면 데이터가 어떻게 저장되어 있는지가 중요하다.

Array-> 인덱스 접근이 빠름

Linked List-> 중간 삽입/삭제에 유리한 구조

Hash Table-> 평균적으로 빠른 키 기반 탐색

Tree-> 계층적인 데이터 표현 및 탐색

Heap-> 우선순위가 높은 데이터 처리

Graph-> 객체 사이의 관계 표현

알고리즘 선택은 자료구조 선택과 같이 봐야 한다.

정렬

정렬은 알고리즘 공부에서 기본적으로 자주 등장하는 문제다.

대표적인 정렬 알고리즘은 다음과 같다.

  • Bubble Sort
  • Selection Sort
  • Insertion Sort
  • Merge Sort
  • Quick Sort
  • Heap Sort

단순한 정렬 알고리즘은 구현하기 쉽지만 일반적으로 O(N²)의 시간 복잡도를 가진다.

반면 Merge Sort, Heap Sort 등은 일반적으로 O(N log N) 수준의 성능을 얻을 수 있다.

실제 개발에서는 직접 정렬 알고리즘을 구현하기보다 언어 또는 라이브러리가 제공하는 정렬 함수를 사용하는 경우가 많다.

알고리즘을 공부하면서 직접 구현하는 이유는 정렬 함수 자체가 필요해서라기보다 데이터를 어떻게 비교하고 분할하고 재구성하는지 이해하기 위해서에 가깝다.

탐색

탐색은 주어진 데이터에서 원하는 대상을 찾는 문제다.

가장 단순한 방법은 순차 탐색이다.

첫 번째 확인
    ->
두 번째 확인
    ->
세 번째 확인
    ->
...

시간 복잡도는 O(N)이다.

데이터가 정렬되어 있다면 이진 탐색을 사용할 수 있다.

중간 확인 -> 왼쪽 또는 오른쪽 선택 -> 다시 중간 확인 -> 반복

탐색 범위를 계속 절반으로 줄이기 때문에 O(log N)이다.

여기서 중요한 조건이 하나 있다.

이진 탐색은 정렬된 데이터라는 조건이 있어야 한다.

알고리즘의 성능만 보고 선택하면 안 된다. 그 알고리즘이 요구하는 전제 조건까지 같이 봐야 한다.

재귀

재귀(Recursion)는 함수가 자기 자신을 호출하는 방식이다.

대표적으로 트리 탐색이나 DFS에서 자주 사용한다.

void DFS(Node* node)
{
    if (node == nullptr)
        return;

    for (Node* child : node->children)
        DFS(child);
}

재귀에서는 반드시 종료 조건이 필요하다.

문제 ->더 작은 문제 ->더 작은 문제 ->종료 조건

재귀 호출이 깊어지면 호출 스택을 많이 사용할 수 있다.

따라서 재귀가 항상 좋은 것은 아니다. 같은 구조를 반복문으로 구현할 수 있다면 명시적인 Stack 자료구조를 사용하는 방법도 있다.

분할 정복

Divide and Conquer는 문제를 작은 문제로 나누고 각각 해결한 뒤 결과를 합치는 방식이다.

대표적인 예가 Merge Sort다.

전체 배열 -> 두 부분으로 분할 -> 각각 정렬 -> 두 결과 병합

큰 문제를 작은 문제로 나누면 복잡한 문제를 비교적 단순한 문제들의 조합으로 만들 수 있다.

이 패턴은 정렬뿐만 아니라 다양한 알고리즘에서 등장한다.

그리디 알고리즘

Greedy Algorithm은 현재 상황에서 가장 좋아 보이는 선택을 계속하는 방식이다.

예를 들어 어떤 문제에서 현재 가장 큰 이득을 주는 선택을 하고, 그 선택을 고정한 뒤 다음 선택을 진행한다.

현재 최선의 선택 -> 다음 최선의 선택 -> 다음 최선의 선택 -> ...

구현 자체는 단순한 경우가 많다.

문제는 현재 최선의 선택이 전체적으로도 최선이라는 보장이 있는가다.

그리디 알고리즘은 모든 문제에 적용할 수 없다.

따라서 그리디 문제를 만났을 때는 “일단 가장 좋은 것을 선택하면 되겠지”가 아니라 왜 이 선택이 최적해를 만들 수 있는지를 증명하거나 문제의 성질을 확인해야 한다.

동적 계획법

Dynamic Programming(DP)은 큰 문제를 작은 부분 문제로 나누고, 같은 부분 문제가 반복해서 등장할 때 그 결과를 저장해서 재사용하는 방법이다.

대표적인 형태는 다음과 같다.

A를 두 번 계산할 필요가 없다.

한 번 계산한 결과를 저장해두면 된다.

DP를 볼 때는 보통 다음 세 가지를 생각하면 된다.

상태(State)
전이(Transition)
초기값(Base Case)

예를 들어 피보나치 수열을 단순 재귀로 계산하면 같은 값을 계속 다시 계산하게 된다.

메모이제이션을 적용하면 이미 계산한 결과를 재사용할 수 있다.

DP의 핵심은 단순히 “배열에 값을 저장한다”가 아니다.

문제의 상태를 어떻게 정의하고, 이전 상태에서 현재 상태를 어떻게 만들 것인지 찾는 것이 핵심이다.

그래프

그래프는 객체와 객체 사이의 관계를 표현하는 자료구조다.

각 객체를 정점(Vertex), 관계를 간선(Edge)이라고 한다.

게임에서는 그래프가 상당히 자주 등장한다.

맵의 위치를 노드로 만들고 이동 가능한 관계를 간선으로 표현하면 길찾기 문제를 그래프로 볼 수 있다.

그래프는 방향이 있는지, 가중치가 있는지에 따라 문제의 성질이 달라진다.

A -> B

처럼 방향이 있는 그래프가 있고,

A -- B

처럼 방향이 없는 그래프도 있다.

간선에 이동 비용이 존재할 수도 있다.

A -- 5 -- B

이 차이에 따라 선택하는 알고리즘도 달라진다.

BFS와 DFS

그래프를 탐색하는 가장 기본적인 방법으로 BFS와 DFS가 있다.

BFS

BFS는 가까운 노드부터 탐색한다.

Start -> 거리 1 -> 거리 2 -> 거리 3 -> ...

Queue를 사용한다.

가중치가 없는 그래프에서 시작점으로부터 각 노드까지의 최단 거리를 구할 때 사용할 수 있다.

DFS

DFS는 한 방향으로 최대한 깊게 들어간 뒤 돌아온다.

Start -> A -> B -> C -> Back

Stack 또는 재귀 호출을 사용한다.

모든 경로를 탐색하거나 연결 요소를 찾거나 그래프 구조를 확인하는 등의 문제에서 자주 사용한다.

둘 다 그래프 탐색이지만 탐색 순서가 다르다.

최단 경로

그래프에서 두 지점 사이의 가장 짧은 경로를 찾는 문제는 게임 개발에서도 자주 등장한다.

가중치가 없는 그래프라면 BFS를 사용할 수 있다.

모든 간선의 가중치가 양수라면 Dijkstra Algorithm을 사용할 수 있다.

Start -> 가장 가까운 노드 선택 -> 주변 노드의 거리 갱신 -> 반복

간선의 가중치가 음수가 존재하는 경우에는 Dijkstra를 그대로 사용할 수 없다.

게임의 길찾기에서는 A*도 많이 사용한다.

A*는 실제 이동 비용 g(n)과 목적지까지의 예상 비용 h(n)을 이용해 우선순위를 계산한다.

f(n) = g(n) + h(n)

휴리스틱이 좋은 경우 Dijkstra보다 탐색해야 할 영역을 줄일 수 있다.

게임에서 맵의 크기와 이동 비용, 장애물 구조 등을 고려해 적절한 길찾기 알고리즘을 선택하게 된다.

백트래킹

Backtracking은 가능한 선택을 하나씩 시도하다가 조건에 맞지 않으면 이전 상태로 돌아가는 방식이다.

선택 ->선택 ->조건 위반 ->되돌리기 ->다른 선택

대표적으로 순열, 조합, N-Queen, 퍼즐 같은 문제에서 사용한다.

가능한 경우의 수가 많기 때문에 최악의 경우 매우 큰 시간 복잡도를 가질 수 있다.

그래서 조건을 이용해 애초에 답이 될 수 없는 경로를 중간에 제거하는 것이 중요하다.

이런 가지치기(Pruning)를 얼마나 잘하느냐에 따라 실제 실행 시간이 크게 달라진다.

알고리즘을 선택하는 기준

문제를 보면 바로 알고리즘 이름부터 떠올리기보다 조건을 먼저 확인하는 편이 좋다.

입력 크기는?
데이터가 정렬되어 있는가?
그래프인가?
간선에 가중치가 있는가?
음수 가중치가 존재하는가?
중복되는 부분 문제가 있는가?
최적해를 구해야 하는가?
시간 제한은 어느 정도인가?
메모리 제한은 어느 정도인가?

예를 들어 같은 최단 경로 문제라도 조건에 따라 달라진다.

가중치 없음-> BFS

양수 가중치-> Dijkstra

휴리스틱 사용 가능-> A*

음수 가중치 존재-> 다른 최단 경로 알고리즘 고려

알고리즘 선택은 결국 문제의 조건과 알고리즘의 조건을 맞추는 과정이다.

알고리즘 문제를 볼 때

문제를 처음 보면 구현부터 시작하기 쉽다.

그보다는 먼저 입력의 크기부터 보는 것이 좋다.

예를 들어 N이 수십만인데 O(N²) 알고리즘을 사용한다면 구현이 아무리 깔끔해도 실행 시간이 문제가 될 가능성이 높다.

반대로 N이 10 정도라면 O(2^N)이나 백트래킹 같은 방법도 충분히 사용할 수 있다.

대략적으로 보면

N이 작음-> 완전 탐색 / 백트래킹

N이 큼-> O(N), O(N log N) 등을 우선 고려

정렬된 데이터-> 이진 탐색 등 활용

중복 부분 문제-> DP 고려

관계 구조-> Graph + BFS / DFS / 최단 경로 등 고려

이런 식으로 문제의 제약 조건에서 가능한 알고리즘의 범위를 먼저 좁혀가는 것이 효율적이다.

알고리즘을 공부하면서 보는 것

알고리즘을 공부하면서 결국 반복해서 보게 되는 것은 몇 가지 패턴이다.

탐색-> BFS / DFS / Binary Search

정렬-> Merge Sort / Quick Sort / Heap Sort

최적화-> Greedy / Dynamic Programming

경로-> BFS / Dijkstra / A*

경우의 수-> Backtracking

분할-> Divide and Conquer

관계-> Graph

하지만 알고리즘 이름을 많이 알고 있는 것과 문제를 잘 푸는 것은 별개의 문제다.

실제로 중요한 것은 문제를 봤을 때

이 과정을 자연스럽게 수행하는 것이다.

결국 알고리즘은 특정 코드를 외우는 공부라기보다 문제를 어떤 구조로 바꿔서 생각할 것인가를 훈련하는 분야에 가깝다.

같은 문제라도 자료구조 하나를 바꾸고, 탐색 순서를 바꾸고, 중복 계산을 제거하는 것만으로 성능이 몇 배에서 수천 배까지 달라질 수 있다.

개발에서 알고리즘을 알아야 하는 이유도 여기에 있다. 코드를 작성하는 능력과 별개로, 어떤 문제를 어떤 방식으로 풀어야 하는지 판단하는 능력이 필요하기 때문이다.