코딩 테스트를 위한 '알고리즘'

알고리즘은 주어진 문제를 해결하는 단계적인 절차이다. 효율적인 알고리즘을 선택하면 시간과 공간을 절약할 수 있고, 문제를 더 빠르게 해결할 수 있기에 알아둬야겠지? (맨날 까먹는다)

---

Brute Force

브루트포스 알고리즘은 모든 가능한 경우의 수를 다 고려하여 문제를 해결하는 방법이다. 이 알고리즘은 매우 직관적이고 구현하기 쉽지만, 경우의 수가 많을 경우 시간 복잡도가 매우 커질 수 있다. 따라서 주로 제한이 적거나, 문제의 크기가 작은 경우에 유용하다.

특징

• 단순하고 직관적: 알고리즘이 매우 간단하고 이해하기 쉬움.
• 시간 복잡도: 문제의 크기에 따라 O(n^2), O(n!)와 같은 높은 시간 복잡도를 가질 수 있음.
• 모든 경우의 수를 시도: 최적화된 방법을 사용하지 않고, 가능한 모든 경우를 시도하는 방식이다.

사용 사례

• 가능한 조합, 순열을 모두 탐색하는 문제.
• 제한이 작은 문제에서 최적의 해답을 구할 때.
• 문제를 해결하는 데 있어 간단한 접근 방식이 필요한 경우.

주어진 배열에서 두 수의 합이 특정 값이 되는지 확인하는 문제를 브루트포스로 해결할 수 있다. 이 경우 배열의 모든 요소를 두 개씩 비교하면 된다.

def brute_force_two_sum(nums, target):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return (nums[i], nums[j])
    return None

nums = [2, 7, 11, 15]
target = 9
print(brute_force_two_sum(nums, target))  # (2, 7)

 

이진 탐색 (Binary Search)

이진 탐색은 정렬된 배열에서 특정 값을 찾기 위해 사용되는 알고리즘이다. 이 알고리즘은 배열을 반으로 나누어 검색 범위를 좁혀 나가며, O(log n)의 시간 복잡도를 가진다. 따라서 정렬된 배열에서 원하는 값을 빠르게 찾을 수 있다.

특징

• 시간 복잡도: 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  # 값이 없으면 -1 반환

arr = [1, 3, 5, 7, 9]
target = 5
print(binary_search(arr, target))  # 2 (5는 인덱스 2에 있음)

 

그리디 알고리즘 (Greedy Algorithm)

그리디 알고리즘은 매 단계에서 최적의 선택을 하는 알고리즘이다. 이 알고리즘은 전체 문제에 대한 최적해를 구하는 것이 아니라, 지역적으로 최적인 선택을 반복하며 해결한다. 그리디 알고리즘은 항상 최적해를 보장하지 않지만, 많은 경우에 유용하게 사용될 수 있다.

특징

• 단계별로 최적의 선택을 한다.
• 전역 최적해를 구하지 않지만, 지역 최적 선택이 전체 최적을 이룬다고 가정한다.
• 간단하고 직관적인 알고리즘으로, 구현이 비교적 쉽다.
• 그러나 모든 문제에 적합하지 않다. 일부 문제에서는 그리디 알고리즘이 최적의 해를 보장하지 않을 수 있다.

사용 사례

• 최소 신장 트리 (Prim, Kruskal 알고리즘)
• 활동 선택 문제
• 동전 교환 문제

주어진 동전들로 특정 금액을 만들기 위한 최소 동전 개수를 구하는 문제이다. 그리디 알고리즘을 이용하여 가장 큰 동전부터 사용하여 최소 동전 개수를 구할 수 있다.

def greedy_coin_change(coins, target):
    coins.sort(reverse=True)  # 큰 동전부터 사용
    result = 0
    for coin in coins:
        result += target // coin
        target %= coin
    return result

coins = [1, 5, 10, 25]
target = 30
print(greedy_coin_change(coins, target))  # 2 (1 x 25, 1 x 5)

 

다이나믹 프로그래밍 (Dynamic Programming)

다이나믹 프로그래밍(DP)은 문제를 더 작은 부분 문제로 나누어 해결하고, 그 결과를 저장하여 중복 계산을 피하는 알고리즘이다. 이 방법은 최적화 문제를 해결하는 데 유용하며, 같은 문제를 여러 번 계산하지 않도록 하여 시간 복잡도를 크게 줄일 수 있다.

특징

• 부분 문제의 해결 결과를 저장하여 중복 계산을 방지한다.
• 하위 문제 해결의 결과를 상위 문제 해결에 재사용한다.
• 재귀적으로 문제를 해결하되, 이전 결과를 메모이제이션(Memoization) 방식으로 저장하여 계산 효율성을 높인다.
• 보통 탐색 공간을 줄이는 방식으로 작동한다.

사용 사례

• 피보나치 수열
• 최단 경로 문제 (다익스트라, 플로이드-워셜)
• 배낭 문제 (Knapsack problem)
• 문자열 편집 거리 (Levenshtein Distance)

피보나치 수열을 계산하는 문제에서 다이나믹 프로그래밍을 활용할 수 있다. 중복 계산을 피하고, 이전 계산 결과를 저장하여 효율적으로 구할 수 있다.

# 다이나믹 프로그래밍을 활용한 피보나치 수열 계산
def fib(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]

print(fib(10))  # 55

 

BFS (Breadth-First Search)

BFS(너비 우선 탐색)는 그래프나 트리에서 넓이 우선으로 탐색하는 알고리즘이다. BFS는 시작 노드에서 가까운 노드부터 차례로 탐색하며, 큐를 이용해 구현된다.

특징

• 시작 노드에서 가까운 노드부터 탐색한다.
• 큐(Queue)를 사용하여, 각 노드를 탐색한 후 그에 연결된 노드를 차례로 큐에 넣어 탐색한다.
• 최단 경로를 찾는 데 유용하다.

사용 사례

• 최단 경로 찾기: 특정 노드에서 다른 노드까지의 최단 경로를 찾는 데 사용된다.
• 너비 우선 탐색이 필요한 문제에서 사용된다.
• 그래프의 연결 요소를 찾는 데 유용하다.

다음은 BFS를 사용하여 그래프에서 특정 노드를 탐색하는 코드이다.

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])

    while queue:
        node = queue.popleft()
        if node not in visited:
            print(node, end=" ")  # 방문한 노드 출력
            visited.add(node)
            queue.extend(graph[node] - visited)  # 연결된 노드를 큐에 추가

# 그래프 표현 (인접 리스트)
graph = {
    1: {2, 3},
    2: {1, 4},
    3: {1, 5},
    4: {2},
    5: {3}
}

bfs(graph, 1)  # 1 2 3 4 5

 

DFS (Depth-First Search)

DFS(깊이 우선 탐색)은 그래프나 트리에서 깊이 우선으로 탐색하는 알고리즘이다. DFS는 스택(혹은 재귀 호출)을 이용해 구현된다. DFS는 가능한 한 깊게 탐색하고, 더 이상 깊게 갈 수 없으면 다시 돌아와 다른 경로를 탐색한다.

특징

• 시작 노드에서 가능한 한 깊게 탐색한다.
• 스택(Stack)을 사용하여 탐색하며, 재귀를 이용한 구현도 가능하다.
• 경로가 깊고 복잡한 그래프에서 유용하다.

사용 사례

• 그래프 탐색 및 트리 탐색에서 사용된다.
• 경로 찾기 및 백트래킹 문제에서 유용하다.
• 모든 경로 탐색이 필요할 때 사용된다.

다음은 DFS를 사용하여 그래프에서 모든 노드를 탐색하는 코드이다.

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=" ")  # 방문한 노드 출력

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

# 그래프 표현 (인접 리스트)
graph = {
    1: {2, 3},
    2: {1, 4},
    3: {1, 5},
    4: {2},
    5: {3}
}

dfs(graph, 1)  # 1 2 4 3 5

 

최소 힙 (Min Heap)

최소 힙(Min Heap)은 우선순위 큐를 구현하는 자료 구조로, 부모 노드가 자식 노드보다 작은 값을 갖는 완전 이진 트리 형태로 데이터를 저장한다. 최소 힙은 루트 노드가 항상 가장 작은 값을 가지며, 이 값을 빠르게 꺼낼 수 있다. 이 구조는 삽입과 삭제가 효율적으로 이루어지며, 우선순위 큐에서 자주 사용된다.

특징

• 부모 노드가 항상 자식 노드보다 작은 값을 가진다.
• 루트 노드는 가장 작은 값을 가진다.
• 완전 이진 트리 형태로 구현된다.
• 삽입과 삭제가 O(log n)의 시간 복잡도를 갖는다.

사용 사례

• 우선순위 큐를 구현할 때 사용된다.
• 다익스트라 알고리즘과 같은 최단 경로 알고리즘에서 우선순위 큐가 필요할 때 사용된다.
• 힙 정렬에서 사용된다.

파이썬에서는 heapq 모듈을 사용하여 최소 힙을 쉽게 구현할 수 있다. heapq는 최소 힙을 기본으로 제공하며, 힙의 가장 작은 값을 빠르게 추출할 수 있다.

import heapq

# 최소 힙을 이용한 예시
heap = []

# 최소 힙에 값 삽입
heapq.heappush(heap, 3)  # O(log n)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)

# 최소 힙에서 가장 작은 값 추출
print(heapq.heappop(heap))  # 1 (최소값)
print(heapq.heappop(heap))  # 2
print(heapq.heappop(heap))  # 3