[Algorithm] 분할 정복 (Divide and Conquer)
Divide and Conquer (DAC : 분할 정복) 문제를 더이상 나눌 수 없을 때까지 나누고, 나누어진 문제를 각각 개별적으로 풀어 전체 문제에 대한 답을 얻는 알고리즘 장점 : 문제를 나누어 풀기 때문에 성능 우수 단점 : 재귀 함수를 사용...
[Algorithm] 최단경로 (Shortest Path) - 다익스트라(Dijkstra)
Shortest Path (최단 경로 알고리즘) 최단 경로 알고리즘 가중치 그래프(Weighted Graph)에서 한 정점에서 다른 정점으로 갈때, 가중치 합이 최소가 되도로 하는 경로를 찾는 알고리즘 G = (V, E) 최단 경로 알고리즘 종류 ...
[Algorithm] 최소신장트리 (MST) - 크루스칼(kruskal), 프림(Prim)
Minimum Spanning Tree (MST: 최소신장트리) - Kruskal(크루스칼), Prim(프림) Spanning Tree 속성 최소 가장자리 수를 갖는 동일한 가중치의 Minimum Spanning Tree가 여러 개 존재 가능 주어진 그...
[Algorithm] 그래프 순회(Graph Traversal) - BFS, DFS
Graph Traversal (그래프 순회) - BFS, DFS Breath First Search (BFS) 너비우선 탐색 Queue 인접점 우선 모든 인접 노드를 탐색하는 그래프 순회 알고리즘 가장 가까운 노드를 선택하고 탐색되지 않은 모든 ...
[Algorithm] 해시(hash), 자바로 해시테이블 구현하기
Hash (해시) hashing 은 데이터를 저장할 index를 간단한 연산으로 구현하는 것 hash function을 통해 얻어지는 값이 hash value, hash code, hash라고 함 hash table 데이터의 해시 값을 테이블내의...
[Algorithm] 검색(Search) - 선형 검색, 이진 검색 정의 및 구현
Search (검색) - Linear Search (선형 검색), Binary Search (이진 검색) 순서화된 리스트(ordered list)에서 어떤 원소의 위치 및 존재유무를 찾는 것 탐색문제의 해 또는 결과 : 원소의 위치 보통, 자료구조 형...
[Algorithm] 정렬(Sort)-기수 정렬(Radix Sort)
정렬(Sort) - 기수 정렬(Radix Sort) Radix Sort(기수 정렬) bucket(=queue) 에 분배하면서 정렬하는 방법 LSD : Least Signification Digit (최하위 자릿수) 우선 정렬 MSD : Most Si...
[Algorithm] 정렬(Sort)-병합 정렬(Merge Sort)
정렬(Sort) - 병합정렬(Merge Sort) merge sort (병합 정렬) Divide and Conquer 알고리즘 여러 개의 정렬되어있는 배열 자료들을 혼합하여 하나의 정렬된 배열로 합치는 작업 재귀 용법 사용 연산 리스트의...
[Algorithm] 정렬(Sort)-힙 정렬(Heap Sort)
정렬(Sort) - 힙 정렬(Heap Sort) Heap Sort(힙 정렬) 내부정렬 알고리즘 키를 비교하여 선택에 의하여 정렬하는 선택방식 정렬 Max-Heap(최대 힙) : 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 커야 함 M...
[Algorithm] 정렬(Sort)-퀵 정렬(Quick Sort)
정렬(Sort) - 퀵 정렬(Quick Sort) Quick Sort(퀵 정렬) Divide and Conquer 알고리즘 평균수행능력이 가장 뛰어남 분할중심값을 pivot 또는 control key 라고 함 연산 피벗값을 선택(맨 오...