코딩 테스트 문제를 풀다보면 마주치게 되는 크루스칼 알고리즘에 대해 알아봤다. What is Kruskal’s algorithm? 최소 비용 신장 부분 트리를 찾는 알고리즘 변의 개수를 E, 꼭짓점의 개수를 V라고 하면 이 알고리즘의 시간복잡도는 O(ElogV) 노드와 간선으로 이루어진 그래프가 있을 때, 가장 적은 비용으로 노드를 연결하는 방법을 찾는 알고리즘이다. 주로 간선마다 가중치가 있을 때 가장 적은 비용으로 연결하기 위해 사용한다. How it works 위키백과의 크루스칼 알고리즘 예제를 통해 어떻게 동작하는지 알아보자. 간선 옆에 있는 숫자는 변의 가중치를 가리킨다. 지금은 모든 간선의 색이 검정색이다. 앞으로 연결된 선은 녹색으로, 연결할 수 없는 선은 빨강으로 나타낸다. 가중치가 가장 작은 간선을 고른다. 지금처럼 가중치가 가장 작은 선이 두개을 경우 아무거나 골라 선택하면 된다. AD 와 CE 중 AD를 선택하고, AD는 연결된 선이기 때문에 녹색으로 변경한…

그래프의 모든 노드를 방문하려면 어떻게 해야 할까? 가장 대표적인 탐색방법인 DFS와 BFS에 대해 알아보자. Depth First Search (DFS) 한 길을 깊게 파서 탐색 자신과 연결된 노드 중 한 노드를 탐색 탐색 과정 다음과 같은 그래프가 있다. 1. 시작 노드에서 갈 수 있는 노드 중 하나를 선택하여 탐색한다. 그래프에서 0 을 시작 노드로 정하고, 갈 수 있는 노드 중 1 을 선택했다. 2. ① 과 같은 방법으로 탐색을 반복한다. (이미 방문한 노드는 선택지에서 제외) 1번 노드에서 갈 수 있는 선택지 0 과 2 중, 0은 이미 방문했으므로 2를 선택한다. 2번 노드에서 갈 수 있는 선택지 0 과 3 중, 0은 이미 방문했으므로 3를 선택한다. 3. 다음으로 탐색해야 할 노드가 없다면 해당 노드를 호출한 부모 노드로 돌아가 더 탐색해야 할 노드가 있는지 찾는다. 3번 노드에서 더 이상 갈 수 있는 선택지가 없으므로, 2번 노드로 돌아간다. 2번 노드에서는…

트리(Tree)란? 계층적인 구조를 나타내며, 부모-자식 관계의 노드들로 이루어짐 리스트, 스택, 큐와 같은 선형 자료구조가 아닌 비선형 자료구조 컴퓨터 디스크의 디렉터리 구조도 트리에 해당한다. 트리 용어 node: 트리의 구성요소 root: 부모가 없는 노드 subtree: 하나의 노드와 그 노드의 자손들로 이루어진 트리 terminal node(단말노드): 자식이 없는 노드 non-terminal node(비단말노드): 적어도 하나의 자식을 가지는 노드 level: 트리의 각 층의 번호 트리의 height(높이): 트리의 최대 레벨 노드의 degree(차수): 노드가 가지고 있는 자식 노드의 개수 edge(간선): 노드와 노드를 연결하는 선 트리의 degree(차수): 트리가 가지고 있는 노드의 차수 중에서 가장 큰 차수 forest: 트리들의 집합 이진트리(Binary tree)란? 자식 노드의 개수가 최대 2개인 트리 자료구조 서브트리 간에 순서가 존재하여 왼쪽과 오른쪽 …

특정 수가 소수인지 판별해내는 함수를 JavaScript로 구현하고자 합니다. 먼저 소수가 무엇인지 알아봅시다. 소수(Prime Number)란? 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수 위를 통해 소수의 기준을 다음과 같이 정의할 수 있습니다. 1보다 큰 자연수 1과 자기 자신만이 약수 간단하게 소수판별함수 구현하기 소수 은 과 자기자신만을 약수로 가지므로, 까지의 수로 나눴을 때 나머지가 이 아닙니다. 이를 이용해 간단한 소수 판별 함수를 만들 수 있습니다. 숫자 을 부터 까지 나눴을 때 나머지가 인지 체크합니다. 이 함수의 시간 복잡도는 입니다. 더 효율적인 소수판별함수 구현하기 소수 판별 함수를 더 빠르게 돌릴 수 있는 방법입니다. 보다 더 큰 수는 합성수이거나 소수일 수 밖에 없습니다. 직접 해보면 이해됩니다. 참고로 합성수는 1보다 큰 자연수 중 소수가 아닌 수를 의미합니다. 따라서 숫자 을 부터 까지 나눴을 때 나머지가 인지 체크합니다. 이 함수의 시…