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

1. 원시 타입(Primitive Type) 자바스크립트 데이터는 두 가지 타입으로 나뉜다. 첫 번째는 원시타입, 두 번째는 참조타입이다. 원시 타입(Primitive Type)은 String, Number, Boolean, undefined, null, symbol 총 여 섯개의 타입이 있으며 다음과 같이 선언을 한다. const num = 123; const str = "hello"; const NULL_POINT = null; num, str, NULL_POINT 변수 모두 선언해준 값을 가지고 있다. 메모리는 이러한 변수, 값들을 다음과 같은 이미지 형태로 저장한다. 그렇다면, 다음과 같이 새로운 변수를 만들어 기존에 선언했던 변수 값을 = 연산자를 이용해서 복사한다면? let num1 = 123..

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

1. 문제 설명 문제 설명을 보고 내가 난독증인가 했다. 나만 이해를 못한건가 싶어서 바로 질문하기 버튼을 누르니, 나같은 사람이 정말 많았다. 출제자도 논란이 많은 것을 알고 그런지 모르겠지만, 문제 맨 밑에 H-index에 대한 설명이 담긴 위키링크를 걸어뒀다. 위키에서는 H-index를 다음과 같이 구하라고 써있었다. 배열을 내림차순으로 정렬해라. 인덱스 번호[배열 인덱스 + 1] 내림차순 정렬: [4, 3, 2, 1] index + 1 b-a); let idx = 1; while(idx

1. Primitive Type Primitive라는 단어를 사전에서 찾아보면 원시적인, 초기의라는 뜻이 나온다. 지금 생각해보면 왜 이런 단어선택을 했는지는 이해는 안간다. 본론으로 돌아와서, 자바스크립트는 Primitive Type과 Reference Type이라는 두 가지 형태의 자료형이 존재한다. Primitive Type는 총 여섯 개다. true or false -> boolean type null -> 존재하지 않음을 정의 undefined -> 존재하지 않음 number -> 정밀한 64비트의 float형 자료. 자바스크립트에서는 정수형이라는 자료형태가 없다. string -> 문자형 자료 symbol(ES6에서 나온 새로운 자료형) 여기서 null과 undefined를 헷갈려 하는 사람들..

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