![]()
문제가 영어라 내가 이해한? 영어대로 해석해보겠다. 문제 가방이 있고 물건이 있다. 가방에는 최대 2개의 물건을 담을 수있다. 가방의 용량을 넘어서는 물건을 담을 수 없다. 입력 첫 번째 입력은 물건의 개수 두 번째 입력은 가방의 용량 문제 해석 물건의 무게가 큰 순서대로 정렬함. 가방의 개수가 최소화되는 방법은 가장 큰 거를 우선 담고, 그 빈자리에 담을 수 있는 가장 작은 무게를 담는다. 만약 담았다면 담았던 물건은 제외시켜준다. 코드 #include #include #include using namespace std; int big(int i, int j) { return i > j; } int N, W, totweight = 0; vector profit; vectorinclude; int Cou..
![]()
●허프만 코드란? 데이터를 효율적으로 압축하기 위해서 만들어진 알고리즘. 탐욕법을 사용함. 데이터 파일은 통상적으로 이진 코드(binary code)로 표현한다. 각 문자는 코드 워드(code word)라고 하는 유일한 이진 문자열로 표현한다. ●fixed length binary code 각 문자를 표현하는 bit의 개수가 일정하다. 예를 들어 문자의 집합이 {a,b,c}라면 bit 2개만으로 문자를 코드화 할 수 있다. bit 2개로는 4개의 문자를 bit 3개로는 8개의 문자를 표현할 수 있다. a : 00 b:01 c:11 이라고 가정하자. 만약 File이 ababcbbbc라면 결과 코드는 000100011001010110일것이다. ->18비트를 사용한다. ●variable-length binar..
![]()
Knapsack Problem(배낭문제) 1)Fractional Knapsack Problem 보석의 무게를 쪼갤 수 있다는 가정을 둔다. 예를 들어 보석이 10kg라도 내가 들고가고싶은 만큼 담아서 가방에 넣을 수 있다. ->greedy를 이용해서 해결 2)0-1 Knapsack Problem 보석의 무게를 쪼 갤 수없다. 예를 들어 보석이 10kg라면 10kg 그대로 가방에 담아야 한다. ->dynamic programming을 이용해서 해결 배낭문제의 목표는 가방에 담는 보석들의 가치 합이 최대가 되야한다. ●Greedy Approach 탐욕법을 통한 전략은 다음과 같다. 단위 무게당 가치가 가장 큰 보석을 담는다. 가방에 최대 무게가 넘지않을때까지 보석을 담는다. 이러한 접근법은 보석을 쪼갤수있는..
![]()
Scheduling problem은 운영체제에서 다루는 개념이다. 최대한 적은 시간을 사용하면서 많은 작업을 해야 효율적이다 어떻게 하면 효율적으로 배치할 수 있을까? ●FCFS(First-come , First served) 들어온 순서대로 일을 시작한다. 도착 순서는 P1->P2->P3이라고 가정하자. FCFS의 방식은 p1이 먼저 도착했으니까 p1의 일을 다 끝내기 전까지 p2, p3는 일을 시작하지 못한다. P1, P2, P3의 모든 작업이 끝나는데 소요되는 시간은 30이지만, P1, P2, P3가 기다리는 시간은 24+27 = 51이다. p2, p3는 p1에 비해 굉장히 적은 시간을 사용하는 작업임에도 불구하고 p1이 끝날 때까지 기다려야 한다. 이러한 알고리즘은 굉장히 효율적이지 못하다. ●S..
