[알고리즘] 코딩테스트 단골 알고리즘(이진탐색/정렬/그래프탐색) 설명, 예제 코드

코딩 테스트에서 자주 다뤄지는 알고리즘 몇 가지와 간단한 설명 및 예시 코드를 제시하겠습니다

 

1. 이진 탐색 Binary Search

• 정렬된 배열에서 특정 값을 찾는 알고리즘
• 중간 값을 선택하여 찾고자 하는 값과 비교하고 탐색 범위를 반으로 줄여나감
• 시간 복잡도 : $O(logN)$
• 예제 코드

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

# 사용 예시
my_list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 6
result = binary_search(my_list, target)
print(f"Index of target: {result}")  # Output: Index of target: 5

 

 

2. 정렬 알고리즘 Sorting Algorithms

• 배열이나 리스트의 요소들을 특정한 순서로 재배치하는 알고리즘
• 대표적으로 선택 정렬 Selection Sort, 삽입 정렬 Insertion Sort, 퀵 정렬 Quick Sort, 병합 정렬 Merge Sort 등이 있음
• 각 정렬 알고리즘마다 시간 복잡도와 장단점이 다르므로 상황에 맞는 선택이 필요함
• 예제 코드

# 선택 정렬(Selection Sort)
def selection_sort(arr):
    for i in range(len(arr)):
        min_idx = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

# 사용 예시
my_list = [5, 3, 8, 2, 1, 7]
selection_sort(my_list)
print(my_list)  # Output: [1, 2, 3, 5, 7, 8]

 

 

3. 그래프 탐색 알고리즘 Graph Traversal Algorithm

• 그래프 내의 노드를 탐색하는 알고리즘
• 대표적으로 깊이 우선 탐색 Depth-First Search, DFS와 너비 우선 탐색  Breadth-First Search, BFS가 있음
• DFS는 스택 또는 재귀함수를 사용하며, BFS는 큐를 사용하여 구현함
• 예제 코드

# 깊이 우선 탐색(DFS)
def dfs(graph, start):
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            stack.extend(graph[node] - visited)
    
    return visited

# 사용 예시
my_graph = {'A': {'B', 'C'},
            'B': {'A', 'D'},
            'C': {'A', 'E'},
            'D': {'B'},
            'E': {'C'}}
start_node = 'A'
result = dfs(my_graph, start_node)
print(result)  # Output: {'A', 'B', 'C', 'D', 'E'}

 

이외에도 많은 다양한 알고리즘이 코딩 테스트에서 다뤄집니다. 

탐색, 동적 프로그래밍, 그리디 알고리즘, 백트래킹, 분할 정복 등 다양한 아록리즘 개념을 학습하고 실습하여 문제 해결 능력을 키워나가야 합니다.