BFS의 응용으로 "어느 한 정점에서 모든 정점까지의 최단 경로"를 찾는데 사용되며, 매 탐색마다 해당 정점까지의 가중치의 합을 최소값으로 갱신시켜나가는 방식이다. 💡다익스트라 특징 가중치 그래프에서 사용되며, 모든 가중치가 음이 아닌 경우에만 적용 한다 =>음의 가중치가 있는 경우에는 벨만-포드 알고리즘을 사용해야한다 우선순위 큐를 사용하여 현재까지 발견된 최단 거리가 가장 작은 정점을 선택하고, 해당 정점과 인접한 정점들의 최단 거리를 갱신한다 다익스트라 알고리즘은 방문하지 않은 노드 중 최단 거리인 노드를 선택하는 과정을 반복한다. 또한 각 단계마다 탐색 노드로 한 번 선택된 노드는 최단 거리를 갱신하고, 그 뒤에는 더 작은 값으로 다시 갱신되지 않는다. 도착 노드는 해당 노드를 거쳐 다른 노드로 ..

기수정렬 기수정렬은 비교 연산을 하지 않으며 정렬 속도가 빠르지만, 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요하다. 가장 큰 자릿수를 D라고 했을 때 0(DN)의 시간 복잡도를 가진다 =>기수 정렬을 사용하기 위해선 데이터의 값들이 동일한 길이를 가지는 숫자나 문자열로 구성되어 있어야 한다. 📌num의 i번째 자리에 있는 수를 반환 코드 function getDigit(num, i) { return Math.floor(Math.abs(num) / Math.pow(10, i)) % 10; } 📌num의 자리 수를 반환 코드 function digitCount(num) { if (num === 0) return 1; return Math.floor(Math.log10(Math.abs(nu..

트리는 노드로 이루어진 재귀적 자료 구조이다 이터를 순차적으로 저장하지 않기 때문에 비선형 자료구조이다 트리는 하나의 루트 노드를 갖는다. 노드(node)들과 노드들을 연결하는 간선(edge)들로 구성되어 있다 노드가 n개인 트리는 항상 n-1개의 간선(edge)을 가진다 트리에는 사이클(cycle)이 존재할 수 없다. 노드들은 특정 순서로 나열될 수도 있고 그럴 수 없을 수도 있다. 각 노드는 부모 노드로의 연결이 있을 수도 있고 없을 수도 있다. 각 노드는 어떤 자료형으로도 표현 가능하다. Node LinkedList와 비슷하게 tree에도 node가 존재한다. 각 node는 데이터를 포함하고 있다 Parent(부모) Child(자식) 부모노드는 다수의 자식 노드를 가지고 있을수 있다 하지만 자식 노..

Greedy Algorithm(탐욕 알고리즘) 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법 =>탐욕 알고리즘은 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 방법이다 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택한다 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사한다 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영..