Matroid Theory 매트로이드 이론 - Greedy Algorithm(그리디 알고리즘)이 Optimal Solution(최적해)을 가려낼 수 있는 경우인지를 판별할 수 있게 하는 수학적 공간이다. * Greedy Algorithms (그리디 알고리즘, 탐욕 알고리즘) (URL) [Algorithms] Greedy Algorithms | 그리디 알고리즘, 탐욕 알고리즘 Greedy Algorithms 그리디 알고리즘, 탐욕 알고리즘 - 지금 당장의 최선의 선택지만을 골라가며 해를 도출해나가는 방법을 채택한 알고리즘을 의미한다. (당장, 눈앞의 이익만을 좇는다.) - 그리디 dad-rock.tistory.com - 단, Greedy한 방법을 적용할 수 있는 모든 경우를 판별해낼 수 있는 것은 아니라서..
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)∈E에 대해, 경로 u⇝v 와 경로 v⇝u 가 동시에 존재하면, 그래프 G는 "Strongly Connected"("강하게 연결되어 있다")라 표현한다. - 즉, 어떤 두 정점을 잡더라도 양방향으로 서로에게 이르는 경로가 존재하면 "강하게 연결되어 있다"라 표현할 수 있다. - 그래프상에서 강하게 연결된 부분 그래프들을 각각 Strongly Connected Components(강연결 요소)라 부른다. * Graph (그래프) (URL) [Data Structures]..
