끵뀐꿩긘의 여러가지

◎동적 계획법, 다이나믹 프로그래밍(DP, Dynamic Programming) 분할정복 기법(큰 문제를 작은 문제로 나누어 푸는 방법)을 사용할때, 반복되는 문제의 답을 기록해 둠으로서 그 문제들을 재계산하지 않고 재사용하는 방법. Dynamic(동적)과 Programming(계획법)이라는 뜻과는 전혀 상관없다. 1. 최적 부분 구조(Optimal Substructure): 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다 2. 중복되는 부분 문제 (Overlapping Subproblem): 동일한 작은 문제를 반복적으로 해결해야 한다 의 두가지 조건을 만족할때 사용할 수 있다. ◎ DP 문제 예시-1, 피보나치 수열 피보나치 수는..

◎프림 알고리즘(Kruskal) 프림 알고리즘은 노드를 중점으로 그리디하게 최소 스패닝 트리(MST)를 찾는 알고리즘이다. 영역을 단계적으로 넓혀간다고 생각하면 이해하기 편하다. ※MST의 정의와 MST를 구하는 다른 방법인 크루스칼 알고리즘에 대한 설명 https://kkwong-guin.tistory.com/61 Java - 크루스칼 알고리즘(Kruskal) ◎최소 스패닝 트리(minimum spanning tree) 스패닝 트리(spannig tree)란 신장 트리라고도 하며, 그래프 내의 모든 정점을 사이클 없이 포함하는 트리를 말한다. 하나의 그래프는 여러 개의 스패닝 트리를 kkwong-guin.tistory.com 1. 임의의 정점을 트리에 추가한다. 2. 임의의 정점에서 인접한 정점 중 최..

◎최소 스패닝 트리(minimum spanning tree) 스패닝 트리(spannig tree)란 신장 트리라고도 하며, 그래프 내의 모든 정점을 사이클 없이 포함하는 트리를 말한다. 하나의 그래프는 여러 개의 스패닝 트리를 가질 수 있으며, 사이클이 생기면 안 되므로 N개의 노드에 대하여 정확하게 N-1개의 엣지(간선)를 가진다. 최소 스패닝 트리(minimum spanning tree)란 MST라고도 하며, 그래프가 가질 수 있는 스패닝 트리중 간선의 가중치 합이 가장 작은 트리를 말한다. 스패닝 트리 또한 하나에 그래프에 여러 개일 수 있다. ◎크루스칼 알고리즘(Kruskal) 크루스칼 알고리즘은 간선을 중점으로 그리디하게 최소 스패닝 트리를 찾는 알고리즘이다. 1. 간선의 가중치 값을 기반으로 ..

◎유니온 파인드란? 상호 배타적 집합(Disjoint-set)이라고도 하며, 2가지 연산을 수행한다 1. Find(): 두 요소가 같은 집합에 속하는지 확인한다 2. Union(): 두 요소가 속한 집합을 병합한다. ◎유니온 파인드의 동작 처음에는 병합을 하지 않았기 때문에 각 요소들이 서로 각각의 집합에 속한다. 각각의 집합 이름은 각 요소의 이름이다. Find(1,2)를 하면, 요소 1과 요소 2는 다른 집합에 속하므로 false가 반환된다. Union(1,2)를 하면, 요소 1과 요소 2가 속한 집합이 병합되므로, (집합을 합칠 때는 일반적으로 더 작은 값으로 합치므로 합쳐진 집합의 이름은 더 작은 값인 0이다.) 와 같이 변한다. 이때, Find(1,2)를 하면, 요소 1과 요소 2가 같은 집합에..

◎힙(heap)이란 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리(complete binary tree)를 기본으로 한 자료구조 - 포화 이진 트리(perfect binary tree) 모든 내부 노드가 두 개의 자식 노드를 가지며 모든 잎 노드가 동일한 레벨을 가지는 트리 - 완전 이진 트리(complete binary tree) 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 노드는 왼쪽부터 채워진 트리 위의 완전 이진트리에서 노드를 1개 추가하면, 노드가 왼쪽부터 채워져야 하므로 아래의 그림과 같아진다. ◎힙(heap)의 특징과 종류 -언제나 느슨한 정렬 상태를 유지한다. -최대힙(max heap): 부모 노드의 키 값이 자식 노드의 키 값보다 ..

지금까지 여러 기본 정렬 알고리즘을 알아보고 구현하였다. 여기서는 매우 복잡하지만 실제로 쓰이는 Tim sort, Dual pivot sort 등등과 실용성은 없지만 재미있는 여러 정렬 알고리즘을 소개하겠다. ◎Tim sort https://d2.naver.com/helloworld/0315536 ◎Dual Pivot quick sort https://defacto-standard.tistory.com/38 Dual-Pivot Quick Sort ( Arrays.sort() 내부 정렬 알고리즘 ) Arrays.sort()는 내부적으로 3개의 Sorting을 쓴다. 1. Insertion Sort 2. Merge Sort 3. QuickSort 예전에는 3개를 분리하여서 각각의 경우에 따로 사용을 했지만 ..

◎기수 정렬 가장 작은 자릿수부터 가장 큰 자릿수까지 자릿수(기수) 별로 자리를 찾아주는 방식으로 숫자를 정렬하는 방식 ◎기수 정렬의 특징 1. 비교 정렬(comparison sort)이 아니다 기수 정렬은 데이터를 비교하면서 찾지 않는다. 2. 제자리 정렬(in-place sort)이 아니다 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 한다. 3. 안정 정렬(unstable sort) 정렬되지 않은 상태에서 같은 키값을 가진 원소의 순서가 정렬 후에도 유지된다. ◎기수 정렬의 동작 기수 정렬은 모든 데이터의 길이가 같아야 사용할 수 있다. ex. [aaa,bbb,dsd,gdf,ret] => 모든 데이터의 길이가 3이므로 기수정렬 사용가능 1. 0~9번까지의 Queue를 생성한다 2. 모든 데..

◎셸 정렬 삽입 정렬이 어느 정도 정렬되어 있는 배열에 대해서는 대단히 빠르다는 점을 이용하여, 삽입 정렬을 보완한 알고리즘 ◎삽입 정렬의 문제점 삽입 정렬은 타깃 원소가 앞의 숫자보다 작으면 앞의 원소들을 모두 교환해야 한다는 단점을 가지고 있다. ex. [1,2,3,4,0]인 배열이 있다고하면, 맨 마지막 원소인 0 때문에, [0,2,3,4,1] [0,1,3,4,2] [0,1,2,4,3] [0,1,2,3,4] 의 과정을 거치며 모든 원소들을 교환하는 비효율적인 상황이 발생한다 ◎셸 정렬의 특징 1. 비교 정렬(comparison sort) 셸 정렬은 데이터를 비교하면서 찾는다. 2. 제자리 정렬(in-place sort) 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않는다. 3. 불안..