1. 이진 검색 이진 검색(Binary Search)은 자료 가운데 있는 항목을 키 값과 비교하여 더 크면 오른쪽 부분을 검색하고, 키 값이 더 작으면 왼쪽 부분을 검색하는 방법이다. 이진 검색(Binary Search)은 퀵 정렬과 마찬가지로 분할과 정복 기법을 사용하기 때문에 시간 복잡도가 O(log₂N)으로 엄청나게 빠른 속도를 자랑한다. 하지만 이진 검색은 삽입, 삭제를 수행한 후에 항상 배열의 상태를 정렬된 상태로 유지해야 하는 작업이 따로 필요하다. 그 이유는 이진 검색(Binary Search)이 정렬된 순차 자료구조에서만 사용할 수 있기 때문이다. 2. 동작 순서 퀵 정렬의 동작을 제대로 알고 있다면, 이진 검색(Binary Search)의 동작도 쉽게 이해할 수 있을 것이다. 이진 검색의..

1. 가중치 그래프 가중치 그래프는 간선에 가중치를 할당한 그래프를 말한다. 가중치 그래프에서 간선에 주어진 가중치는 비용, 거리, 시간을 의미하는 값이 될 수 있다. 크루스칼(Kruskal) 알고리즘은 비용, 거리, 시간을 최소화하는 신장트리를 만들기 위해 나온 알고리즘이다. 즉, 모든 가중치의 합이 최소 값이 되어야 한다는 것이다. 최소 값이 나오게 하려면, 가중치를 오름차순으로 n-1만큼 더하면 된다. 그런데 앞에서 크루스칼 알고리즘에 대해 설명할 때 신장트리라는 말을 한 적이 있다. 신장 트리란, n 개의 정점을 가진 그래프 G에서 모든 정점이 n-1개의 간선으로 이루어진 트리를 말한다. 2. 크루스칼(Kruskal) 알고리즘 크루스칼 알고리즘은 두 가지 방법이 있다. 첫 번째 방법은 가중치가 높..

1. 너비 우선 탐색 너비 우선 탐색은 시작 정점으로부터 인접한 정점들을 모두 차례로 방문한 후 방문했던 정점을 다시 시작점으로 하여 인접한 정점들을 차례로 방문하는 방법이다. 깊이 우선 탐색과 반대의 움직임을 보인다고 생각하면 된다. 깊이 우선 탐색이 세로 본능이라면 너비 우선 탐색은 가로본능이라고 생각하면 된다. 정확히는 거리로 보면 된다. A에서 1떨어진 노드는 B, C 다. 고로 B와 C는 형제다. 하지만 B, C와 A는 부모-자식 관계다. 깊이 우선 탐색은 자식부터 탐색을 하는 구조다. 하지만 너비 우선 탐색은 주변 인접노드, 형제를 먼저 탐색하는 구조다. 너비 우선 탐색은 인접한 정점들에 대해서 차례로 다시 너비 우선 탐색을 반복해야 하므로 선입 선출의 구조를 갖는 큐 자료구조를 사용한다. 2..

1. 그래프 그래프란 연결되어있는 원소 간의 관계를 표현하는 자료구조를 말한다. 버스 노선도, 전철 노선도, 인간관계를 나타내는 연결구조는 구조가 너무나도 다양하고 복잡하기 때문에 선형 자료구조나 트리로 표현할 수 없다. 그래프는 연결할 객체를 나타내는 정점(vertex)과 객체를 연결하는 간선(edge)로 구성된다. 그래프 G를 G = (V, E)로 정의하는데, V는 정점들의 집합을 의미하고, E는 정점을 연결하는 간선의 집합을 의미한다. 2. 그래프의 종류 (1) 무방향 그래프 무방향 그래프는 간선에 방향이 없는 그래프를 말한다. 무방향 그래프는 정점 V₁과 정점 V₂를 연결하는 간선을 (V₁, V₂) 로 표현한다. 아래 [그림 1]은 무방향 그래프를 나타낸 그림이다. 위 무방향 그래프 G를 정점의 ..

1. Array.fill([]) 자료구조 책을 보고 기수정렬을 프로그래밍할 때 였다. 기수 정렬 포스팅에서는 버킷이라는 객체를 만들때 오브젝트 자체를 생성했지만, 원래는 이 차원 배열을 만들려고 했었다. 하지만 그러지 못했다. 왜냐하면 Array.fill([]) 함수 때문이었다. 다음 프로그램을 보자. const arr = new Array(3).fill([]); arr[0].push(1); /* 이 함수의 출력은? */ console.log(arr); /* 정답 */ /* [ [1], [1], [1] ] */ 위 프로그램의 출력 결과는 무엇일까? 나는 arr의 첫 번째 원소 배열에만 1이라는 요소가 추가될 줄만 알았다. 하지만 결과는 아니었다. 모든 원소 배열에 1이 추가됐던 것이다. 내가 키워드를 잘..

1. 기수 정렬 기수 정렬은 분배 방식의 정렬 방법으로 정렬할 원소의 키값에 해당하는 버킷에 원소를 분배하였다가 버킷의 순서대로 원소를 꺼내는 방법을 반복하는 배열이다. 기수 정렬은 원소의 키를 표현하는 값의 기수만큼의 버킷이 필요하고, 키 값의 길이만큼 기수 정렬을 반복한다. 숫자는 기본적으로 10진수로 표현되기 때문에, 키 값을 가진 원소들을 정렬할 때는 0부터 9까지 총 10 개의 버킷을 사용한다. 정렬의 반복 횟수는 입력 배열의 원소 중 최대 값의 길이 만큼이다. 예를 들어 [103, 3, 22]를 기수정렬을 이용하여 반복해야 할 때, 입력 배열 중에서는 103이 최댓값이므로, 기수 정렬의 반복횟수는 103의 길이인 3이 된다. 2. 동작 순서 길이가 5인 입력배열 [3, 55, 7, 17, 1]..