Software Algorithm 10

1. DFS (깊이 우선 탐색, Depth-First Search)

• 사용: 그래프 탐색, 백트래킹, 경로 찾기
• 특징: 한 경로를 끝까지 탐색한 후 다른 경로로 넘어가는 방식
• 응용 문제: 미로 찾기, 섬의 개수 세기, 그래프에서의 경로 탐색

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end=' ')
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

2. BFS (너비 우선 탐색, Breadth-First Search)

• 사용: 그래프 탐색, 최단 경로 탐색
• 특징: 가까운 노드부터 탐색하는 방식 (큐를 사용)
• 응용 문제: 최단 경로 문제, 미로 찾기

from collections import deque

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True
    while queue:
        v = queue.popleft()
        print(v, end=' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

3. 이진 탐색 (Binary Search)

• 사용: 정렬된 배열에서의 탐색
• 특징: 중간값과 비교해 탐색 범위를 절반씩 줄여나가는 방식
• 응용 문제: 특정 값 찾기, 범위를 빠르게 좁히는 문제

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

4. 다익스트라 알고리즘 (Dijkstra's Algorithm)

• 사용: 가중치가 있는 그래프에서의 최단 경로 탐색
• 특징: 우선순위 큐(최소 힙)를 사용해 현재까지의 최단 경로를 계속 갱신하는 방식
• 응용 문제: 특정 노드에서 다른 노드까지의 최단 경로

import heapq

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

5. 동적 계획법 (Dynamic Programming, DP)

• 사용: 작은 문제를 풀고, 그 결과를 저장해서 큰 문제를 푸는 방식
• 특징: 재귀적 접근과 메모이제이션을 사용해 중복 계산을 피함
• 응용 문제: 피보나치 수열, 배낭 문제, 최소 비용 경로

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

6. 최소 신장 트리 (Minimum Spanning Tree, MST)

• 사용: 그래프에서 모든 정점을 연결하는 최소 비용의 트리 구하기
• 주요 알고리즘: Kruskal's Algorithm, Prim's Algorithm
• 응용 문제: 네트워크 연결, 도로 건설
• 크루스칼 알고리즘 (Kruskal's Algorithm):
  • 간선을 정렬한 후 최소 비용으로 연결하는 방식 (Union-Find 사용)

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

def union(parent, a, b):
    rootA = find(parent, a)
    rootB = find(parent, b)
    if rootA < rootB:
        parent[rootB] = rootA
    else:
        parent[rootA] = rootB

7. 투 포인터 (Two Pointer)

• 사용: 배열에서 두 개의 포인터를 사용해 특정 조건을 만족하는 구간 찾기
• 특징: 양 끝에서 포인터를 이동시켜가며 문제 해결
• 응용 문제: 부분합 구하기, 특정 구간 찾기

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

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

• 사용: 고정된 크기 또는 가변적인 크기의 구간을 이동하면서 문제 해결
• 특징: 부분 합, 최대값/최소값을 구하는 문제에 적합
• 응용 문제: 최대 부분합 구하기, 문자열에서 특정 패턴 찾기

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

9. 유니온 파인드 (Union-Find)

• 사용: 그래프에서 연결된 컴포넌트를 찾는 알고리즘
   
• 특징: 집합을 합치고 연결 여부를 판단할 때 사용 (서로소 집합)
• 응용 문제: 사이클 판별, 네트워크 연결 여부 확인

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

def union(parent, a, b):
    rootA = find(parent, a)
    rootB = find(parent, b)
    if rootA != rootB:
        parent[rootB] = rootA

10. 백트래킹 (Backtracking)

• 사용: 가능한 모든 경우를 탐색하면서 조건을 만족하는 해를 찾는 방식
• 특징: 해를 찾다가 조건에 맞지 않으면 이전 단계로 돌아가는 방식
• 응용 문제: N-Queen 문제, 부분 집합 구하기

def backtracking(path, choices):
    if 조건에 만족:
        결과 저장
        return
    for choice in choices:
        if 조건에 맞는 choice:
            backtracking(path + [choice], choices)

이 외에도 정렬 알고리즘(퀵 정렬, 병합 정렬), 그리디 알고리즘, 문자열 처리 알고리즘(KMP, 라빈-카프 알고리즘) 등이 코딩 테스트에서 자주 사용됩니다.