입금후 변신하는 헐리우드 코딩 스타

Basic Example - 행렬 경로 문제 : 정수들이 저장된 n×n 행렬의 좌상단에서 우하단까지 이동한다. 단 오른쪽이나 아래쪽 방향으로만 이동할 수 있다. 방문한 칸에 있는 정수들의 합이 최소화되도록 하라. Key Observation 세로 축 : i 가로 축 : j => (i,j) (i,j)에 도달하기 위해서는 (i,j-1) 혹은 (i-1,j)를 거쳐야 한다. 또한 (i,j-1) 혹은 (i-1,j)까지는 최선의 방법으로 이동해야 한다. 순환식 L[i, j] : (1,1)  에서  (i,j)까지 이르는 최소합 L[i, j]  =  mij                                                           if i = 1 and j = 1; L[i  1, j] + mij                                         if j = 1; L[i, j  1] + mij                                         if i = 1; min(L[i  1, j], L[i, j  1]) + mij                  otherwise. 경로 구하기 void printPathRecursive(int i, int j)      {            if (i==1 && j==1)                 print(1 + “ “ + 1);            else {                  if (P[i][j] == ‘←’)                      printPathRecursive(i, j-1);                 else                      printPathRecursive(i-1, j);                 print(i + “ “ + j);       } } 이렇게 recursive 하게 구하는 게 낫다. int mat() 같은 경우에도 for 문 두번 돌리면서 경로 구하는 형태임.

다이나믹 프로그래밍 = 동적계획법 피보나치 수열 : 많은 계산이 중복됨 -> recursion 으로 계산하니까 중복현상이 있음! Memoization int fib(int n) {       if (n==1 || n==2)            return 1;       else if (f[n] > -1) /* 배열 f가 -1으로 초기화되어 있다고 가정 */            return f[n]; /* 즉 이미 계산된 값이라는 의미 */       else {            f[n] = fib(n-2) + fib(n-1); /* 중간 계산 결과를 caching */            return f[n];       } } bottom-up 방식으로도 중복 계산을 피할 수 있다. 이항 계수(Binomial Coefficient) int binomial(int n, int k) {       if (n == k || k == 0)            return 1;       else            return binomial(n - 1, k) + binomial(n - 1, k - 1); } 역시 많은 계산이 중복되어 일반적으로  n     n-1             n-1    =           +                   과 같은 경우의 수를 볼 수 있다. k       k              k-1 Memoization int binomial(int n, int k) {        if (n == k || k == 0)            return 1;       else if (binom[n][k] > -1) /* 배열 binom이 -1로 초기화되어 있다고 가정 */            return binom[n][k];       else {            binom[n][k] = binomial(n-1, k) + binomial(n-1, k-1);            return binom

제 6단계 디코딩하기 class HuffmanDecoder public class HuffmanDecoder {       static public void main (String args[]) {            String fileName = "";            HuffmanCoding app = new HuffmanCoding();            RandomAccessFile fIn;            Scanner kb = new Scanner(System.in);            try {                 System.out.print("Enter a file name: ");                 fileName = kb.next();                 fIn = new RandomAccessFile(fileName,"r");                 app.decompressFile(fileName,fIn);                 fIn.close();            } catch (IOException io) {                 System.err.println("Cannot open " + fileName);            }       } } //실제 추가할 함수 decompressFile public void decompressFile(String inFileName, RandomAccessFile fIn)  throws IOException {       String outFileName = new String(inFileName+".dec");       RandomAccessFile fOut = new       RandomAccessFile(outFileName,"rw");       inputFrequencies(fIn);       crea

제5단계 인코딩하기 압축파일의 맨 앞부분(header)에 파일(원본)을 구성하는 run들에 대한 정보를 기록한다. 이 때 원본 파일의 길이도 함께 기록한다. (왜 필요할까?) : 각각의 run 들에게 어떤 codeword를 부여했는지 알아야 복원 가능하기 때문에 codeword에 대한 정보를 기록한다. 아니면 frequency에 대한 정보를 저장한다. outputFrequencies private void outputFrequencies(RandomAccessFile fIn,  RandomAccessFile fOut) throws IOException {     //fIn : 압축할 파일     //fOut : 압축된 파일            fOut.writeInt(runs.size());     // 먼저 run의 개수를 하나의 정수로 출력한다.       fOut.writeLong(fIn.getFilePointer());     // 원본 파일의 크기(byte 단위)를 출력한다.           for (int j = 0; j < runs.size(); j++) {     //             Run r = runs.get(j);            fOut.write(r.symbol); // write a byte            fOut.writeInt(r.runLen);            fOut.writeInt(r.freq);      } } compressFile public void compressFile(String inFileName, RandomAccessFile fIn) //fin은 압축할 파일, inFileName은 그 파일 이름이다. (압축 파일명 정하기 가능)  throws IOException {      String outFileName = new String(inFileName+”.z");     // 압축 파일의 이름은 압축할 파일의 이름에 확장자를 . z를 붙인 것이다.      RandomAcc

제 4단계 Codeword 검색하기 인코딩 - 데이터 파일을 압축하기 위해서는 [데이터 파일을 다시 시작부터 읽으면서 run들을 하나씩 인식한 후 ] 해당 run에 부여된 codeword를 검색하다. - 허프만 트리에서는 모든 run들이 리프노드에 위치하므로 검색하기 불편하다. - 따라서 검색하기 편리한 구조를 만들어야 한다. = 런들이 트리 구조로 되어 있어서 AAA라는 run이 어디에 있는지, 어떤 애가 AAA인지 찾는게 상당히 번거롭게 되어 있음. (규칙성이 없어서 불편함) 이제 4단계에서는 tree 구조 필요가 없어서 다른 자료구조 형태로 변경한다. 예전 가이드 : 해시맵 구조로 변경 현재 가이드 : 연결리스트로 변경 (hashing 비슷한 것) symbol                    : A  codeword               :  0 freg                         : 1 runLen                    : 1 codewordLen          : 2  right                       :  이런 식으로 되어 있으면 runLen이 1이고 symbol이 A 이므로 A이다. symbol                : A  codeword            :  2 freg                    : 2 runLen                : 2 codewordLen        : 2  right                   :  이런 식으로 되어 있으면 runLen이 2이고 symbol이 A이므로 AA이다. 이렇게 symbol이 동일한 run 들을 하나의 연결리스트로 저장한다. 각 run의 right 필드는 다음 노드를 가리키는 링크 필드로 사용한다. 한 run에 대해 마지막 노드는 right 값이 null이 된다. 이렇게 동일한 심볼의 run들을 연결 리스트로 만들어서 저장한다. 크기가 256인 chars 라는 연결 리스트 배열을 만들어서 사용한다. 아스키 코드로

제 3단계 Codeword 부여하기 각각의 런들에게 실제로 코드워드 부여하는 법 : Huffman 트리의 리프 노드에 위치한 run 들에게 이진 codeword 를 부여할 차례이다. -리마인드- Prefix Code : 어떤 codeword(101, 010 같은 것) 도 다른 codeword의 prefix(접두사)가 되지 않는 코드 (codeword란 하나의 문자에 부여된 이진코드를 말함) -리마인드 끝- assignCodeword(prefix, node) 만약에 node가 leaf 이면     prefix 를 node 에 할당한다. (부여한다) 아니면     assignCodeword(prefix + '0' , node.left);     assignCodeword(prefix + '1', node.right); 루트  루트 자식 왼쪽 - 0 | 루트 자식 오른쪽 - 1 루트 자식 왼쪽의 왼쪽 - 00 | 루트 자식 왼쪽의 오른쪽 - 01  ㄴ 이런 식으로 자식 위치에 따라서 나의 codeword 에 0  이나 1을 추가한다. 루트 자식 오른쪽의 왼쪽 - 10 | 루트 자식 오른쪽의 오른쪽 - 11  루트 자식 오른쪽의 오른쪽의 왼쪽 - 110 | 루트 자식 오른쪽의 오른쪽 - 111 ㄴ 이런 식으로 추가하라는 수도 코드임 여기서 prefix를 하나의 32비트 정수로 표현한다 (8비트) 하지만 32비트 중에서 하위 몇 비트만이 실제 부여된 codeword이다. 따라서 codeword의 길이를 따로 유지해야 한다. class Run implements Comparable<Run>{     public byte symbol;     public int runLen;     public int freq;     //트리의 노드로 사용하기 위해서 왼쪽 자식과 오른쪽 자식 노드 필드를 추가한다.     //노드에 부여된 코드워드를 저장하기 위한 필드를 아래와 같이 추가한다.     public int codeword; //부여된

제 2단계 Huffman Tree Huffman coding 알고리즘은 [트리들의 집합]을 유지하면서 매 단계에서 가장 프리퀀시가 작은 두 트리를 찾아서 두 트리를 하나로 합친다. 이런 연산에 가장 적합한 자료구조는 최소 힙이다. (우선순위큐!) 즉 힙에 저장된 각각의 원소들은 하나의 트리이다. (노드가 아니라) ㄴ 런 객체들이 모여서 만들어지는 트리이다. ㄴ extractMin (힙 안의 최소값을 꺼내 주는 것)  ㄴ insert (넣기) 이 기능을 지원하도록 만들 것 최소 힙 - 크기가 5인 힙 - 5개의 트리가 저장되어 있다 - 각 트리는 오직 하나의 노드로 구성되어 있다.  heap 0 : A3 1(프리퀀시 값) 1 : C2 1 2 : A1 1 3 : B1 2 4 : A2 2 이렇게 각각의 런을 싱글 노드 트리라고 보면 되고, 각 트리가 노드 하나짜리 트리이다. min heap은 컴플릿 바이너리 트리 + 힙 프로퍼티를 만족해야 함 부모는 자식보다 작거나 같다 - frequency 값으로 보는 것 A3 1 - C2 1 / A1 1 C2 1 - B1 2 / A2 2  트리 모양은 이런 구조로 되어 있음 힙을 이진 트리 모양으로 만들기는 하는데, 프로그램 상에서는 그냥 1차원 배열 힙으로 만들면 되는 거라서   heap 0 : A3 1(프리퀀시 값) 1 : C2 1 2 : A1 1 3 : B1 2 4 : A2 2 이런 식으로 삽입 하면 된다. 일단 최소 힙 만들기 위해 힙을 만들어서 extreactMin을 두번 반복하고 insert를 하면  공백 7 (루트 - the Root 라고 부름) 공백 4  - 차일드 2      A2 2     B1 2 공백 3  - 차일드 2      C2 1     공백 2 - 차일드 2          A3 1          A1 1 이런 허프만 트리를 조성할 수 있다. class Run implements Comparable<Run>{     public byte symbol;     public int runL

Huffman Method with Run-Length Encoding 무손실 압축 알고리즘을 하이브리드로 이용해서 구현을 해 본다고 한다.   - 파일을 구성하는 각각의 run 들을 하나의 super-symbol로 본다. 이 super-symbol에 대해서 허프만 코딩을 적용한다. 예를 들어 AABAACCAABA는 AAA B AA CC AA 로 구성되며 등장 회수는 1 1 1 2 2 와 같다. A3 - 1 C2 - 1 A1 - 1 B1 - 2 A2 - 2 이 파일에 등장하는 run 들에게 이진 코드를 부여해서 동작시킨다. A3 - 110 C2 - 10 A1 - 00 B1 - 01 A2 - 111 로 run에 대해서 이진 코드를 부여하면 AAABAACCAABA는 110 01 10 111 10 01 00 으로 인코딩 된다 1100110111100100 <- 이거 이진 트리로 변경 하면 접두사가 겹치지 않는 트리를 제작 가능 * Run과 frequncy 찾기 - 압축할 파일을 처음부터 끝까지 읽어서 파일을 구성하는 run 들과 각 run 들의 등장횟수를 구한다. - 먼저 각 run들을 표현할 하나의 클래스 class run을 정의한다. 클래스 런은 적어도 세개의 데이터 멤버 symbol, runLen, freq를 가져야 한다. symbol만 byte고 다른 것은 다 정수이다. - 인식한 run 들은 하나의 ArrayList에 저장한다. - 적절한 생성자와 equals 메소드를 구현한다. symbol : run이 가지고 있는 단자? (AAA 면 A가 symbol이다) runlen : 길이 freq : 빈도 class Run{     byte symbol;     int runlen;     int freq; } 요러면 데이터 파일을 적어도 두번은 읽어야 한다. 1) run 찾기 2) 실제 압축 수행 RandomAccessFile을 이용해서 데이터 파일을 읽어본다고 한다. [RandomAccessFile]  원래 스트림은 원칙적으로 순서대로 처리되지만  예외적으

Case Study : Huffman Coding Huffman Coding : 대표적인 데이터 압축 알고리즘의 하나  - 무손실 Lossless : 데이터 손실이 있으면 안 되는 경우에 사용한다. - 손실 Lossy : 압축률 측에서 효율적이다. 가령 6개의 문자 a,b,c,d,e,f로 이루어진 파일이 있을 때, 문자의 총 개수는 100,000개이고 각 문자의 등장 횟수가 아래와 같을 때 a : 45 b : 13 c : 12 d : 16 e : 9 f : 5 -> 각 문자를 3 비트로 만듬 a : 000 b : 110 c : 010 d : 011 e : 100 f : 101 (45 + 13 + 12 + 16 + 9 + 5) * 3비트 = 300000비트 고정길이 코드를 사용하면 각가의 문자를 표현하기 위해서 3비트가 필요하며, 따라서 파일의 길이는 300,000 비트가 된다. -> 가변길이 코드를 사용하면 a : 0 1비트 * 45 = 45000비트 b : 101 3비트 * 13 = 39000비트 c : 100 3비트 * 12 = 36000비트 d : 111 3비트 * 16 = 48000비트 e : 1101 4비트 * 9 = 36000비트 f : 1100 4비트 * 5 = 20000비트 위 테이블의 가변길이 코드를 사용하면 224,000비트가 된다. : 압축 효과가 좋아졌다. 근데 이거를 1비트 2비트만 사용하면 파일 크기는 줄어든다고 생각 할 수 있겠으나 인코딩을 하는 것이 나중에 다시 디코딩이 가능해야 하는데 문제가 있을 수 있다. 이런 규칙 : Prefix Code Prefix Code : 어떤 codeword(101, 010 같은 것) 도 다른 codeword의 prefix(접두사)가 되지 않는 코드 (codeword란 하나의 문자에 부여된 이진코드를 말함) -> 어떤 코드도 다른 코드의 접두사가 될 수 없는 것이다.  0일 경우 어떤 코드도 0 으로 시작 불가 101 일 경우 어떤 코드도 101로 시작 불가 그래서 1101일 경우에는

Floyd-warshell Algorithm : 동적계획법의 일종  (수학과 컴퓨터 과학, 그리고 경제학에서 동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.) - 가중치 방향 그래프 G=(V,E), V = {1,2,... n} - 모든 노드 쌍들간의 최단경로의 길이를 구함 - d^k[i,j[ : 중간에 노드집합 {1,2...k}에 속한 노드들만 거쳐서 노드 i에서 j까지 가는 최단경로의 길이  ㄴ 노드 i에서 j까지 가는 최단경로는 두 가지 경우가 있다 (노드 k를 지나는 경우 , 지나지 않는 경우) i에서 j까지 경로가 k를 안 지나면 중간정점들이 모두 {1,2,...k}에 속한다. i에서 j까지의 경로가 k를 지나면 중간정점들이 모두 {1,2,... k-1}과 {1,2...k-1}에 속한다.  이 알고리즘은 처음에 모든  {\displaystyle (i,j)} 쌍에 대해서  {\displaystyle k=1} 일 때  {\displaystyle \mathrm {shortestPath} (i,j,k)} 를 계산하고, 다음으로  {\displaystyle k=2} 일 때를 계산하는 식으로  {\displaystyle k=N} 이 될 때까지 계속하면, 모든  {\displaystyle (i,j)} 쌍에 대해서 최단 경로를 찾게 된다. 기본적인 알고리즘의 의사코드는 다음과 같다: 1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity) 2 for each edge ( u , v ) 3 dist[ u ][ v ] ← w( u , v ) // 변 ( u , v )의 가중치 4 for each vertex v 5 dist[ v ][ v ] ← 0 6 f

Bellman-Ford 알고리즘 : 이어서 수업  * 릴랙스 하는 순서에 따라서 결과가 달라질 수 있음 : 따라서 진행 되는 결과가 변경 될 수 있긴 함 * 얘는 시간 복잡도 측면에서는 좋은 알고리즘이 아님 Dijkstra의 알고리즘 : 네트워크에서 하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘이다. 최단 경로는 경로의 길이순으로 정해진다.  Dijkstra의 알고리즘에서는 시작 정점에서 집합 S에 있는 정점만을 거쳐서 다른 정점으로 가는 최단 거리를 기록하는 배열이 반드시 있어야 한다. * 한 번 노드를 선택한 게 있으면 두번 선택 불가 (최단 경로는 중복 불가) -음수 가중치가 없다고 가정 - s로부터의 최단경로의 길이를 이미 알아낸 노드들의 집합 S를 유지. 맨 처음엔 S={s}. - Loop invariant :  u !∈ S 인 각 노드 u에 대해서 d(u)는 이미 S에 속한 노드들만 거쳐서 s로부터 u 까지 가는 최단경로의 길이 - 정리 : d(u) min v!∈S d(v)인 노드 u에 대해서, d(u)는 s에서 u까지의 최단경로의 길이이다. - 증명은 다른 경로가 존재할 경우에 d(v) >_ d(u) 이므로 모순이라 한다  (s에서 u까지 다른 최단경로가 존재한다고 했을 때) d(u)가 최소인 노드 u!∈S를 찾고, S에 u를 추가 S가 변경되었으므로 다른 노드들의 d(v) 값을 갱신 즉, 에지 (u,v)에 대해서 relaxation 하면 루프 불변이 유지됨 요...요약하면 프림이랑 다익스트라는 루프문 내 조금 다른 거 빼고는 똑같다고 볼 수 있어서 사실 Prim 의 알고리즘이랑 동일하다고 보면 된다고 한다 (-.-);;; 어려워서 나무위키 도움을 받음 다익스트라 알고리즘은 다음과 같다. (P[A][B]는 A와 B 사이의 거리라고 가정한다) 1. 출발점으로부터의 최단거리를 저장할 배열 d[v]를 만들고, 출발 노드에는 0을, 출발점을 제외한 다른 노드들에는 매우 큰 값 INF를 채워 넣는다. (정말 무한이 아닌, 무

최단경로 - 가중치 (방향) 그래프 G = (V,E), 즉 모든 에지에 가중치가 있음. - 경로 p = (v0, v1, ... vk)의 길이는 경로상의 모든 에지의 가중치의 합 - 노드 u에서 v까지의 최단경로의 길이를 δ(u, v)라고 표시하자.   최단경로문제의 유형 - Single-source  : 하나의 출발 노드 s로부터 다른 모든 노드까지의 최단 경로를 찾아라. - Single-destination : 모든 노드로부터 하나의 목적지 노드까지의 최단 경로를 찾아라. * single-source와 singled-destination은 사실상 같은 것으로 볼 수 있다. - Single-pair : 주어진 하나의 출발 노드 s로부터 하나의 목적지 노드 t까지의 최단 경로를 찾아라. * 최악의 경우 시간 복잡도에서 Single-Source 문제보다 나은 알고리즘이 없을 수 있다. - All-pairs : 모든 노드 쌍에 대해서 최단 경로를 찾아라. 최단 경로와 음수 가중치 - 음수 가중치  : 가중치가 음수인 경우 - 음수 사이클이 있으면 최단 경로가 정의되지 않는다. * 알고리즘에 따라 음수 가중치가 있어도 작동하는 경우도 있고, 그렇지 않은 경우도 있다. 최단 경로의 기본 특성 - 최단 경로의 어떤 부분경로도 역시 그 부분에 대한 최단 경로이다 * 전체 u~v에서, u에서 v까지의 최단 경로를 지정했을 떄, 중간 위치의 x~y 가 있다면 이 경로는 x에서 y까지의 최단경로이다. - 최단 경로는 사이클을 포함하지 않는다. ( 음수 사이클이 없다는 가정 ) Single-source (one to all) 최단경로문제 - 입력 : 음수 사이클이 없는 가중치 방향그래프 G=(V,E)와 출발 노드 s ∈ V - 목적 : 각 노드 v ∈ V에 대해서 다음을 계산한다. - d[v]     - 처음에는 d[s]=0, d[v]=∞ 로 시작한다.     - 알고리즘이 진행됨에 따라서 감소해간다. 하지만 항상 d[v] ≥ δ(s,v)를 유지한다.     - 최종적으로는  d

String to hex String appendValue = ""; StringBuffer sbuf = new StringBuffer();         for(int i=0; i<변경할String.length(); i++){         sbuf.append( "0x" + Integer.toHexString(변경할String.charAt(i)) );         }         appendValue = sbuf.toString();              System.out.println("Original Page default " + 변경할String); System.out.println("Original Page convert " + appendValue); hex to String String convertValue = ""; Pattern p = Pattern.compile("(0x([a-fA-F0-9]{2}([a-fA-F0-9]{2})?))");     Matcher m = p.matcher(변경된String);     StringBuffer sb = new StringBuffer();     int hashCode = 0;     while( m.find() ) {         hashCode = Integer.decode("0x" + m.group(2));         m.appendReplacement(sb, new String(Character.toChars(hashCode)));     }     m.appendTail(sb);     convertValue = sb.toString(); System.out.println("GPKIError Page convert : " + convertValue); 구글링 해서 찾은 것 중에 이거만 오류