Algorithm

동적계획법(DP)

• 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서, 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘

def fibo_dp(num):
    cache = [ 0 for index in range(num + 1)]
    cache[0] = 0
    cache[1] = 1
    
    for index in range(2, num + 1):
        cache[index] = cache[index - 1] + cache[index - 2]
    return cache[num]

 

퀵정렬

• 기준점(pivot 이라고 부름)을 정해서, 기준점보다 작은 데이터는 왼쪽(left), 큰 데이터는 오른쪽(right) 으로 모으는 함수를 작성함

def qsort(data):
    if len(data) <= 1:
        return data
    
    pivot = data[0]

    left = [ item for item in data[1:] if pivot > item ]
    right = [ item for item in data[1:] if pivot <= item ]
    
    return qsort(left) + [pivot] + qsort(right)

 

 

 

다익스트라 알고리즘

import heapq

def dijkstra(graph, start):
    
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    queue = []
    heapq.heappush(queue, [distances[start], start])
    
    while queue:
        current_distance, current_node = heapq.heappop(queue)
        
        if distances[current_node] < current_distance:
            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

 

 

KRUSKAL 알고리즘

 

parent = dict()

rank = dict()

def find(node):

    # path compression 기법

    if parent[node] != node:

        parent[node] = find(parent[node])

    return parent[node]

def union(node_v, node_u):

    root1 = find(node_v)

    root2 = find(node_u)

    

    # union-by-rank 기법

    if rank[root1] > rank[root2]:

        parent[root2] = root1

    else:

        parent[root1] = root2

        if rank[root1] == rank[root2]:

            rank[root2] += 1

    

    

def make_set(node):

    parent[node] = node

    rank[node] = 0

 

def kruskal(graph):

    mst = list()

    

    # 1. 초기화

    for node in graph['vertices']:

        make_set(node)

    

    # 2. 간선 weight 기반 sorting

    edges = graph['edges']

    edges.sort()

    

    # 3. 간선 연결 (사이클 없는)

    for edge in edges:

        weight, node_v, node_u = edge

        if find(node_v) != find(node_u):

            union(node_v, node_u)

            mst.append(edge)

    

    return mst