Algorithm 핵심 개념 완벽 정리

고급 개발자를 위한 알고리즘 핵심 개념을 실전 코드와 함께 정리했습니다. 시간복잡도 분석부터 고급 자료구조까지 실무에 바로 적용 가능한 내용을 다룹니다.

---

---

들어가며

이 글에서는 Algorithm 핵심 개념 완벽 정리에 대해 상세히 알아보겠습니다. 총 12가지 주요 개념을 다루며, 각각의 개념에 대한 설명과 실제 코드 예제를 함께 제공합니다.

목차

1. 이진_탐색_최적화
2. 동적_프로그래밍_메모이제이션
3. 그래프_깊이우선탐색
4. 그래프_너비우선탐색
5. 트리_중위순회
6. 투_포인터_기법
7. 슬라이딩_윈도우
8. 백트래킹_순열생성
9. 최소_힙_구현
10. 유니온_파인드
11. LRU_캐시_구현
12. 트라이_문자열_검색

---

1. 이진 탐색 최적화

개요

정렬된 배열에서 O(log n) 시간에 원소를 찾는 핵심 알고리즘입니다. 하한/상한 탐색 변형도 함께 구현합니다.

코드 예제

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

설명

중간값을 기준으로 탐색 범위를 절반씩 줄여나가며, 로그 시간복잡도로 효율적으로 탐색합니다.

---

2. 동적 프로그래밍 메모이제이션

개요

중복 계산을 방지하여 지수 시간을 다항 시간으로 최적화하는 기법입니다. 피보나치 수열을 예시로 구현합니다.

코드 예제

def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

print(fib_memo(100))  # 빠르게 계산

설명

이미 계산한 값을 딕셔너리에 저장하여 재사용함으로써 O(2^n)을 O(n)으로 개선합니다.

---

3. 그래프 깊이우선탐색

개요

스택 또는 재귀를 이용해 그래프의 모든 노드를 깊이 방향으로 탐색합니다. 사이클 감지, 위상정렬 등에 활용됩니다.

코드 예제

def dfs(graph, node, visited=set()):
    if node in visited:
        return
    visited.add(node)
    print(node, end=' ')
    for neighbor in graph[node]:
        dfs(graph, neighbor, visited)

graph = {0:[1,2], 1:[3], 2:[3], 3:[]}
dfs(graph, 0)

설명

방문 체크를 하며 재귀적으로 인접 노드를 탐색하고, 백트래킹으로 모든 경로를 확인합니다.

---

4. 그래프 너비우선탐색

개요

큐를 사용하여 레벨 순서로 그래프를 탐색합니다. 최단경로 찾기에 최적화된 알고리즘입니다.

코드 예제

from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    while queue:
        node = queue.popleft()
        print(node, end=' ')
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

설명

큐에서 노드를 꺼내며 인접 노드를 레벨별로 방문하여 최단 거리를 보장합니다.

---

5. 트리 중위순회

개요

이진 탐색 트리에서 정렬된 순서로 노드를 방문하는 핵심 순회 방법입니다. 왼쪽-루트-오른쪽 순서로 탐색합니다.

코드 예제

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = self.right = None

def inorder(root):
    if root:
        inorder(root.left)
        print(root.val, end=' ')
        inorder(root.right)

설명

왼쪽 서브트리를 먼저 방문하고 루트를 처리한 후 오른쪽 서브트리를 방문하여 오름차순 출력을 보장합니다.

---

6. 투 포인터 기법

개요

두 개의 포인터를 이동시키며 배열 문제를 O(n) 시간에 해결합니다. 정렬된 배열에서 특히 효과적입니다.

코드 예제

def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        current = arr[left] + arr[right]
        if current == target:
            return [left, right]
        elif current < target:
            left += 1
        else:
            right -= 1
    return None

설명

양 끝에서 시작하여 합이 목표보다 작으면 왼쪽을, 크면 오른쪽을 이동하며 O(n) 시간에 해결합니다.

---

7. 슬라이딩 윈도우

개요

고정 또는 가변 크기의 윈도우를 이동시키며 부분 배열 문제를 효율적으로 해결합니다.

코드 예제

def max_sum_subarray(arr, k):
    max_sum = curr_sum = sum(arr[:k])
    for i in range(k, len(arr)):
        curr_sum += arr[i] - arr[i-k]
        max_sum = max(max_sum, curr_sum)
    return max_sum

print(max_sum_subarray([1,4,2,10,23,3,1,0,20], 4))

설명

윈도우를 한 칸씩 이동하며 이전 값을 빼고 새 값을 더해 O(n) 시간에 최대 합을 찾습니다.

---

8. 백트래킹 순열생성

개요

모든 가능한 조합을 탐색하되, 조건에 맞지 않으면 즉시 되돌아가는 효율적인 완전탐색 기법입니다.

코드 예제

def permute(nums):
    result = []
    def backtrack(path, remaining):
        if not remaining:
            result.append(path[:])
            return
        for i in range(len(remaining)):
            backtrack(path + [remaining[i]],
                     remaining[:i] + remaining[i+1:])
    backtrack([], nums)
    return result

설명

재귀적으로 원소를 선택하고, 선택을 취소하며 모든 순열을 생성합니다.

---

9. 최소 힙 구현

개요

우선순위 큐의 기본이 되는 힙 자료구조로, O(log n) 삽입/삭제를 제공합니다.

코드 예제

import heapq

heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 1)
heapq.heappush(heap, 3)

while heap:
    print(heapq.heappop(heap), end=' ')  # 1 3 5

설명

heapq 모듈을 사용해 최소값을 O(log n) 시간에 추출하며, 다익스트라 등에 필수적입니다.

---

10. 유니온 파인드

개요

분리 집합을 효율적으로 관리하는 자료구조로, 경로 압축과 랭크 최적화로 거의 O(1) 연산을 달성합니다.

코드 예제

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        self.parent[self.find(x)] = self.find(y)

설명

경로 압축으로 트리 높이를 줄여 find 연산을 최적화하며, 크루스칼 알고리즘 등에 사용됩니다.

---

11. LRU 캐시 구현

개요

최근 사용 빈도 기반 캐시로, 해시맵과 이중 연결 리스트를 결합하여 O(1) 삽입/삭제/조회를 구현합니다.

코드 예제

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

설명

OrderedDict로 삽입 순서를 유지하며, 용량 초과 시 가장 오래된 항목을 O(1)에 제거합니다.

---

12. 트라이 문자열 검색

개요

문자열 집합을 트리 구조로 저장하여 O(m) 시간에 검색/삽입하는 효율적인 자료구조입니다.

코드 예제

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end

설명

각 문자를 노드로 저장하여 공통 접두사를 공유하며, 자동완성과 사전 구현에 최적화되어 있습니다.

---

마치며

이번 글에서는 Algorithm 핵심 개념 완벽 정리에 대해 알아보았습니다. 총 12가지 개념을 다루었으며, 각각의 사용법과 예제를 살펴보았습니다.

관련 태그

#Algorithm #BinarySearch #DynamicProgramming #Graph #TreeTraversal