코딩의 신 84

알고리즘

시간복잡도 체감 (Big-O 실전)

자주 쓰는 감각

O(1) : 즉시

O(log N) : 이진 탐색

O(N) : 한 번 순회

O(N log N) : 정렬

O(N²) : 대부분 터짐

// O(N)
foreach (var x in list) { }

// O(N^2)
for (int i = 0; i < n; i++)
  for (int j = 0; j < n; j++) { }

// 유니티 Update()에서 O(N²) = x!!

탐색 알고리즘

DFS / BFS

BFS (최단거리)

Queue<int> q = new();
bool[] visited = new bool[n];

q.Enqueue(start);
visited[start] = true;

while (q.Count > 0)
{
    int cur = q.Dequeue();
    foreach (int next in graph[cur])
    {
        if (!visited[next])
        {
            visited[next] = true;
            q.Enqueue(next);
        }
    }
}
//
쓰임:

최단 이동 거리

맵 탐색

UI 트리 탐색

DFS (모든 경우 탐색)

void DFS(int node)
{
    visited[node] = true;
    foreach (int next in graph[node])
        if (!visited[next])
            DFS(next);
}

쓰임:

모든 조합

던전/맵 구조

백트래킹

정렬 알고리즘 (내부 동작 감각)

list.Sort();

알고리즘 감각용

퀵정렬: 평균 빠름

병합정렬: 안정적

힙정렬: 우선순위 큐 기반

쓰는 용도:

커스텀 기준

부분 정렬

안정성 필요

그리디 (생각력 테스트)

// 회의실 배정, 동전 문제

동적 계획법 (DP)

핵심 사고

작은 문제로 나눈다

결과를 저장한다

다시 안 푼다

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];

//
최적 경로

점수 최대화

스테이지 클리어 조건

우선순위 큐 / 힙

PriorityQueue<int, int> pq = new();
pq.Enqueue(value, priority);
int top = pq.Dequeue();

최단경로 알고리즘

// BFS + PriorityQueue

쓰임:

네비게이션

몬스터 추적

맵 이동 비용

A*

다익스트라 + 휴리스틱

게임에서 제일 많이 씀

분할정복

// merge sort, binary search

큰 문제 → 반으로 → 합침

재귀 감각 중요

백트래킹 (조합/퍼즐)

void Solve(int depth)
{
    if (depth == max) return;

    for (...)
    {
        if (조건)
        {
            Solve(depth + 1);
            되돌리기;
        }
    }
}

쓰임:

퍼즐

경우의 수

스킬 조합