yevdev◡̈

앞서, 그리디 알고리즘을 통해 해결했던 배낭문제를 동적계획 알고리즘을 이용해서 해결해보자! 💡배낭문제의 부분문제를 찾아내기 4가지 요소 : 물건, 물건의 무게, 물건의 가치, 배낭의 용량 이중에서 물건과 물건의 무게는 부분문제를 정의하는데 고려 이유 : 배낭이 비어있는 상태에서 시작하여 물건을 하나씩 배낭에 담는 것과 안 담는 것을 현재 배낭에 들어있는 물건의 가치의 합에 근거하여 결정해야하기 때문 또한 물건을 배낭에 담으려고 할 경우, 배낭 용량의 초과 여부를 검사해야한다. 따라서, 부분문제를 아래와 같이 정의! K[i,w] = 물건 1~i 까지 (임시) 배낭의 용량이 w일 때의 최대 가치 i= 1~n, w= 1~C n : 물건의 개수, C: 배낭의 용량 여기서 C의 값이 매우 크면, 알고리즘의 수행시..

💡허프만 압축 아이디어 파일에 빈번히 나타나는 문자 -> 짧은 이진코드 할당 드물게 나타나는 문자 -> 긴 이진코드 할당 💡접두부 특성 (prefixx property) 허프만 압축방법으로 변환시킨 문자 코드들 사이에 존재 각문자에 할당된 이진 코드는 어떤 다른 문자에 할당된 이진코드의 접두부가 되지 않는다를 의미 접두부 특성의 장점은 코드와 코드 사이를 구분할 특별한 코드가 필요 없다는 것! 💡그래서, 허프만 압축은 뭘까? 입력파일에 대해 각문자의 출현 빈도수에 기반을 둔 이진트리를 만들어서, 각 문자에 이진코드를 할당 이러한 이진코드를 허프만 코드라고 한다. 💡의사코드 입력 : 입력 파일의 n개의 문자에 대한 각각의 빈도 수 출력 : 허프만 트리 1. 각 문자당 노드를 만들고, 그 문자의 빈도수를 노..

💡작업스케줄링 수행해야할 다수의 Job을 주어진 목적에따라 어떻게 수행할지를 결정하는 문제 주어진 목적에따라 작업스케줄링을 다양하게 정의할 수 있다. 이러한 문제들은 대부분 NP-hard문제이나, 일부 목적에 대해서 또는 문제를 단순화 시킬 경우 polynomial time에 해결할 수 있다. 💡작업스케줄링 문제 작업의 수행시간이 중복되지 않도록 모든 작업을 가장 적은 수의 기계에 배정하는 문제이다. n개의 각작업은 시작시간과 종료시간이 있다. 주어진 문제요소 작업의 수 각 작업의 시작과 종료시간 : 이는 정해져 있으므로 작업의 길이도 주어진 것이 된다. 시각시간, 종료시간, 작업의 길이에 대해 그리디 알고리즘을 생각해 볼 수 있는데 빠른 시작시간 작업 우선 배정 빠른 종료시간 작업 우선 배정 짧은 작업..

💡집합커버문제 (Set Covering Problem) n개의 원소를 가진 집합 U U의 부분집합들을 원소로하는 집합 F F의 원소들인 집합들 중에서 어떤 집합들을 선택하여 합집합하면 U와 같게 되는가? 여기서, F에서 선택하는 집합들의 수를 최소화하는 문제이다. ❓최적해를 어떻게 찾아야할까? 가장 단순한 방법 : F에 있는 집합들의 모든 조합을 1개씩 합집합하여 U가 되는지 확인하고, U가 되는 조합의 집합 수가 최소인 것을 찾는 것 Brute Force Algorithm : n개의 원소가 있으면 (2^n -1)개를 다 검사 필요 n이 커지면 최적해를 찾는 것은 실질적으로 불가능 실제로 집합커버문제는 NP-hard 문제로 polynomial time optimal algorithm을 설계하기 매우 어렵..

💡배낭 문제 n개의 물건이 있고, 각 물건은 무게와 가치를 가지고 있으며, 배낭이 한정된 무게의 물건들을 담을 수 있을 때, 최대의 가치를 갖도록 배낭에 넣을 물건들을 정하는 문제 💡부분 배낭 문제 물건을 부분적으로 (쪼개서) 담는 것을 허용 최적해를 위해서 '욕심내어' 단위 무게 당 가장 값나가는 물건을 배낭에 넣고, 계속해서 그 다음으로 값나가는 물건을 넣는다. 만약, 그 다음으로 값나가는 물건을 '통째로' 배낭에 넣을 수 없게되면, 배낭에 넣을 수 있을 만큼만 물건을 부분적으로 배낭에 담는다. 💡의사코드 입력 : n개의 물건 및 각 물건의 무게, 가치, 배낭의 용량 C 출력 : 배낭에 담은 물건 리스트 L, 배낭에 담은 물건의 가치 합 v 1. 각 물건에 대해 단위 무게당 가치를 계산 2. 물건들을..

💡 그리디(Greedy) 알고리즘? 최적화 문제를 해결하기 위한 방법이다. (입력) 데이터 간의 관계를 고려하지 않고 수행과정에서 현 상황에서 가장 좋은 (locally optimal)을 욕심내어 최소 또는 최대 것을 가진 데이터를 선택하여 문제를 해결 전체적으로 최적인지는 판단X, 오로지 현재 최적! 근시안적인 선택으로 부분적인 최적해를 찾고, 이들을 모아서 문제의 최적해를 얻는다. 한번 선택하면 절대 번복 X 어떤 알고리즘이 항상 global solution을 얻는다는 것을 주장하기 위해서는 논리적인 증명이 필요 증명할 수 없다면, 알고리즘의 해는 suboptimal일 수도 있으며, 이경우 이것을 휴리스틱 알고리즘이라고 부른다 그리디 알고리즘으로 해결할 수 있는 문제는? 아래의 두가지 조건이 만족되어..