Huffman Coding Algorithm 허프만 암호화 알고리즘 Reference: Introduction to Algorithms 3E (CLRS) (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein 저, MIT Press, 2018) Reference: 쉽게 배우는 알고리즘 (문병로 저, 한빛아카데미, 2018)
Meeting Room Scheduling Problem 회의실 스케줄링 문제 - 하나의 회의실을 여러 팀이 사용하고자 할 때, 회의들이 서로 겹치지 않게 하면서 최대한 많은 회의를 수용할 수 있도록 스케줄링하는 문제이다. - 보통, 구현의 편의를 위해 한 팀의 회의 종료 시간과 다른 팀의 회의 시작 시간은 겹칠 수 있다고 가정한다. (즉, 11시에 회의가 끝나고 곧바로 11시에 다른 팀이 회의를 시작하는 것이 가능하다.) - \(n\)개의 회의가 요청된다 하고, 각각의 팀은 (회의 시작 시간, 회의 종료 시간) Pair를 넘겨준다. - Greedy 알고리즘에서는 요청된 회의 시간들을 회의 종료 시간을 기준으로 오름차순으로 정렬한 다음, 종료 시간이 빠른 회의에 회의실을 배정한다. (이때, 선택한 회의가..
Fractional Knapsack Problem 분할 가능한 배낭 채우기 문제 Reference: Introduction to Algorithms 3E (CLRS) (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein 저, MIT Press, 2018) Reference: 쉽게 배우는 알고리즘 (문병로 저, 한빛아카데미, 2018)
Zero/One Knapsack Problem 0/1 배낭 채우기 문제 Reference: Introduction to Algorithms 3E (CLRS) (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein 저, MIT Press, 2018) Reference: 쉽게 배우는 알고리즘 (문병로 저, 한빛아카데미, 2018)
Coin Exchange Problem 동전 교환 문제 Reference: Introduction to Algorithms 3E (CLRS) (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein 저, MIT Press, 2018) Reference: 쉽게 배우는 알고리즘 (문병로 저, 한빛아카데미, 2018)
Greedy Algorithms 그리디 알고리즘, 탐욕 알고리즘 - 지금 당장의 최선의 선택지만을 골라가며 해를 도출해나가는 방법을 채택한 알고리즘을 의미한다. (당장, 눈앞의 이익만을 좇는다.) - 그리디 알고리즘은 대체로 좋은 결과를 기대할 수 없지만, 특정 문제에서는 그리디 알고리즘이 최적해를 보장해주기도 한다. (예를 들어, 매트로이드와 같은 특수 구조에서는 그리디 알고리즘이 최적해를 보장한다.) - 그리디 알고리즘은 최적화 문제를 대상으로 적용할 수 있는데, 최적해를 찾을 수 있다면, 최적해를 찾는데 목표를 두고, 최적해를 주어진 시간에 찾아낼 수 없다면, 그런대로 괜찮은 해를 찾는데 목표를 둔다. * Constructive Algorithm (구축형 알고리즘) - 불완전한 상태에서 온전한 최적..
Strongly Connected Components 강연결 요소 - Directed Graph \(G = (V, E)\)에서 모든 \((u ,v) \in E\)에 대해, 경로 \(u \rightsquigarrow v\) 와 경로 \(v \rightsquigarrow u\) 가 동시에 존재하면, 그래프 \(G\)는 "Strongly Connected"("강하게 연결되어 있다")라 표현한다. - 즉, 어떤 두 정점을 잡더라도 양방향으로 서로에게 이르는 경로가 존재하면 "강하게 연결되어 있다"라 표현할 수 있다. - 그래프상에서 강하게 연결된 부분 그래프들을 각각 Strongly Connected Components(강연결 요소)라 부른다. * Graph (그래프) (URL) [Data Structures]..
Shortest Path in DAG 사이클이 없는 방향 그래프의 최단 경로 * DAG (Directed Acyclic Graph) - "사이클이 없는 방향 그래프"의 약자이다. - DAG에서는 모든 정점을 한 줄로 늘어놓으면, 뒤에 위치한 정점부터 앞에 위치한 정점으로 가는 간선은 존재하지 않도록 하는(=역방향으로 가지 못하는) 정점들의 순열이 존재한다. - DAG에서 이러한 순열은 위상 정렬을 통해 얻을 수 있다. - DAG의 경우, 간선들의 가중치의 부호를 모두 바꾸어 수행하면 최장 경로까지도 계산해낼 수 있다. (반면, 벨만-포드, 다익스트라 알고리즘에서는 최장 경로를 계산해낼 수 없다.) - DAG를 넘어서, 일반적인 그래프에서 최장 경로를 구하는 문제는 NP-Complete에 해당되는 문제이다..
