코딩테스트에 주로 등장하는 알고리즘

코딩테스트에 주로 등장하는 알고리즘

코딩테스트는 개발자의 문제 해결 능력과 알고리즘 이해도를 평가하는 중요한 과정입니다. 이러한 테스트에서 주로 등장하는 알고리즘을 미리 학습하고 연습하면, 실전에서 더 나은 성과를 거둘 수 있습니다. 이번 포스팅에서는 코딩테스트에 자주 등장하는 알고리즘과 그 예제를 소개하겠습니다.

1. 정렬 알고리즘

정렬 알고리즘은 데이터를 특정 순서대로 정렬하는 방법을 말합니다. 코딩테스트에서 자주 등장하는 정렬 알고리즘은 다음과 같습니다:

• 버블 정렬 (Bubble Sort):
  • 가장 간단한 정렬 알고리즘 중 하나로, 인접한 두 요소를 비교하여 정렬합니다.
  • 시간 복잡도: O(n^2)
• 삽입 정렬 (Insertion Sort):
  • 배열의 요소를 순차적으로 비교하여 올바른 위치에 삽입합니다.
  • 시간 복잡도: O(n^2)
• 퀵 정렬 (Quick Sort):
  • 분할 정복 알고리즘의 하나로, 피벗을 기준으로 배열을 나누어 정렬합니다.
  • 시간 복잡도: 평균 O(n log n)
• 병합 정렬 (Merge 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)

arr = [3, 6, 8, 10, 1, 2, 1]
print(quick_sort(arr))

2. 탐색 알고리즘

탐색 알고리즘은 데이터 구조 내에서 원하는 값을 찾는 방법을 말합니다. 주로 사용되는 탐색 알고리즘은 다음과 같습니다:

• 이진 탐색 (Binary Search):
  • 정렬된 배열에서 절반씩 범위를 줄여가며 탐색합니다.
  • 시간 복잡도: O(log n)
• 너비 우선 탐색 (Breadth-First Search, BFS):
  • 그래프 또는 트리에서 가까운 노드부터 탐색합니다.
  • 시간 복잡도: O(V + E) (V는 노드 수, E는 간선 수)
• 깊이 우선 탐색 (Depth-First Search, DFS):
  • 그래프 또는 트리에서 깊이 우선으로 탐색합니다.
  • 시간 복잡도: O(V + E)

예제 문제:

• "정렬된 배열에서 주어진 값을 찾는 프로그램을 작성하시오."

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

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(binary_search(arr, 5))

3. 그래프 알고리즘

그래프 알고리즘은 노드와 간선으로 구성된 그래프 구조를 탐색하거나 최적의 경로를 찾는 방법을 말합니다. 주요 알고리즘은 다음과 같습니다:

• 다익스트라 알고리즘 (Dijkstra's Algorithm):
  • 가중치가 있는 그래프에서 최단 경로를 찾는 알고리즘입니다.
  • 시간 복잡도: O(E + V log V)
• 벨만-포드 알고리즘 (Bellman-Ford Algorithm):
  • 가중치가 음수일 수 있는 그래프에서 최단 경로를 찾는 알고리즘입니다.
  • 시간 복잡도: O(VE)
• 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm):
  • 모든 노드 쌍 간의 최단 경로를 찾는 알고리즘입니다.
  • 시간 복잡도: O(V^3)

예제 문제:

• "가중치가 있는 그래프에서 주어진 시작 노드에서 모든 노드로의 최단 경로를 찾으시오."

import heapq

def dijkstra(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    pq = [(0, start)]
    while pq:
        current_distance, current_node = heapq.heappop(pq)
        if current_distance > distances[current_node]:
            continue
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
    return distances

graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}
print(dijkstra(graph, 'A'))

4. 동적 계획법 (Dynamic Programming)

동적 계획법은 복잡한 문제를 작은 하위 문제로 나누어 해결하는 방법입니다. 주로 중복되는 계산을 줄여 효율성을 높입니다.

• 피보나치 수열 (Fibonacci Sequence):
  • 동적 계획법을 사용하여 피보나치 수를 계산합니다.
• 배낭 문제 (Knapsack Problem):
  • 제한된 용량의 배낭에 최대 가치를 담는 방법을 찾습니다.
• 최장 공통 부분 수열 (Longest Common Subsequence):
  • 두 시퀀스의 최장 공통 부분 수열을 찾습니다.

예제 문제:

• "피보나치 수열의 n번째 값을 동적 계획법으로 구하시오."

def fibonacci(n):
    fib = [0, 1]
    for i in range(2, n + 1):
        fib.append(fib[i - 1] + fib[i - 2])
    return fib[n]

print(fibonacci(10))

5. 문자열 알고리즘

문자열 알고리즘은 문자열을 처리하고 분석하는 방법을 말합니다. 코딩테스트에서 자주 등장하는 알고리즘은 다음과 같습니다:

• KMP 알고리즘 (Knuth-Morris-Pratt):
  • 문자열에서 부분 문자열을 찾는 효율적인 알고리즘입니다.
  • 시간 복잡도: O(n + m)
• 라빈-카프 알고리즘 (Rabin-Karp):
  • 해시 함수를 사용하여 문자열에서 부분 문자열을 찾습니다.
  • 시간 복잡도: 평균 O(n + m)
• 트라이 자료구조 (Trie):
  • 문자열 집합을 저장하고 효율적으로 검색할 수 있는 자료구조입니다.

예제 문제:

• "문자열에서 특정 패턴을 찾는 프로그램을 작성하시오."

def kmp(pattern, text):
    def compute_lps(pattern):
        lps = [0] * len(pattern)
        length = 0
        i = 1
        while i < len(pattern):
            if pattern[i] == pattern[length]:
                length += 1
                lps[i] = length
                i += 1
            else:
                if length != 0:
                    length = lps[length - 1]
                else:
                    lps[i] = 0
                    i += 1
        return lps

    lps = compute_lps(pattern)
    i = j = 0
    matches = []
    while i < len(text):
        if pattern[j] == text[i]:
            i += 1
            j += 1
        if j == len(pattern):
            matches.append(i - j)
            j = lps[j - 1]
        elif i < len(text) and pattern[j] != text[i]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    return matches

text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
print(kmp(pattern, text))

결론

코딩테스트에서 자주 등장하는 알고리즘을 미리 학습하고 연습하면, 실전에서 더 나은 성과를 거둘 수 있습니다.