Data Structure & Algorithm/알고리즘29 [DP] Knapsack Problem (0-1 Knapsack) References Algorithms (Sanjoy Dasgupta) Contents Knapsack Problem (배낭 문제) with repetition without repetition Knapsack Problem 배낭 문제(knapsack problem)는 간단하게 다음과 같습니다. 한 여행가의 배낭에 담을 수 있는 무게의 최댓값(W)이 정해져 있습니다. 담을 수 있는 항목은 총 n개가 있는데, 이들의 무게는 \(w_1, \cdots, w_n\)이고, 그 항목의 가치는 \(v_1, \cdots, v_n\) 일 때, 가치의 합이 최대가 되도록 배낭에 담을 항목을 고르는 방법은 무엇일까요? 예를 들어, W = 10일 때를 생각해보도록 하겠습니다. 이 문제는 두 종류의 버전이 존재합니다. 만약 각.. 2022. 4. 14. 동적 프로그래밍 (Dynamic Programming) References Algorithms (Sanjoy Dasgupta) Contents DAG에서의 최단 경로 Longest Increasing Subsequence (LIS; 최장 증가 부분 수열) Edit Distance (편집 거리) DAG에서의 최단 경로 DAG(Directed Acyclic Graph), 즉, 유향 비순환 그래프에서의 최단 경로 알고리즘에는 다익스트라(Dijkstra) 알고리즘, 벨만-포드(Bellman-Ford) 알고리즘 등이 있습니다. 이 알고리즘을 통해서 최단 경로 문제는 쉽게 해결될 수 있다는 것을 알 수 있습니다. 이는 동적 프로그래밍의 핵심적인 부분이기 때문에, 동적 프로그래밍에 대해 시작하기 전에 한 번 요약해보도록 하겠습니다. 각 최단 경로 알고리즘에 대해서는 다른.. 2022. 4. 13. 최소 신장 트리 (Minimum Spanning Tree) References Algorithms (Sanjoy Dasgupta) Contents Minimum Spanning Tree 크루스칼 알고리즘 (Kruskal's algorithm) Union-Find 자료구조 C++ 구현 그리디(Greedy) 알고리즘들은 가장 명백하게 당장의 이득을 제공하는 다음 조각을 항상 선택하면서 한 조각씩 해결책을 만들어 나갑니다. 이와 같은 접근 방법이 계산을 요구하는 작업에 많은 피해를 줄 수 있을지라도, 최적이 되는 해결책을 얻을 수도 있습니다. 그리디 알고리즘의 예로 이번 포스팅에서는 최소 신장 트리(Minimum Spanning Tree; MST)에 대해 알아보고자 합니다. 최소 신장 트리 컴퓨터들을 쌍으로 연결함(linking)으로써 네트워크를 구성한다고 가정해봅시.. 2022. 4. 11. 피보나치 수열 Reference Algorithm (Sanjoy Dasgupta) 피보나치 수열 이번에 아주 간단한 피보나치 수열과 n번째 피보나치 수를 구하는 알고리즘에 대해서 알아보도록 하곘습니다. 피보나치 수열은 위 이미지에 나타난 수열이며, 수열 내에서 각 숫자는 이전 두 숫자의 합입니다. 정확하게 이야기하면, 피보나치수 \(F_n\)은 아래의 간단한 규칙(점화식)으로 생성됩니다. \[F_n = \left\{\begin{matrix} F_{n-1} + F_{n-2} && \text{if } n > 1 \\ 1 && \text{if } n = 1 \\ 0 && \text{if } n = 0 \end{matrix}\right.\] 피보나치 수열은 \(2^n\)과 거의 같은 속도로 증가합니다. 예를 들어, \(F_{.. 2021. 10. 26. 보이어-무어-호스풀 알고리즘(Boyer-Moore-Horspool Algorithm) References 리얼월드 알고리즘 KMP 알고리즘과 라빈-카프 알고리즘에 이어서 다른 문자열 알고리즘인 보이어-무어-호스풀(Boyer-Moore-Horspool) 알고리즘에 대해서 알아보겠습니다. 2020.11.25 - [Data Structure & Algorithm/알고리즘] - KMP 알고리즘 2020.12.17 - [Data Structure & Algorithm/알고리즘] - Rabin-karp(라빈 카프) 알고리즘 KMP 알고리즘이나 라빈-카프 알고리즘은 주어진 텍스트를 왼쪽에서 오른쪽으로 살펴봤습니다. 이와는 반대로 보이어-무어-호스풀 알고리즘은 오른쪽에서 왼쪽으로 텍스트를 스캔합니다. 아래는 'APESTLEINTHEKETTLE'이라는 텍스트에서 보이어-무어-호스풀 알고리즘을 사용하여 패.. 2021. 10. 12. [그래프] 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) References 리얼월드 알고리즘 Contents 플로이드-워셜 알고리즘 다익스트라 알고리즘과 벨만-포드 알고리즘에 이어서 또 다른 최단 경로 알고리즘인 플로이드-워셜 알고리즘에 대해서 알아보겠습니다. 2021.10.07 - [Data Structure & Algorithm/알고리즘] - [그래프] 다익스트라 알고리즘(Dijkstra's algorithm) [그래프] 다익스트라 알고리즘(Dijkstra's algorithm) References 리얼월드 알고리즘 Contents 다익스트라(데이크스트라) 알고리즘 구현 임의의 원소에 접근해 값 갱신(update)이 가능한 Heap(우선순위 큐) 구현 음의 가중치는 사용 불가 그래프의 지름 C++로 junstar92.tistory.com 2021.10.1.. 2021. 10. 11. [그래프] 벨만-포드 알고리즘(Bellman-Ford Algorithm) References 리얼월드 알고리즘 Contents 벨만-포드 알고리즘 큐 기반 벨만-포드 알고리즘 음의 가중치 순환 2021.10.07 - [Data Structure & Algorithm/알고리즘] - [그래프] 다익스트라 알고리즘(Dijkstra's algorithm) [그래프] 다익스트라 알고리즘(Dijkstra's algorithm) References 리얼월드 알고리즘 Contents 다익스트라(데이크스트라) 알고리즘 구현 임의의 원소에 접근해 값 갱신(update)이 가능한 Heap(우선순위 큐) 구현 음의 가중치는 사용 불가 그래프의 지름 C++로 junstar92.tistory.com 이전 게시글에서 다룬 최단 경로 알고리즘인 다익스트라 알고리즘에 이어서, 다른 최단 경로 알고리즘인 벨.. 2021. 10. 10. [그래프] 다익스트라 알고리즘(Dijkstra's algorithm) References 리얼월드 알고리즘 Contents 다익스트라(데이크스트라) 알고리즘 구현 임의의 원소에 접근해 값 갱신(update)이 가능한 Heap(우선순위 큐) 구현 음의 가중치는 사용 불가 그래프의 지름 C++로 구현한 전체 코드는 아래를 참조바랍니다 ! https://github.com/junstar92/DataStructure_Algorithm/tree/master/Algorithm/Dijkstra GitHub - junstar92/DataStructure_Algorithm Contribute to junstar92/DataStructure_Algorithm development by creating an account on GitHub. github.com 다익스트라(또는 데이크스트라) .. 2021. 10. 7. [그래프] 가중치 그래프와 임계 경로(Critical Path) References 리얼월드 알고리즘 Contents 가중치 그래프(weighted graph) 임계 경로(critical path) 가중치 그래프 Weighted Graph 이전 글들에서 그래프 자료구조와 위상 정렬에 대해서 살펴봤습니다. 2021.10.04 - [Data Structure & Algorithm/자료구조] - [자료구조] Directed Graph 2021.10.05 - [Data Structure & Algorithm/알고리즘] - [그래프] 위상 정렬 Topological Sort 이 글들에서 정점과 이들 사이를 연결하는 간선으로 표현하는 그래프를 사용했는데, 숫자로 된 가중치를 각 간선에 부옇여 그래프를 확장할 수 있습니다. 이러한 그래프를 가중치 그래프(weighted graph.. 2021. 10. 6. [그래프] 위상 정렬 Topological Sort References 리얼월드 알고리즘 https://blog.naver.com/kks227/220800013823 Contents Directed Acyclic Graph(DAG) 위상 정렬(Topological Sort) 아래 구현에서 사용되는 그래프 자료구조는 이전 게시글에서 구현한 DirectedGraph 코드를 사용하였습니다. 그래프 자료구조의 구현은 이전 게시글을 참조바랍니다 ! 2021.10.04 - [Data Structure & Algorithm/자료구조] - [자료구조] Directed Graph [자료구조] Directed Graph References Data Structrue : A Pseudocode Approach with C Contents Graph Directed Graph.. 2021. 10. 5. 이전 1 2 3 다음
