알고리즘 — foot-data-engineering

# 자료구조 : 데이터를 어떠한 형태로 저장하고 관리할 것인지에 대한 방법. 그래서 자료구조는 어떻게 효율적으로 자료를 저장할 것인가에 대한 고민이 필요하다.

# 알고리즘 : 저장된 데이터를 찾거나 변형하거나 수정할 때 필요한 방법.

기본

빅O : n이 무한대로 간다고 했을 때 상수항을 제거한 n으로 복잡도를 표현하는 방식
O, 오메가, 쎄타가 있는데, O는 상한선(Upper Bound)으로 최악의 경우, 오메가는 하한선(Lower Bound)으로 최선의 경우, 쎄타(평균)으로 볼 수 있다.
[참고] https://vaert.tistory.com/117

투포인트 기법

두개의 포인터로 연속적으로 값을 순회하는 기법. 한쪽에서 같이 시작하거나 양 끝에서 각자 이동하면서 동작을 수행한다
시간복잡도는 O(n)

Max, Min

최댓값이나 최솟값을 뽑을 때 순회하면서 이를 찾는 방식으로 max_val = max(max_val, new_val) 을 사용한다.

DFS BFS

dfs는 깊이 탐구, dfs는 일반적으로 모든 경로를 탐색할때 사용함.

보통 재귀함수나 스택으로 구현하는 편인데, 이 때 재귀나 스택에 들어갈 인자는 지속적으로 변화하는 상태값을 담아야 한다. 대표적으로 인덱스나 누적시킬 것 등을 추가해야 함. 유연하게 사고해야 쉽게 문제를 풀 수 있음.

bfs는 너비 탐구. bfs는 다익스트라로 최소 경로를 측정할 때 사용함. 보통 Queue로 구현할 수 있음.

def dfs(graph, start_node):
    visited, need_visit = list(), list()
    need_visit.append(start_node)
    
    while need_visit:
        node = need_visit.pop()
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])
    
    return visited
    
    
    
def bfs(graph, start_node):
    visited = list()
    need_visit = list()
    
    need_visit.append(start_node)
    
    while need_visit:
        node = need_visit.pop(0)
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])
    
    return visited

백트래킹

백트래킹은 DFS의 골격을 이루는 알고리즘이라고 보면 되는데, 만약에 없으면 돌아가고, 다시 들어가는 걸 반복하는 작업임

재귀함수

기본적으로 for문으로 구현하는 작업을 더 우아하게 할 수 있음. 함수 안에 재귀가 호출되는 부분 상위 코드는 차례대로 축적된다고 보면 되며 아래 코드는 Stack이 pop되듯이 끝에서부터 터진다고 보면 됨.

재귀함수를 진짜 다양한 패턴으로 연습해봐야 됨. dfs에서 많이 사용되는 편인데, 여러 패턴으로 사용이 가능하므로 익혀두는 게 좋을 듯

이차배열 포인터 문제

이차배열에서는 기본적으로 한 번 베껴내더라도 배열이다. 근데 여기서 문제는 배열이 mutable이므로 값을 변경하는 작업들이 있다면 copy를 해주는 게 좋음. deepcopy나 [:]를 사용하기

중첩함수

중첩함수는 상위 함수의 객체를 그대로 사용할 수 있다는 장점이 있음. 다만 mutable 객체를 변경하려고 하면 변경이 되지 않고 새로운 변수가 중첩 함수 안에 생성이 된다.

순열, 조합

순열인 경우 값들을 전부 조회하면 되기에 간단하게 순회하면서 배열 값을 추가하면 된다.

다만 조합인 경우 순서가 생긴다. 그래서 순서를 유지할 수 있도록 함수 안에서 반복적으로 순회할 배열들을 조절해줘야 한다.

def dfs(elements,start):
 for i in range(start:n+1):
	dfs(...,start+1)
...
dfs(arr, i)

그래프 순회 알고리즘 (다익스트라 & 플로이드 워샬 & MST )

다익스트라는 그리디 알고리즘을 모태로 하며 두 vertex간의 최단 경로를 구할 때 사용되는 알고리즘이다. BFS 방식으로 시작되는 노드로 부터 가중치가 낮은 경로를 뽑아서 앞으로 전진하는 기법임.

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)
        
        # 처음이 아니라 차후 거리 업데이트시 이미 더 짧은거리라면 무시하는 코드
        # 마지막 f떄문에 B로 다시 돌아오네
        if distances[current_node] < current_distance:
            print(current_node,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

플로이드 워샬 은 모든 노드 간의 최단거리를 구하는 알고리즘이다. 다익스트라는 1:N이었다면 플로이드 워샬은 N:N

MST는 그래프에서 순환하지 않으면서 전체를 순회할 수 있는 Spanning Tree 중에 가장 가중치 합이 낮은 Tree 구하는 알고리즘. MST 알고리즘으로 크루스칼, 프림이 있다. 크루스칼은 가중치 기준으로 sort한 후 사이클이 만들어지지 않는다면 순차적으로 간선을 채택하는 방식임 (Find & Union 방식 사용)

참고 : (Min Heap 사용하면 O(NlogN)으로 탐색비용 줄이기)

정렬

버블, 선택, 삽입, 머지, 퀵 등의 여러 정렬이 있다.

버블 정렬 : O(n*2)로 정말로 Brute Force한 방식

선택 정렬, 삽입 정렬 : O(n*2)이나 삽입 정렬은 처음에 정렬 잘 되어있으면 O(n)까지 가능

머지 정렬 : divide and conquer로 동작하며 최선 최악 모두 O(NlogN)으로 동일한 퍼포먼스 보여줌

퀵 정렬 : 파티션 기반으로 동작함. 최선은 O(NlogN)으로 머지 정렬보다 빠를 수 있으나 최악의 경우 O(n^2)라서 안정성이 떨어져 현업에서는 잘 사용되지 않음

팀 정렬 : 파이썬에서 사용하는 sort 기법으로 휴리스틱하게 머지, 퀵의 장점을 섞었다.

다이나믹 프로그래밍

DP(다이나믹 프로그래밍)은 계산 결과를 저장했다가 재활용하는 기법임. 보통 Top Down, Bottom Up 방식이 있으며 Top Down 방식은 재귀, Bottom Up은 for문으로 순차적으로 계산을 하는 방식임.

흔히 DP와 비교되는 것으로 분할정복, 그리디가 있음. 그리디는 앞 선택이 뒤에 영향을 주지 않고 문제의 최적 해결 방법이 부분 문제에도 동일하게 최적일 때 사용된다. Optimal Substructure라고도 함. 로컬 최적해를 구하는 것에만 집중할 뿐 DP 처럼 글로벌 최적화를 구할지는 모른다. 분할 정복은 탑다운 방식으로 문제를 쪼개는 것은 동일하나 부분 문제들이 서로 독립적이라 memoization이 불가능하다.

이진 탐색

정렬된 숫자들 사이에서 특정 값의 위치(Lower Bound, Upper Bound)를 찾는 알고리즘.

Python에서는 보통 bisect.bisect_left를 사용하면 해당 값의 인덱스(만약 값이 없으면 들어가야 할 인덱스 위치를 반환)하며 Lower Bound를 구한다고 보면 된다.

반면 bisect_right는 Upper Bound를 찾을 때 사용된다.

완전 탐색

Brute Force
순열
백트래킹
BFS

DP에서 조심할 것

DP는 크게 dictionary나 list로 사용함

Dictionary

if key in dp: 와 if dp[key] 속도가 차이가 정말 어마어마하다.

if key in dp 를 쓰면 O(1)이고 dp[key]는 key가 없으면 이를 생성하는 과정이 있어서 그런듯

List

아래도 아래가 훨씬 빠르다. 명시적으로 값을 비교해줘야 더 빠르게 비교할 수 있는듯 앞으로 dp 쓸 때 참고하자

dp = [0] * (target+1)
if dp[target] :

**dp = [-1] * (target+1)
if dp[target] != -1 :**

참고 :

https://leetcode.com/discuss/general-discussion/458695/Dynamic-Programming-Patterns

Union & Find

참고 : https://m.blog.naver.com/ndb796/221230967614

합집합을 찾는 의미를 가진 알고리즘으로, 현재 이 두 노드가 서로 같은 그래프에 속하는 지 판별하는 알고리즘.

# 그냥 간선리스트 만들면 되네 ㅇㅇ 전체 구조랑(함수 4개 ㅇㅇ)
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

parent = dict()
rank = dict()

    
def make_set(node):
    parent[node] = node
    rank[node] = 0


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

[TIP]

싸이클이 된다는 것은 Union 코드에서 p1 == p2 일 경우임.

Topological Sort

참고 : https://m.blog.naver.com/ndb796/221236874984

위상 정렬은 보통 Queue를 이용해서 BFS방식으로 구현한다고 함.