다락방

AVL Tree 자가균형 이진 탐색트리의 한 유형 각 노드의 서브트리 높이 차이가 최대 1을 유지하도록 스스로 균형을 유지하는 트리 이 서브트리의 높이 차이를 균형계수(BalanceFactor, BF)라 한다. 그렇기 때문에 삽입, 삭제 연산을 수행할 때마다 트리의 균형계수를 체크하고, 균형계수가 1보다 커질 때 회전(Rotation) 연산을 통해 균형을 유지한다. 검색, 삽입, 삭제 모두 O(logN) 하지만 삽입, 삭제시마다 회전연산을 수행하기에 연산속도가 느릴 수 있다. 회전연산의 종류 왼쪽 - 왼쪽 오른쪽 - 오른쪽 Single rotation 왼쪽 - 오른쪽 오른쪽 - 왼쪽 double rotation 특징 이진 검색 트리 모든 노드의 두 하위 트리의 높이는 최대 1까지 차이가 난다. 트리의 모..

최장 공통 부분수열(Longest Common Subsequence) 최장 공통 문자열Longest common substring 점화식 if i == 0 or j == 0: LCS[i][j] = 0 elif string_A[i] == string_B[j] LCS[i][j] = LCS[i-1][j-1] + 1 else: LCS[i][j] = 0 동작 문자열 A, 문자열 B의 한 글자씩 비교한다. 두 문자가 다르다면 LCS[i][j]에 0을 표시 두 문자가 같다면 LCS[i-1][j-1] 값을 찾아 + 1 위 과정을 반복한다. 이 과정이 성립하는 이유는 공통 문자열은 연속 되어야 하기 때문에 현재 두 문자가 같을 때 두 문자의 앞 글자 까지가 공통 문자열이라면 계속 공통 문자열이 이어질 것이고, 아니라면 ..

동적계획법(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의 집합에 추가한다. 특징 간선선택을..

신장트리(Spanning Tree) 그래프 내의 모든 정점을 포함하는 트리 그래프의 최소 연결 부분 그래프다. 최소연결 : 간선의 수가 가장 적다 n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 spanning tree가 된다. 그래프에서 일부 간선을 선택해서 만든 트리 특징 BFS,DFS 를 이용해서 그래프에서 신장트리를 찾을 수 있다. 탐색 도중에 사용된 간선만 모으면 만들 수 있다. 하나의 그래프에서 많은 신장 트리가 존재할 수 있다. Spanning tree는 트리의 특수한 형태이므로 모든 정점들이 연결 되어 있어야 하고 사이클을 포함해서는 안된다. Spanning tree는 그래프에 있는 n개의 정점을 정확히 ..

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

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