격자상의 경로 문제 n x n 격자가 있을 때 왼쪽 위 지점에서 오른쪽 아래 지점으로 가는 경로를 구하는 문제입니다. 이때 조건은 움직이는 방향은 오른쪽과 아래만 가능합니다. 결과는 경로가 지나가는 지점의 값을 모두 더한 값이 가장 커야 합니다. 격자상의 경로 예시 예를 들어 5 x 5 격자에서 최적 경로는 다음과 같습니다. 결과는 67입니다. 이 값이 왼쪽 위에서 오른쪽 아래로 가는 경로 중 가능한 최대의 값입니다. 격자상의 경로 접근 격자의 행과 열의 번호가 0~n-1이고 value[y][x]가 (y,x) 지점의 값이라고 가정 왼쪽 위 지점에서 (y,x) 지점까지의 경로의 최대값을 sum(y,x)로 나타내기로 함 점화식 sum(y,x) = max(sum(y, x-1), sum(y-1, x)) + va..

1. 최장 증가 부분 수열 문제 정의 원소가 n개인 배열의 일부 원소를 골라내어 만든 부분 수열 중에서, 각 원소가 이전 원소보다 크다는 조건을 만족하면서 그 길이가 최대인 것을 최장 증가 부분 수열(longest increasing subsequence)이라 합니다. 문제 예시 다음과 같은 정수형 배열이 있다고 가정합니다. [6, 2, 5, 1, 7, 4, 8, 3] length(k)를 위치 k에서 끝나는 최장 증가 부분 수열의 길이라고 가정합니다. 그러면 0 5 -> 7) length(5) = 2 (1 -> 4) length(6) = 4 (2 -> 5 -> 7 -> 8) length(7) = 2 (1 -> 3) 위 결과에서 최장 증가 부분 수열을 가진 결과는 6번째로써 [2, 5, 7, 8]임을 알 ..

동전 교환 문제 여러 동전의 값 coins = {c1, c2, ... , ck}과 만들어야 하는 목표 액수 n이 주어질때 가장 적은 수의 동전을 사용하여 합이 n이 되도록 하는 문제 예를 들어 coins = {1, 2 , 5}이고 n=12라면 최적해는 동전을 3개 사용하여 5 + 5 + 2 = 12입니다. 1. 탐욕법이 실패하는 경우 탐욕 알고리즘을 사용하여 문제를 해결하기 위해서 항상 액수가 제일 큰 동전을 택하되, 합이 목표 액수를 넘지 않도록 함 예를 들어 coins = {1, 2, 5}이고 n=12라면 제일 큰 5원짜리 동전 2개를 선택하고 2원짜리 동전 1개를 선택하면 답이 된다. coins = {1, 3, 4}, n=6 탐욕 알고리즘 : 4 + 1 + 1 = 6, 동전 3개 반례 : 3 + 3..

1. 압축 해제 수행과정 압축 파일의 헤더에서 Run 객체들의 개수, 원본 파일의 크기, Run 객체들의 정보를 추출하여 저장(runs) (inputFrequencies 메서드) runs 리스트를 기반으로 허프만 트리 생성 (createHuffmanTree 메서드) 허프만 트리를 기반으로 Run 객체들의 codeword 할당 (assignCodeword 메서드) 압축 파일을 읽어서 디코딩을 수행 (decode 메서드) 위 수행과정에서 허프만 트리 생성과 codeword 할당은 인코딩 과정에서의 메서드와 동일합니다. 2. inputFrequencies 메서드 압축 파일의 맨 앞부분(헤더)을 읽어서 Run 객체들의 개수, 원본 파일의 크기, Run 객체들의 정보들을 읽어서 runs 리스트에 저장하는 메서드입..

1. 압축 수행과정 압축파일 맨 앞부분(헤더)에 파일을 구성하는 run들에 대한 정보를 기록 (outputFrequencies 메서드) run 객체의 개수 원본 파일의 크기, byte단위이고 8byte로 저장됨 각각의 Run 객체에 대한 문자(symbol), 길이(runLen), 빈도수(freq)를 저장함 symbol : 1byte 단위로 저장 runLen : 4byte 단위로 저장 freq : 4byte 단위로 저장 원본 파일의 문자들을 codeword로 변환하여 0또는 1의 형태로 저장 (encode 메서드) 예를 들어 원본파일의 내용이 "AAABAACCAABA"인 경우 인코딩 수행과정은 다음과 같습니다. 위 수행과정에서 압축파일(fOut)에 작성하는 부분은 outputFrequencies 메서드와 ..

Huffman Coding의 단계 문자열을 읽어서 Run 객체 생성 및 저장 (collectRuns 메서드) Run 타입의 리스트를 활용한 Huffman Tree 생성 (createHuffmanTree 메서드) Huffman Tree 리프노드에 codeword 할당 (assignCodewords 메서드) Huffman Tree 리프노드들을 체이닝 구조의 배열에 저장 (storeRunsIntoArray, 현재 구현해야하는 단계) 파일 압축 (encode 메서드) 1. Huffman Tree의 리프노드들을 체이닝 구조의 배열에 저장 필요성 데이터 파일을 압축하기 위해서는 데이터 파일을 다시 시작부터 읽으면서 run을 하나씩 인식한 후 해당 run에 부여된 codeword를 검색해야 합니다. Huffman T..