다락방

동적계획법(DP : Dynamic Programming) 작은 문제들을 풀면서 그 결과를 저장해 나아가면서 전체 문제를 해결하는 알고리즘 중복 계산을 줄여서 계산속도를 높일 수 있으며 경우의 수가 많은 경우에도 효율적으로 계산할 수 있다 일반적으로 재귀로 구현되며 메모이제이션(memoization) 기법을 사용하여 중복 계산을 피한다 메모이제이션 - 이전에 계산된 결과를 저장하고 다음에 동일한 계산에 필요할 때 저장된 결과를 이용하여 중복계산을 피함으로서 성능을 향상 시킬 수 있다. 구현단계 문제를 하위 문제로 쪼갠다 하위 문제를 재귀적으로 해결한다 결과를 저장한다(메모이제이션, 테블레이션) 저장된 결과를 이용해 큰 문제를 해결한다. 동적 계획법 조건 최적부분구조(Optimal Substucture) 전..

그리디 알고리즘(Greedy Algorithm) 최적의 값을 구해야 하는 상황에서 사용되는 근시안적인 방법론 각 단계에서 최적이라고 생각되는것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘 이다. 항상 최적의 값을 보장하는 것이 아니라 최적의 값의 ‘근시값’을 목표로 하고 있다. 그리디 알고리즘 주요속성 탐욕선택속성(Greedy Choice Property) 각 단계에서 ‘최선의 선택’을 했을때 전체 문제에 대한 최적해를 구할 수 있는 경우 최적부분구조(Optimal Substructure) 전체 문제의 최적해가 부분 문제의 최적해로 구성 될 수 있는 경우 전체 문제를 작은 부분 문제로 나누어 각각의 부분 문제에서 최적의 해를 구한 다음 이를 조합해 전체 문제의 최적해를 구하는 것을..

Prim 알고리즘 시작 정점에서 출발하여 신장트리 집합을 단계적으로 확장해 나가는 방법 동작 시작 단계에서는 시작 정점만이 MST에 포함 앞 단계에서 만들어진 MST집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장한다. 즉, 낮은 가중치를 먼저 선택한다. 위의 과정을 트리가 (N-1) 개의 간선을 가질 때까지 반복한다. 정점선택을 기반으로 하는 알고리즘 이전 단계에서 만들어진 신장트리를 확장하는식

Union-Find Disjoint Set을 표현할 때 사용하는 알고리즘 서로 중복되지 않는 부분집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조 집합을 구현하는데 비트벡터, 배열, 연결리스트를 이용할 수 있으나 그 중 효율적인 트리구조를 이용하여 구현 연산 make-set(x) 초기화 x를 유일한 원소로 하는 새로운 집합을 만든다. union(x,y) 합하기 x가 속한 집합과 y가 속한 집합을 합친다. find(x) 찾기 x가 속한 집합의 대표값(루트노드값)을 반환한다. x가 어떤 집합에 속해있는지 찾는 연산 전체 집합이 있을 때 구성 원소들이 겹치지 않도록 분할 하는데 자주 사용 최악의 상황 트리 구조가 완전 비대칭인 경우 연결리스트 형태 트리의 높이가 최대가 된다. 원소의 개수가 N일..

크루스칼(Kruskal) 탐욕적인 방법(greedy method)을 이용하여 네트워크(가중치 그래프)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것 탐욕적인 방법 결정을 할 때마다 그 순간 가장 좋다고 생각 되는것을 선택함으로서 최종적인 해답에 도달하는 것 탐욕적인 방법은 그 순간에는 최적이지만, 전체적인 관점에서 최적이라는 보장이 없기 때문에 반드시 검증해야한다. Kruscal 알고리즘은 최적의 해답을 주는 것으로 증명되었다. 동작 그래프의 간선들을 가중치의 오름차순으로 정렬한다. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다. 즉 가장 낮은 가중치를 먼저 선택한다. 사이클을 형성하는 간선을 제외한다. 해당 간선을 현재의 MST의 집합에 추가한다. 특징 간선선택을..

플로이드 워셜 모든 지점에서 다른 모든 지점까지의 최단 경로를 구하는 알고리즘 단계마다 ‘거쳐가는 노드’를 기준으로 알고리즘을 수행한다. 하지만 매 단계마다 방문하지 않은 노드 중에서 최단거리를 갖는 노드를 찾을 필요가 없다. 2차원 테이블에 최단 거리 정보를 저장한다. DP알고리즘에 속한다 노드 개수가 N이라고 할 때, N번만큼의 단계를 반복하며 ‘점화식에 맞게’ 2차원 리스트를 갱신하기 때문에 DP라고 볼 수 있다. 시간복잡도 O(N^3)

다익스트라 그래프의 한 정점에서 다른 정점까지의 최단 경로를 구하는 알고리즘 중 하나이다. 이 과정에서 도착 정점뿐만 아니라 모든 다른 정점까지 최단경로로 방문하여 각 정점까지의 최단 경로를 모두 찾게된다. 매번 최단 경로의 정점을 선택해 탐색을 반복하는 것이다. 동작과정 출발노드와 도착노드를 설정한다 ‘최단 거리 테이블’을 초기화 한다. 현재 위치한 노드의 인접노드 중 방문하지않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 짧은 노드를 선택한다. 그 노드를 방문처리한다. 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용(가중치)를 계산해 ‘최단 거리 테이블’ 을 업데이트 한다. 3-4 과정을 반복한다. ‘최단거리 테이블’ 은 1차원 배열로, N개의 노드까지 오는데 필요한 최단거리를 기록한다. N개..

위상정렬(Topological Sorting) 순서가 정해져 있는 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘. 사이클이 없는 방향, 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것. 진입차수와 진출차수 진입차수(Indegree) : 특정한 노드로 들어오는 간선의 개수 진출차수(Outdegree) : 특정한 노드에서 나가는 간선의 개수 동작과정 큐를 이용해 구현한다. 진입차수가 0 인 노드를 큐에 넣는다. 큐가 빌 때까지 다음의 과정을 반복한다 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다 새롭게 진입차수가 0이 된 노드를 큐에 삽입한다. 위상정렬을 수행할 수 있는 그래프는 사이클이 없는 방향 그래프(DAG)이여야 한다. 위상정렬의 특징 위상정렬은 사..

DFS(Depth-First Search) 깊이 우선 탐색 알고리즘 특정한 경로를 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문 한 후 다시 돌아가 다른 경로로 탐색하는 알고리즘 DFS는 스택 자료구조를 이용한다(보통 재귀함수를 이용해 DFS를 구현한다.) 동작과정 탐색 시작노드를 스택에 삽입 후 방문 처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접노드를 스택에 넣고 방문처리를 한다. 방문하지 않은 인접노드가 없으면 최상단 노드를 꺼낸다. 2를 수행할 수 없을때까지 반복한다. def DFS(graph,v,visit): visited[v] = True print(v) for i in graph[v]: if not visited[i]: DFS(graph,i,vi..

병합정렬(Merge Sort) 하나의 리스트를 두개의 균일한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법. 동작과정 Divide - 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다 Conquer - 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면(left < right) 순환호출을 이용해 다시 분할 정복 방법을 적용한다. Combine - 정렬된 부분 배열들을 하나의 배열에 병합한다. def merge_sort(arr): def sort(low, high): if high - low < 2: return mid= (low + high) // 2 sort(low, mid) sort(mid, high) me..