justgo_developer

최소 스패닝 트리(Minimum Spanning Tree, MST)란? 최소 스패닝 트리의 정의는 그래프에서 그래프의 모든 정점을 연결하되, 사이클이 존재하지 않도록 모든 정점을 간선으로 연결하는 것을 의미한다. 이때, 간선의 가중치 합을 최소로 하며 연결하여야 한다. 이때 생성되는 최소 스패닝 트리는 무조건 하나의 그래프에서 하나만 생성된다고는 보장하지 못한다. Generic MST 알고리즘- 어떤 MST의 부분집합 A에 대해서 A∪{(u,v)}도 역시 어떤 MST의 부분집합이 될경우 에지(u,v)는 A에 대해서 안전하다(safe)고 한다.- Generic MST 알고리즘1. 처음에는 A는 공집합이다.2. 집합 A에 대해서 안전한 에지를 하나 찾은 후 이것을 A에 더한다.3. 에지의 개수가 n-1개가 ..

플로이드 워셜 알고리즘(Floyd-Warshall) All-pairs 문제 그래프에서 모든 정점 사이의 최단경로 및 최단거리를 구하는 알고리즘 동적계획법 접근으로, 그래프 상의 모든 두 정점을 잇는 경로의 최단거리를 구한다.여기에 경유지를 기록하면 최단거리 경로까지 구할 수있다.- 두 정점을 잇는 최소 비용 경로는 경유지를 거치거나 거치지 않는 경로 중 하나에 속한다.- 만약 경유지를 거친다면 그것을 이루는 부분 경로 역시 최소 비용 경로여야 한다. 음수사이클이 없는 그래프라면 음수 가중치가 있어도 동작

벨만-포드 알고리즘(Bellman-Ford Algorithm) single source 문제 음수 가중치가 있고, 음수 사이클이 없는 그래프에서 한정점에서 다른 모든 정점까지의 최단경로 및 거리를 구하는 알고리즘음수사이클이 있으면 무한히 사이클을 루프할수 있어서 최단경로를 구할수 없다.단 벨만포드알고리즘의 장점은 그래프내에 음수사이클이 있음을 판단할수 있다. 1. 시작점을 제외한 모든 정점들을 최단거리를 무한대로 설정2. 그래프 모든 간선에 대해3. 정점 A에서 B로의 방향을 가지고 있는 각 간선에 대해현재 정점 B까지의 거리가 정점 A까지의 거리 + 현재 간선의 거리의 합보다 클경우정점 B의 경로와 거리를 갱신해준다.4. 이들 경로와 거리의 갱신이 일어나지 않을때까지 반복한다.만약 정점의 수 만큼의 시..

최단경로(shortest path problem)- 가중치(방향) 그래프 G=(V,E), 즉 모든 에지에 가중치가 있음- 경로 p=(v0,v1,...vk)의 길이는 경로상의 모든 에지의 가중치의 합- 노드 u에서 v까지의 최단경로의 길이를 S(u,v)라고 표시하자. 최단경로문제의 유형- Single-source(one-to-all) : 하나의 출발 노드 s로부터 다른 모든 노드까지의 최단 경로를 찾아라. ex)Dijkstra의 알고리즘- Single-destination : 모든 노드로부터 하나의 목적지 노드까지의 최단 경로를 찾아라./ single-source문제와 동일- Single-pair(one-to-one) : 주어진 하나의 출발 노드 s로부터 하나의 목적지 노드 t까지의 최단 경로를 찾아라- ..

위상정렬: 그래프를 정렬하는 것/ 정렬기준은 진입 차수의 비 내림차순 순서즉, 진입차수가 0개->N개 순으로 탐색하고정렬하면서 진입차수가 0인 노드들은 제거하고, 진입차수가 0이 아닌 노드들은 0으로 수정한 뒤 제거해가며 정렬진입차수란? 해당 노드로 들어오는 간선의 개수 위상정렬은 DAG그래프여야 한다.DAG란 Directed Acyclic Graph 방향성이 있고 사이클이 없는 그래프위상정렬은 DFS 방법과 진입차수(Indegree)를 이용한 방법이 있다.

힙 정렬(Heap Sort): 힙 자료구조를 이용한 정렬 방법: 힙에서 항상 가장 큰 원소가 루트노드가 되고 삭제 연산을 수행하면 항상 루트노드의 원소를 삭제하여 반환 힙 정렬 수행 방법1. 정렬한 원소들을 입력하여 최대 힙 구성2. 힙에 대하여 삭제 연산을 수행하여 얻은 원소를 마지막 자리에 배치3. 나머지 원소에 대해서 다시 최대 힙으로 재구성 (원소의 개수만큼 반복 수행) 정렬되지 않은 [69,10,30,2,16,8,31,22]의 자료들을 힙정렬-> 정렬할 원소가 8개 이므로 노드가 8개인 완전 이진 트리를 만들고 최대 힙으로 구성1. 힙에 삭제 연산을 수행하여 루트 노드의 원소 69를 구해서 배열의 마지막 자리에 저장한다. 그리고 나머지 원소들에 대해서 최대 힙으로 재구성 평균 시간복잡도 : O(..

배열의 경우, 인덱스나 주소값을 통해서 한번에 해당값에 접근할수있다.대신에 길이가 가변적이지 못하다. 링크드리스트의 경우, 길이가 고정되지 않는 대신 원하는 값을 찾기 위해 각 노드를 일일이 순회해야 한다. 최악의 경우 O(n) 해시 테이블(hash table): 키 값의 연산에 의해 직접 접근이 가능한 구조: 데이터의 해시 값을 테이블 내의 주소로 이용하는 궁금의 탐색 알고리즘-> 탐색 성능이 향상됐지만 공간은 희생함 해싱(hashing): 해시테이블을 이용한 탐색: 자료를 검색할 때, 탐색이나 첨자가 아닌 내용에 의해 필요한 자료에 도달하는 기법 자료를 찾아주는 함수를 해싱함수라고 한다.서로 다른 자료가 해싱 함수에 의해 같은 값을 생성하는 경우 충돌(Collision)이라고 한다.탐색시간이 O(1)..

knapsack problem- n개의 아이템과 배낭- 각각의 아이템은 무게 Wi와 Vi를 가짐- 배낭의 용량 W- 목적 : 배낭의 용량을 초과하지 않으면서 가격이 최대가 되는 부분집합예Greedy - 가격이 높은 것부터 선택- 무게가 가벼운 것부터 선택- 단위 무게당 가격이 높은것부터 선택->불가능 순환식bottom-up

LCS(Longest Common Subsequence) 순환식 항상 순환식은 base케이스로 수렴하는지 확인해야한다. 동적계획법

힙이란 최대값 및 최소값을 찾아내는 연산을 하기 위한 완전이진트리를 기본으로 한 자료구조- 완전이진트리- 부모노드의 키 값이 자식 노드의 키 값보다 크다(최대힙) or 작다(최소힙) 노드 삽입- 우선, 삽입하려는 노드를 완전이진트리의 맨 마지막 자리에 추가한 뒤,부모노드와 크기를 비교해가면서 대소관계아 따라 노드를 교환하여 힙으로 다시 만드는 과정을 거친다.노드 삭제- 힙에서 노드의 삭제는 루트노드를 삭제하면서 반환한다는 의미이다. 최대값이나 최소값을 찾아내는 연산을 하기 위한 트리이기 때문이다.노드에 노드가 하나도 남지 않을때까지 삭제연산을 반복해 반환된 노드들을 순서대로 늘어놓으면 오름차순 혹은 내리참순으로 정렬된 배열이 된다. 이를 힙정렬이라고한다. 루트노드와 맨마지막 노드의 자리를 바꾼다. 이렇게..