최단 경로를 구하는 방법은 다양하다. 그 중 다익스트라 알고리즘에 대해 알아보자다익스트라 알고리즘이란?각 경로의 가중치를 비교해서 최단거리 경로를 찾아내는 알고리즘이다.가중치가 양수인 그래프에서 활용이 가능하며, 음수인 경우는 벨만-포드 알고리즘을 사용하면 된다 어떻게 작동할까?다익스트라 알고리즘의 작동 과정은 다음과 같다.1. 출발 노드를 설정한다.2. 최단 거리 테이블을 초기화 한다. 이때 초기화 값은 inf 또는 아주 큰 수로 잡는다.3. 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드를 찾고 해당 노드를 방문 처리한다.4. 해당 노드를 거쳐 다른 노드로 넘어가는 가중치를 계산해 최단 거리 테이블을 업데이트 한다.5. 3~4 과정을 최..

자료구조는 크게 두 종류로 나뉜다.선형 구조와 비선형 구조가 바로 그것이다. 비선형 구조에 속하는 그래프를 소개해 보고자 한다. 그래프란?그래프는 비선형적 자료 구조로, 한정된 Node들 사이에 간선으로 연결된 형태들로 구성된 것들의 집합이다.일반적으로 그래프를 G, node를 V, 간선을 E라고 한다.그래프 사이의 연결은 e1(V1,V2) 이런식으로 나타낸다.해당 그래프가 Directed(방향성) 그래프라면 "V1에서 V2로 가는 e1으로 이어져 있다"정도로 이해하면 되겠다.만약 Undirected(무방향) 그래프 라면 "V1, V2가 e1으로 이어져 있다"로 이해하면 되겠다. 그래프 용어 추가 정리그래프를 다루기 전에 알아야 하는 몇 가지 용어가 있다.먼저 loop이다.루프라는 이름에서 볼 수 있 듯..

지난 글에서는 O(N)인 선형 탐색과 O(logN)인 이분 탐색까지 알아봤다. 그러나 더 빠른 방법이 있다.무려 O(1)이 가능한 Hash방법이다. 마치 마법처럼 '띡' 하고 바로 찾아내는 것이다.Hash란?Hash는 key-value로 데이터를 다루는 방법으로 함수와 테이블로 이루어져 있다.어떤 데이터가 입력으로 들어오면 미리 정해놓은 Hash 함수를 이용해서 특정한 값을 구해낸다.그 다음 그 값에 해당하는 위치에 값을 저장한다.그렇게 하면 나중에 그 값을 찾을 때 똑같이 Hash 함수에 넣어서 그 값이 저장된 곳을 반환하면 즉각적으로 값을 찾을 수 있다. 만약 그 값의 위치가 중복된다면???Hash 알고리즘의 차이는 충돌(collision)이 일어나는 경우에 어떻게 처리하느냐는 것이다.해시 함수를 이..

옛날에 집에서 어떤 책이 다음날 꼭 필요해서 찾으려고 보면 보이지 않는 일이 종종 있었다.결국 집의 모든 책장을 하나하나 뒤져서 찾아내거나, 몇번씩이나 반복해서 찾아봤지만 찾을 수 없었던 기억이 있다.당시에는 인터넷 검색처럼 딱 책 제목을 찾으면 어딨는지 마법처럼 알아내면 좋을 것 같다는 생각을 한 적이 있다.컴퓨터과학을 전공하니 이제는 컴퓨터로 똑같은 짓을 종종한다. 물론 직접 찾지는 않고 컴퓨터가 대신 찾기는 한다. 기초적인 탐색 알고리즘가장 기초적인 탐색 알고리즘은 Linear Search(선형 탐색)이다.말 그대로 있는 데이터를 처음부터 끝까지 순회하면서 찾아내는 방법이다.컴퓨터는 1초에 몇십억번 정도의 연산을 할 수 있기 때문에 O(N)인 이 방법을 사용하면 아주 많은 정보라도 몇초 ~ 몇분 정..

이번 정렬 알고리즘은 분할 정복 기법을 활용한 알고리즘들인 Merge Sort, Quick Sort 그리고 Heap 구조를 사용한 정렬기법인 Heap Sort를 정리해보려고 한다. 분할정복 기법이란?분할 정복이란, 큰 문제를 해결하기 쉬운 작은 문제들로 나눠서 해결해나가 결국 전체 문제를 해결하는 기법이다. 알고리즘 뿐 아니라 정치, 군사 등 다양한 분야에서 사용되는 기법이다.분할 정복 알고리즘의 일반적인 큰 흐름은 다음 세 단계로 요약할 수 있다.1. Divide (분할)정렬해야 할 원소들을 두 개의 크기가 비슷한 그룹으로 나눈다. 예를 들어, 길이가 n인 배열이면 인덱스 0 … (n/2 - 1)을 왼쪽 그룹, 인덱스 (n/2) … (n-1)을 오른쪽 그룹으로 분할한다.2. Conquer (정복, 재귀..

이번에 소개할 알고리즘은 정렬 알고리즘인 Selection Sort와 Insersion Sort이다.두 알고리즘은 모두 최악의 경우 O(N2)의 시간복잡도를 갖는 알고리즘이다. Selection Sort란?Selection Sort는 말 그대로 선택하면서 정렬하는 알고리즘이다.과정은 아래와 같다.1. 앞에서부터 순회하면서 가장 큰 수를 발견하면 맨 뒤로 보내고 고정2. 다시 순회하면서 고정된 범위를 제외하고 가장 큰 수를 발견하면 고정 범위의 앞으로 보내고 고정3. 1과 2의 방법을 반복하면서 고정범위 == 배열의 크기가 될 때까지 진행아래는 정렬되는 예시이다.Selection Sort의 시간복잡도(n-1) 회 반복 * (각 반복마다 최소 요구되는 상수시간 + 적절한 인덱스를 찾는 시간)== O(N2)의..

기존 Binary Search Tree의 문제점기존 BST는 균형이 맞는다는 가정 하에 logN의 시간에 탐색이 가능하다는 장점이 있었지만, 특정 조건 [ex) 일렬로 정렬된 경우]에서 O(n)의 시간복잡도를 갖게 되는 문제점이 발생하기도 한다. 이를 해결하기 위한 Search Tree중 하나가 B-tree다. B-Tree 규칙B-tree는 아래의 규칙을 만족하여야 한다 1. root Node는 최소 하나의 요소를 갖을 수 있다. 이외 모든 다른 Node는 최소 MINIMUN의 요소를 갖어야 한다.* MINIMUN : B-트리를 설계할 때 정해둔 최소 허용 요소 수를 의미하며, 보통 B-트리 차수(order) m에 대해 ⌈m/2⌉−1 또는 ⌈m/2⌉처럼 정의한다.** 여기서 차수 M이라는 것은 한 Nod..

Heap이란?Heap은 다음 두 규칙을 따르는 이진 트리의 일종이다.각 node가 가지고 있는 값은 각 node의 자식 node들이 가지고 있는 값보다 크거나 같아야 함(최대 힙의 경우)트리는 완전 이진 트리를 유지해야 하는데, 즉 가장 아래 레벨을 제외한 모든 레벨이 가능한 한 꽉 차 있어야 함.최대, 최소 값을 빠르게 찾기 위한 자료구조이므로 BST랑 비교했을 때 비슷하다고 생각할 수도 있지만 Heap은 왼쪽 오른쪽 상관없이 상하 관계에 따라서만 크기 결정이 된다는 차이점이 있다. Heap을 이용한 우선순위 큐(priority queue) ADTHeap 구조를 이용하는 우선순위 큐는 다음의 룰을 만족하면 된다.각 요소는 우선순위가 더 높은 상태로 유지가 되어야 한다.(부모 노드가 자식 노드보다 높은..

이진탐색트리(BST)란?이진 트리의 한 종류로, 아래의 특징을 만족한다.각 node는 뚜렷한 데이터 값을 갖는다.더 작거나 또는 더 큰 값으로 key 값이 분류될 수 있다.모든 node는 오른쪽 서브 트리보다 작고, 왼쪽 서브 트리보다 크다. node 탐색하기node를 탐색하는 방법은 간단하다.현재 node가 target이 아니라면, 크기 비교를 한다.작다면 왼쪽 서브 트리로, 크다면 오른쪽 서브 트리로 이동한다.만약 해당 노드가 leaf노드라면 false를 반환한다.위 과정을 반복하면서 target을 찾는다. node 추가하기node를 추가하는 방법도 쉽다.탐색하는 방법과 유사하게 tree를 내려가면서 해당 값이 들어갈 자리를 찾아서 추가해주면 된다. 예를 들어 16이라는 값을 추가한다고 하면45 v..

Binary Tree특징root 라는 특별한 노드가 존재오직 왼쪽 / 오른쪽 두가지 child node만 가질 수 있음각 node는 정확히 1개의 부모 node를 갖음트리의 깊이 : leaf node 중 가장 깊은 node의 깊이 Full Binary tree(정 이진트리)모든 leaf node가 같은 깊이를 갖으면서, 모든 잎이 아닌 node가 2개의 자손이 있는 것Complete Binary Tree (완전 이진 트리)가능한 먼 노드들을 왼쪽부터 채워나가는 이진 트리Array representation of Complete Binary Tree완전 이진트리는 배열을 이용해서 구현할 수 있다.위와 같은 형태의 완전 이진 트리가 있다고 가정해보자.그럼 임의의 배열 arr에 아래와 같이 저장할 수 있다. ..