NP-Completeness Theory NP-완비성(완전성) 이론 - NP-완비성 이론에서는 어떤 문제가 NP-완비군에 속하는지에 대한 여부를 결정하는 여러 가지 기법들이 연구된다. - NP-완비군이란, 풀이 자체는 가능하지만, 현실적인 시간내에 해결할 수 없다 "강력히 추정"되는 문제들이 속한 그룹을 의미한다. (이 추정에 대한 증명은 100만달러 포상금이 걸린, 밀레니엄 문제로 출제되어 있고 아직까지 해결되지 않았다.) ※ 현재까지 NP-완비군에 속하는 문제들은 모두 Polynomial Time내에 풀 수 있는 방법이 고안되지 않았다. - 그러나, 만약 NP-완비군에 속하는 하나의 문제라도 Polynomial Time내에 풀 수 있는 방법이 개발되면, 수 많은 NP-완비군에 속하는 모든 문제들이 P..
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 (구축형 알고리즘) - 불완전한 상태에서 온전한 최적..
