허프만 압축 문제 메모리 공간을 효율적으로 사용할 수있고, 파일 전송 시간을 단축시키기 위해 주어진 파일의 크기를 줄이는 방법을 파일 압축(file compression)이라고 한다. 그렇다면 허프만(Huffman) 압축이란? 파일에 빈번히 나타는 문자에는 짧은 이진 코드를 할당, 드물게 나타나는 문자에는 긴 이진 코드를 할당한다. 허프만 압축을 사용한 문자 코드들은 접두부 특성(Prefix Property)이 존재한다. -> 접두부 특성 : 각 문자에 할당된 이진 코드는 다른 문자에 할당된 이진 코드의 접두부가 되지 않는다. 코드 사이를 구분할 특별한 코드가 필요 없다. ex) 문자 'a' -> 코드 '101' 이라면 다른 모든 문자의 코드는 '101'로 시작 안 함, 또한 '1','10'으로도 시작 ..
Algorithms
작업 스케줄링 문제 작업 스케줄링 문제는 작업의 수행 시간이 중복되지 않도록 모든 작업을 가장 적은 기계의 수에 배정하는 문제이다. 작업 스케줄링 문제에 주어진 문제 요소들은 작업의 수, 각 작업의 시작시간과 종료시간이다. 시작과 종료 시간이 정해져 있다는 것은 작업의 길이가 주어진 것이라고 봐도 무방하다. 그렇다면 이것들을 그리디 알고리즘으로 표현한다면 다음과 같이 표현할 수 있다. 빠른 시작시간 작업을 우선(Earliest start time first) 배정 빠른 종료시간 작업을 우선(Earliest finish time first) 배정 짧은 작업 우선(Shortest job first) 배정 긴 작업을 우선(Longest job first) 배정 하지만 첫 번째 알고리즘을 제외하고 나머지 세 가..
집합 커버 문제 집합 커버 문제는 집합 F에서 선택하는 집합들의 수를 최소화하는 문제이다. 예시로 신도시 학교 배치 문제가 있다 10개의 마을이 신도시에 만들어질 계획이다. 아래의 2가지 조건이 만족되도록 학교 위치를 선정해야 한다. •학교는 마을에 위치해야 한다. •등교 거리는 걸어서 15분 이내이어야 한다. 어느 마을에 학교를 신설해야 학교의 수가 최소가 되는가? 사진을 문제로 변환 시키면 U={1, 2, 3, 4, 5, 6, 7, 8, 9, 10} // 신도시의 마을 10개 F={S1, S2, S3, S4, S5, S6, S7, S8, S9, S10} // Si는 마을 i에 학교를 배치했을 때 커버되는 마을의 집합 S1={1, 2, 3, 8} S5={4, 5, 6, 7} S9 ={6, 9} S2={..
‘백트래킹(Backtracking) 기법’은 해를 찾는 도중에 ‘막히면’ 되돌아가서 다시 해를 찾아가는 기법이다. 백트래킹 기법은 최적화(optimization) 문제와 결정(decision) 문제를 해결할 수 있다. 결정 문제란 문제의 조건을 만족하는 해가 존재하는지의 여부를 yes or no로 답하는 문제이다. 예시로 미로 찾기, 해밀토니안 사이클, 서양 장기 여왕 말, 부분 집합의 합 문제 등이 있다. 이전 포스팅에서 근사 알고리즘으로 해결한, NP-완전 문제인 여행자 문제 (TSP)를 백 트래킹 기법으로 해결하는 과정을 살펴본다. TSP를 위한 백트래킹 알고리즘은 다음과 같다. 단, bestSolution은 현재까지 찾은 가장 우수한 해이며, (tour,tour의 거리)로 나타낸다. 이 때, to..
부분 배낭 문제 배낭(knapsack) 문제는 각 n개의 물건이 무게와 가치를 가지고 있을 때, 최대의 가치를 갖도록 한정된 용량의 배낭에 넣을 물건들을 정하는 문제이다. 그렇다면 부분 배낭 문제는 무엇이 다른 가? 배낭 문제에서는 물건을 통째로 넣어야 하는 것에 반해, 부분 배낭 문제는 물건을 부분적으로 담는 것이 허용된다. 최적해를 위해 단위 무게당 가장 값나가는 물건을 배낭에 넣고, 다음 값나가는 물건을 넣는 중에 통째로 넣는 것이 불가능 하다면 두 번쨰로 값나가는 물건을 배낭에 넣을 수 있는 만큼 부분적으로 담는 것이다. 알고리즘 FractionalKnapsack 입력: n개의 물건과 각 물건의 무게와 가치, 배낭의 용량 C 출력: 배낭에 담은 물건 리스트 L과 배낭에 담은 물건의 가치 합 v 각..
