Algorithm 핵심 개념 완벽 정리

알고리즘의 핵심 개념과 자주 사용되는 패턴들을 실전 코드로 완벽하게 정리했습니다. 시간복잡도 분석부터 실전 문제 해결까지 한번에 마스터하세요.

---

---

들어가며

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

목차

1. 이진_탐색(Binary_Search)
2. 투_포인터(Two_Pointer)
3. 슬라이딩_윈도우(Sliding_Window)
4. 동적_계획법(Dynamic_Programming)
5. 깊이_우선_탐색(DFS)
6. 너비_우선_탐색(BFS)
7. 퀵_정렬(Quick_Sort)
8. 해시_테이블_활용(Hash_Table)
9. 백트래킹(Backtracking)
10. 그리디_알고리즘(Greedy)
11. 유니온_파인드(Union_Find)
12. 이진_힙_우선순위_큐(Binary_Heap)

---

1. 이진 탐색(Binary Search)

개요

정렬된 배열에서 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. 투 포인터(Two Pointer)

개요

두 개의 포인터를 이용해 배열을 효율적으로 탐색하는 기법으로, 정렬된 배열에서 합이나 차이를 찾을 때 유용합니다.

코드 예제

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) 시간에 답을 찾습니다.

---

3. 슬라이딩 윈도우(Sliding Window)

개요

고정 크기 또는 가변 크기의 윈도우를 이동시키며 배열의 부분을 효율적으로 처리하는 기법입니다.

코드 예제

def max_sum_subarray(arr, k):
    window_sum = sum(arr[:k])
    max_sum = window_sum

    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i-k]
        max_sum = max(max_sum, window_sum)

    return max_sum

설명

윈도우를 한 칸씩 이동하며 이전 계산을 재활용해 O(n) 시간에 최대합을 구합니다.

---

4. 동적 계획법(Dynamic Programming)

개요

큰 문제를 작은 부분 문제로 나누고, 결과를 저장(메모이제이션)하여 중복 계산을 피하는 최적화 기법입니다.

코드 예제

def fibonacci(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1

    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]

    return dp[n]

설명

이전에 계산한 값을 배열에 저장해두고 재사용함으로써 O(n) 시간에 피보나치 수를 계산합니다.

---

5. 깊이 우선 탐색(DFS)

개요

그래프나 트리를 깊이를 우선으로 탐색하는 알고리즘으로, 스택이나 재귀를 사용합니다.

코드 예제

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(node, end=' ')

    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    return visited

설명

한 경로를 끝까지 탐색한 후 백트래킹하며, 모든 노드를 방문합니다.

---

6. 너비 우선 탐색(BFS)

개요

그래프나 트리를 레벨별로 탐색하는 알고리즘으로, 큐를 사용하여 최단 경로를 찾을 때 유용합니다.

코드 예제

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)

설명

큐를 사용해 같은 레벨의 노드들을 먼저 방문하고, 최단 경로 문제에 적합합니다.

---

7. 퀵 정렬(Quick Sort)

개요

평균 O(n log n) 시간복잡도를 가진 분할 정복 기반의 효율적인 정렬 알고리즘입니다.

코드 예제

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

설명

피벗을 기준으로 작은 값과 큰 값을 나누어 재귀적으로 정렬하며, 실전에서 가장 많이 사용됩니다.

---

8. 해시 테이블 활용(Hash Table)

개요

O(1) 시간에 검색/삽입/삭제가 가능한 해시 테이블을 활용한 효율적인 문제 해결 패턴입니다.

코드 예제

def two_sum(nums, target):
    hash_map = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in hash_map:
            return [hash_map[complement], i]
        hash_map[num] = i
    return None

설명

해시맵에 값을 저장하며 한 번의 순회로 O(n) 시간에 두 수의 합 문제를 해결합니다.

---

9. 백트래킹(Backtracking)

개요

모든 가능한 경우의 수를 탐색하되, 조건에 맞지 않으면 이전 단계로 돌아가는 완전 탐색 기법입니다.

코드 예제

def permutations(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

설명

재귀적으로 모든 순열을 생성하며, 조건 검사를 통해 불필요한 탐색을 줄일 수 있습니다.

---

10. 그리디 알고리즘(Greedy)

개요

각 단계에서 현재 최선의 선택을 하여 전체 최적해를 구하는 알고리즘입니다.

코드 예제

def min_coins(coins, amount):
    coins.sort(reverse=True)
    count = 0
    for coin in coins:
        if amount >= coin:
            count += amount // coin
            amount %= coin
    return count if amount == 0 else -1

설명

큰 동전부터 최대한 사용하여 최소 개수의 동전으로 거스름돈을 만듭니다.

---

11. 유니온 파인드(Union Find)

개요

서로소 집합을 효율적으로 관리하는 자료구조로, 그래프의 연결성을 판단할 때 사용됩니다.

코드 예제

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)

설명

경로 압축 기법으로 거의 O(1)에 가까운 시간에 집합의 루트를 찾고 합칠 수 있습니다.

---

12. 이진 힙 우선순위 큐(Binary Heap)

개요

최댓값 또는 최솟값을 O(log n) 시간에 추출할 수 있는 완전 이진 트리 기반 자료구조입니다.

코드 예제

import heapq

def k_largest_elements(nums, k):
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)
    return sorted(heap, reverse=True)

설명

최소 힙을 사용해 크기 k를 유지하며, 배열에서 k개의 가장 큰 원소를 효율적으로 찾습니다.

---

마치며

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

관련 태그

#Algorithm #TimeComplexity #BinarySearch #TwoPointer #Sorting