계수 정렬 - Counting Sort (안정 정렬) 키 값이 0을 포함한 양의 정수일때만 사용 가능한 정렬법이다. 각각 요소인 양의 정수값을 인덱스로 사용하여 해당 배열을 정렬하는 방법이다. 입력 배열 A와 그의 길이 N, 임시배열 T와 T의 길이 K, 출력배열을 R이라고 할때 순서는 다음과 같다. 입력배열 A 전체를 순회하며 각각 ...

퀵 정렬 (불안정 정렬) 이론상 가장 빠른 정렬이다. 그래서 이름이 퀵 정렬이라고 붙었다. 하나의 리스트를 피벗 기준으로 작고 큰 것으로 나누어 정렬 한다. pviot을 어떻게 선정하느냐에 따라서 이 알고리즘의 속도 차이가 매우 커진다. 분할(Divide): 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열로 분할한다. 정복(Co...

정렬 데이터를 사용하려면 특정한 법칙에 따라 분류가 되어있어야한다. 그리고 이런 분류 중에 가장 많이 쓰는 것은 정렬이다. 이런 정렬의 종류를 크게 두 가지로 나누자면 안정 정렬과 불 안정 정렬로 나눌 수 있다. 안정 정렬은 기존의 데이터 순서를 유지한채 정렬이 되는 것이고 불안정 정렬은 기존 데이터 순서와 관계 없이 정렬이 되는 것이다. 그냥...

특정 노드에서 특정 노드로 최소 비용 경로 전체 값이 작은 최소 비용 신장 트리 때와는 달리 특정 노드에서 특정 노드로 이동할때 최소 가중치를 이용한 path를 구축하고 싶을 수 있다. 이럴 때 사용하는 알고리즘은 아래와 같다. 다익스트라 알고리즘(Dijkstra algorithm) 동적 계획법 (Dynamic programming) 기법을 이용해서...

그래프 연산 깊이 우선 탐색 (DFS - Depth First Search) 탐색을 시작하는 노드 v에서 인접하며 방문하지 않은 노드 w를 방문 w에서 인접하며 방문하지 않은 노드를 y를 방문 위 과정을 반복하여 탐색하면 깊이 우선 탐색이다. 재귀 함수를 통하거나 stack을 통해 구현 가능하다. 넓이 우선 탐색 (BFS - Breath Firs...

그래프 점이 있고 이 점이 선으로 연결된 형태를 그래프라고 한다. 이러한 점은 각각 vertex, 정점, 노드라고 불리며 연결한 선은 edge 혹은 간선이라고 부른다. 이전에 트리는 순환 형태가 없는 그래프를 말했지만, 그래프는 순환 형태가 있는 것, 순환 형태가 없는 것을 모두 통칭해서 말한다. 종류 그래프의 종류는 크게 두 종류로 나뉜다. 무방향...

해시테이블 {key, value}로 데이터를 저장하는 자료구조로 원하는 값을 빠르게 검색할 수 있는 자료구조이다. 이러한 속도가 가능한 이유는 해시테이블이 내부 적으로는 배열로 구현되어있고 이러한 배열에 엑세스할 수 있는 인덱스를 해시 함수를 통해 산출해내기 때문에 검색의 대부분의 경우는 매우 빠르다. 해시함수 입력값이 있을 때 함수 f에 넣었 을때...

힙(Heap) 이전에 포스팅했던 완전 이진 트리(Complete Binary Tree)의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다. 큰값이 위에 오는지 작은 값이 위에 오는지 종류에 따라 최대 힙과 최소 힙으로 나눈다. 힙 트리에서는 중복된 값을 허용되는데 ...

트리 점이 있고 이 점이 선으로 연결된 형태를 그래프라고 한다. 이러한 점은 각각 노드, 정점, vertex라고 불리며 연결한 선은 edge 혹은 간선이라고 부른다. 트리는 기본적으로 이러한 그래프에서 파생된 것이다. 순환이 없는 그래프라고 봐도 무방한데 순환이 없는 형태라면 필연적으로 한 개의 노드에서 모든 가지가 나오는 형태로 만들어진다. 이때...

스택과 큐 이번에는 스택과 큐에 대해서 알아보도록 하겠다. 스택 스택은 FILO(First In Last Out) 구조의 자료구조로 책 더미를 생각하면 편하다. 스택에서 데이터 삽입하는 것을 PUSH, 데이터를 빼는 것을 POP이라고 한다. 먼저 들어간 것이 가장 아래에 쌓이기 때문에 가장 나중에 들어간 것이 먼저 나오게 된다. 큐 스택과는 ...