알고리즘
1.[알고리즘] 너비 우선 탐색 (BFS)
https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html > 그래프 탐색이란? >> * 하나의 정점으로 부터 시작하여 차례대로 모든 정점들을 한번 씩 방문하는 것 >> EX) 특정 도시에서 다른 도시로 갈 수 있는지 없
2.[알고리즘] 깊이 우선 탐색(DFS)
깊이 우선 탐색(DFS, Depth-First Search) 깊이 우선 탐색(DFS) 이란 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계
3.[알고리즘] 최소신장트리(MST, Minimum-cost Spanning Tree)
Spanning Tree Spanning Tree 란 그래프 내의 모든 정점을 포함하는 트리 Spanning Tree = 신장트리 = 스패닝 트리 신장트리는 그래프의 최소 연결 부분 그래프 이다 최소 연결 = 간선의 수가 가장 적다 n개의 정점을 가지는 그래프
4.[알고리즘] PST-크루스칼(Kruskal) 알고리즘
Kruskal 알고리즘이란 탐욕적인 방법(greedy method) 을 이용하여 네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것 탐욕적인 방법 결정을 해야 할 때마다 그 순간에 가장 좋다고 생각되는 것을 선택함으
5.[알고리즘] Union-Find 알고리즘
Disjoint Set의 개념 Disjoint Set이란 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조 즉, 공통 원소가 없는, 즉 "상호 배타적"인 부분 집합들로 나눠진 원소들에 대한 자료구조이다. Disjoint Set =
6.[알고리즘] MST - 프림(Prim) 알고리즘
Prim 알고리즘이란 시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해나가는 방법 Prim 알고리즘의 동작 시작단계에서는 시작 정점만이 MST집합에 포함된다. 앞 단계에서 만들어진 MST집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리
7.[알고리즘][최단경로 알고리즘] Dijkstra 알고리즘
최단 경로(shortest path) 문제 그래프에서 정점끼리의 최단 경로를 구하는 문제는 여러가지 방법이있다. 1. 하나의 정점에서 다른 하나의 정점까지의 최단 경로를 구하는 문제 (single source and single destination shortest
8.[알고리즘] 최단경로 알고리즘 - Floyd 알고리즘
앞서 다익스트라 알고리즘 포스트에서, 그래프에서 정점끼리의 최단 경로를 구하는 문제가 여러가지 방법이 있다고 했다. 하나의 정점에서 다른 하나의 정점까지의 최단 경로를 구하는 문제(single source and single destination shortest pa
9.[알고리즘][정렬] 선택 정렬(selection sort)
*오름차순 기준으로 정렬한다 선택 정렬(Selection sort) 알고리즘 개념 제자리 정렬(in-place sorting) 알고리즘의 하나 입력 배열(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법 해당 순서에 원소를 넣을 위치는 이미
10.[알고리즘][정렬] 삽입 정렬(insertion sort)
*오름차순을 기준으로 정렬한다 삽입 정렬(insertion sort) 알고리즘 개념 요약 손 안의 카드를 정렬하는 방법과 유사하다. 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입한다. 새로 삽입될 카드의 수 만큼 반복하게 되면 전체 카드가
11.[알고리즘] 버블 정렬(bubble sort)
*오름차순을 기준으로 정렬한다. > 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘 버블 정렬(bubble sort) 알고리즘의 개념 요약 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환
12.[알고리즘] 정렬 - 합병 정렬(merge sort)
분할 정복(Divid and Conquer) 알고리즘의 하나 합병 정렬(merge sort) 알고리즘의 개념 요약 '존 폰 노이만(John von Neumann)' 이라는 사람이 제안한 방법 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알
13.[알고리즘] 정렬 - 셀 정렬(shell sort)
> 가장 오래된 정렬 알고리즘의 하나로, 삽입정렬을 보완한 알고리즘 셸 정렬(shell sort) 알고리즘의 개념 요약 'Donald L. Shell' 이라는 사람이 제안한 방법으로, 삽입정렬을 보완한 알고리즘이다. 삽입정렬이 어느정도 정렬된 배열에 대해서는 대단히
14.[알고리즘] 정렬 - 퀵 정렬(quick sort)
*오름차순을 기준으로 정렬한다 퀵 정렬(quick sort) 알고리즘 개념 요약 '찰스 앤터니 리처드 호어(Charles Antony Richard Hoare)'가 개발한 정렬 알고리즘 퀵 정렬은 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교
15.[알고리즘] 정렬 - 힙 정렬(heap sort)
자료구조 '힙(heap)' 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조 최댓값, 최솟값을 쉽게 추출할 수 있는 자료구조 힙 정렬(heap sort) 알고리즘의 개념 요약 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법 과정 설명 정렬
16.[알고리즘] 정렬 - 위상 정렬(topological sort)
https://gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html
17.[알고리즘] 이분탐색 (Binary Search)
이진탐색이란? 이진 탐색이란 데이터가 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교한다. X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열
18.[알고리즘] 비트마스크 (bit mask)
비트마스크란 무엇인가? 용어 그대로 비트(bit)에 관한 것이다. 알고리즘보다 테크닉 중 하나로써, 정수의 이진수 표현을 활용한 기법이다. 비트마스크를 사용한 코드의 장점 더 빠른 수행시간 더 간결한 코드 더 작은 메모리 사용량 연관 배열을 배열로 대체 : map\