포시코딩

크루스칼 알고리즘(Kruskal's algorithm) 탐욕 알고리즘을 기반으로 한다. 모든 정점을 독립적인 집합으로 만든다. 모든 간선을 비용(가중치)을 기준으로 정렬하고, 비용이 작은 간선부터 양 끝의 두 정점을 비교한다. 두 정점의 최상위 정점을 확인하고, 서로 다를 경우 두 정점을 연결한다. (사이클이 생기지 않도록) 간단히 말해서, 모든 정점을 리스트로 만든 후 비용이 적은 간선부터 하나씩 연결하되 사이클이 생기지 않게 하면 된다. 언제까지? 모든 노드들이 연결될 때까지 과정 아래와 같은 그래프가 있다고 가정할 때, 크루스칼 알고리즘으로 최소 신장 트리를 구하는 과정에 대해 알아보자 1. 가장 가중치가 작은 간선은 5의 가중치를 가진 A-D, C-E가 있다. 뭘 먼저 선택하든 상관없지만 우선 A..

신장 트리(Spanning Tree) Spanning Tree 또는 신장 트리. Spanning Tree가 더 많이 사용된다. 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프를 의미 신장 트리의 조건 본래의 그래프의 모든 노드를 포함 모든 노드가 서로 연결 트리의 속성을 만족(사이클이 존재하지 않음) 최소 신장 트리(MST) Minimum Spanning Tree, MST라고 불린다. 가능한 신장 트리(Spanning Tree)중에서, 사용된 간선들의 가중치 합이 최소인 Spanning Tree를 지칭한다. 그래프에서 최소 신장 트리를 찾을 수 있는 알고리즘이 존재한다. 대표적인 최소 신장 트리 알고리즘은 아래와 같다. 크루스칼 알고리즘(Kruskal's algorithm)..

백트래킹이란? 백트래킹 또는 퇴각검색이라고 불린다. 기법의 한 종류 제약 조건 만족 문제(Constraint Satisfaction Problem)에서 해를 찾기 위한 전략 해를 찾기 위해, 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 backtrack하고, 바로 다른 후보군으로 넘어가며 결국 최적의 해를 찾는 방법 실제 구현 시, 고려할 수 있는 모든 경우의 수(후보군)를 상태 공간 트리(State Space Tree)를 통해 표현한다. 각 후보군을 DFS 방식으로 확인 상태 공간 트리를 탐색하면서, 제약이 맞지 않으면 해의 후보가 될만한 곳으로 바로 넘어가서 다시 탐색 Promising: 해당 루트가 조건에 맞는지 검사하는 기법 Pruning..

최단 경로 문제란? 두 노드를 잇는 가장 짧은 경로를 찾는 문제 가중치 그래프(Weighted Graph)에서 간선(Edge)의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적 문제 종류 단일 출발 및 단일 도착 그래프 내의 특정 노드 u에서 출발, 또 다른 특정 노드 v에 도착하는 가장 짧은 경로를 찾는 문제 단일 출발 그래프 내의 특정 노드 u와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제 출발점이 A라고 한다면 A가 아닌 각각 다른 노드들 간의 최단 경로를 찾는걸 의미 다익스트라 알고리즘이 여기에 해당됨 전체 쌍(all-pair) 그래프 내의 모든 노드 쌍(u, v)에 대한 최단 경로를 찾는 문제 다익스트라 알고리즘 첫 정점을 기준으로 연결되어 있는 정점들을 추가해가며 최단..

자료구조 손코딩 배열 큐 스택 링크드리스트 해쉬 트리 힙 그래프 기본 알고리즘 정렬 버블 삽입 선택 퀵 병합 계수 이진 탐색 최대공약수 공식 소수 판별 + 에라토스테네스의 체 BFS, DFS 구현 코드 순열, 조합 구현 코드 최단 경로(다익스트라) 알고리즘 머리에 박아넣자

에라토스테네스의 체란? 2부터 주어진 숫자까지의 소수들을 찾는 방법으로 고대 그리스 수학자 에라토스테네스가 발견하였다. 원리는 2부터 주어진 숫자까지 모든 구간의 수를 나열한 후 2부터 시작해 발견되는 소수의 배수를 지워나가는 방식으로 소수를 찾는다. 자세한 방법은 위키백과에 나와있다. - [링크] 코드 1. 자신을 포함 안시키는 경우 def prime_list(n): # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주) sieve = [True] * n # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사 m = int(n ** 0.5) for i in range(2, m + 1): if sieve[i] == True: # i가 소수인 경우 for j in ran..

순열(Permutation) 서로 다른 n개의 원소에서 r개를 중복 없이 순서에 상관있게 선택하는 혹은 나열하는 것 nPr로 표현되며 공식으로는 아래와 같이 나타낼 수 있다. n! / (n-r)! DFS 트리와 체크리스트를 사용하는 방법이 가장 쉽다. 체크리스트는 말 그대로 내가 어디로 갔었는지를 기억해야 하기 때문에 임시로 사용하는 체크용 리스트 순열 알고리즘 코드는 그냥 외우는걸 추천 구현 코드 n = [1, 2, 3] r = 2 result = [0] * r checklist = [0] * len(n) def DFS(L): if L == r: print(result) else: for i in range(len(n)): if checklist[i] == 0: result[L] = n[i] check..

탐욕 알고리즘이란? 최적의 해에 가까운 값을 구하기 위해 사용 여러 경우 중 하나를 결정해야 할 때마다, 매 순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행하여 최종적인 값을 구하는 방식 예시 문제 문제 1. 동전 문제 지불해야 하는 값이 4720원일 때 10원, 50원, 100원, 500원 동전으로 동전의 수가 가장 적게 지불하시오. 가장 큰 동전부터 최대한 지불하는 방법으로 구현 가능 탐욕 알고리즘으로 매 순간 최적이라고 생각되는 경우를 선택 코드 coin_list = [500, 100, 50, 10] def min_coin_count(value, coin_list): total_coin_count = 0 details = list() coin_list.sort(reverse=True) # 큰..

DFS 알고리즘 구현 스택, 큐 자료구조 활용 need_visit stack visited queue * BFS 자료구조는 두 개의 큐를 활용하는데 반해, DFS는 스택과 큐를 활용한다는 차이가 있다. 개념 위 그래프에 대해 DFS를 구현한다면 다음과 같은 순서로 진행된다. 1. 제일 처음 노드 A를 need_visit stack에 추가한다. (시작) 2. need_visit stack에서 pop한 뒤 temp_node로 가져온다. (BFS에서 dequeue하던 것과 대조됨) 3. temp_node가 visited queue에 존재하는지 확인 4-1. 없다면 visited queue에 A를 추가 4-2. 존재한다면 아무것도 하지 않고 2번부터 다시 시작 5. temp_node였던 A를 graph_dict..

BFS 알고리즘 구현 큐 자료구조 활용 need_visit queue visited queue 개념 위 그래프에 대해 BFS를 구현한다면 다음과 같은 순서로 진행된다. 1. 제일 처음 노드 A를 need_visit queue에 추가한다. (시작) 2. need_visit queue에서 dequeue 한 뒤 temp_node로 가져온다. (코드에선 list를 사용하기 때문에 pop(0)을 통해 dequeue했다.) 3. temp_node가 visited queue에 존재하는지 확인 4-1. 없다면 visited queue에 A를 추가 4-2. 존재한다면 아무것도 하지 않고 2번부터 다시 시작 5. temp_node였던 A를 graph_dict에서 key로 찾아 나온 value를 need_visit queu..