Fundamental/Algorithm (6) 썸네일형 리스트형 [JavaScript] 요세푸스 순열 문제 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. ((n,k) => { let arr = []; let result = []; for( let i=1; i 다익스트라(Dijkstra's) 알고리듬 간략 정리 그래프의 시작 정점에서 다른 정점까지의 최단 경로를 계산하는 알고리듬 중 하나입니다. 다익스트라는 매 상황에서 비용이 가장 적게 드는 경로를 선택해 최단 경로를 계산하며, 거리를 계산하던 도중 현재까지 알고 있던 경로 비용보다 새로 알게된 경로의 총 비용이 더 적다면 총 비용을 갱신합니다. 1) 시작 정점을 설정 2) 시작 정점을 기준으로, 인접한 정점까지의 최소 비용을 저장 3) 아직 방문하지 않은 정점 중, 총 비용이 낮은 정점을 선택 4) 해당 정점을 거쳐서 특정 정점으로 가는 경우를 고려하여, 그 특정 정점까지의 최소 비용을 갱신 5) 위 과정에서 3~4번을 반복 위 그래프의 경우, 1번에서 5번 정점까지 최단 경로의 비용을 계산하고 있고, 저장과 갱신을 반복해서 최종적으로 최단 경로를 계산하게 .. 최소 비용 신장 트리 알고리즘 간략 정리 목차 1. 신장 트리(Spanning Tree) 2. Kruskal 알고리즘 3. Prim 알고리즘 1. 신장 트리(Spanning Tree) 신장 트리는 그래프 내 정점이 최소의 간선으로 모든 정점이 연결되어 있는 트리로, 사이클이 없는 그래프입니다. 신장 트리에 n 개의 정점이 있다면, 항상 n-1 개의 간선이 존재합니다. 최소 비용 신장 트리는 간선들의 비용 합이 최소가 되는 신장 트리를 뜻합니다. 대표적인 알고리듬으로는 Kruskal 알고리듬과 Prim 알고리듬이 있습니다. 2. Kruskal 알고리듬 전체 간선 중 비용이 낮은 간선을 우선적으로 선택해서 모든 정점을 사이클이 없도록 연결하는 방법으로, 간선의 수가 적을 때 적합합니다. 3. Prim 알고리듬 Kruskal과 달리, 시작 정점으로부.. 그래프 탐색 알고리듬 간략 정리 목차 1. 깊이 우선 탐색(DFS) 2. 너비 우선 탐색(BFS) 1. 깊이 우선 탐색(DFS: Depth First Search) DFS는 시작 정점에서부터 다음 분기까지 해당 분기를 완벽하게 탐색하는 그래프 탐색 기법입니다. 미로를 탐색할 때 한 방향으로 계속 가다가 막히면, 다시 가까운 갈림길로 돌아와 이어가는 것을 예로 들 수 있습니다. 1) 넓게 탐색하는 것이 아닌, 깊게 탐색한다. 3) BFS에 비해 구현이 간단하다. 3) 최단 경로를 보장하지 못한다. 4) BFS에 비해 속도가 느리다. 2. 너비 우선 탐색(BFS: Breadth First Search) BFS는 시작 정점을 방문하고 인접한 모든 정점을 방문하는 그래프 탐색 기법입니다. 1) 깊게 탐색하기보단, 넓게 탐색한다. 2) 시작 정.. 정렬 알고리듬 간략 정리 목차 1. 선택 정렬(selection sort) 2. 삽입 정렬(insertion sort) 3. 버블 정렬(bubble sort) 4. 합병 정렬(merge sort) 5. 셸 정렬(shell sort) 6. 퀵 정렬(quick sort) 7. 힙 정렬(heap sort) 8. 위상 정렬(topological sort) 1. 선택 정렬(selection sort) 자리를 하나 선택하고, 데이터 중 최솟값을 찾아서, 선택한 자리의 데이터와 교환을 반복해 정렬하는 알고리듬입니다. 1) 첫 번째 자리를 선택하고, 나머지 데이터 중 최솟값을 찾아서 자리를 교환 2) 두 번째 자리를 선택하고, 나머지 데이터 중 최솟값을 찾아서 자리를 교환 3) 위를 반복해 정렬을 완료 구현이 비교적 단순하지만, 시간 복잡도는.. 자료구조 간략 정리 목차 1. 스택(Stack) 2. 큐(Queue) 3. 힙(heap) 4. 트리(Tree) 5. 그래프(Graph) 1. 스택(Stack) 스택은 후입선출(LIFO), 즉 마지막에 삽입된 데이터가 가장 먼저 반환되는 자료 구조입니다. push 연산자로 데이터를 삽입하고, pop 연산자로 가장 나중에 삽입된 데이터를 반환합니다. 2. 큐(Queue) 큐는 선입선출(FIFO), 즉 먼저 삽입된 데이터가 가장 먼저 반환되는 자료구조입니다. enqueue 연산자로 Back에 데이터를 삽입하고, dequeue 연산자로 front의 가장 먼저 삽입된 데이터를 반환합니다. 3. 힙(Heap) 큐에 우선순위 개념을 적용한 자료구조입니다. 데이터들은 각자 우선순위를 가지고 있고, 우선순위가 높은 데이터가 먼저 반환됩니다.. 이전 1 다음
