728x90 Algorithm/알고리즘 기본27 [Algorithm] Dynamic Programming 1 Dynamic Programming 기존에 계산된 값을 버리지 않고 가지고 있다가 필요할때 다시 사용한다 중복계산을 줄일때 사용한다. Memoization(Top-Down) 큰문제를 먼저 시도한뒤 안풀린 문제면 다시 작은 문제를 푼다. 재귀로 구현한다. 가독성이 증가한다 어렵다. 실재로 팔요한 문제 들만 푼다. Dynamic Programmig(Bottom-Up) 작은문제를 먼저 풀어 나가는 방식이다. 반복문으로 구현한다. 가독성이 떨어진다. 비교적 쉽다. 모든 작은 문제들을 전부 구해야 한다. Memoization 과 Dynamic Programmig 차이점? 사실 둘다 비슷하다 중간 결과를 저장해 다시 사용한다면 Memoization 하위문제를 풀어나가면서 큰 문제를 해결하면 DP 대표예제 Fibon.. 2021. 10. 20. [Algorithm] Huffman Coding 3: Decoding 예제 설명 과 구현 Huffman 개념 https://vprog1215.tistory.com/232 [Algorithm] Huffman Coding 1: 개념 Huffman Coding 무손실 압축 알고리즘이다. Huffman Coding 예시 파일 안에는 a,b,c,d,e,f 의 단어만 있다고 가정한다. 파일의 크기는 100,000 개 이고 각 문자의 등장 횟수는 다음과 같다. Fixed-length code:.. vprog1215.tistory.com Decoding 앞서 encoding 한 파일을 decoding 하면 된다. 방법은 간단하다 이미 file 에는 run 의정보 가 담겨 있다. run 을 읽고 codeword 를 따라서 트리를 조회 하면 된다. run 을 읽어들이는 코드 private void inputF.. 2021. 10. 15. [Algorithm] Huffman Coding 2: Encoding 예제 설명 과 구현 Huffman 개념 https://vprog1215.tistory.com/232 [Algorithm] Huffman Coding 1: 개념 Huffman Coding 무손실 압축 알고리즘이다. Huffman Coding 예시 파일 안에는 a,b,c,d,e,f 의 단어만 있다고 가정한다. 파일의 크기는 100,000 개 이고 각 문자의 등장 횟수는 다음과 같다. Fixed-length code:.. vprog1215.tistory.com Huffman Method With Run-Length Encoding 실제 예제를 가지고 어떻게 허프만 알고리즘이 동작 하는지 알아본다. 인코딩 대상 각각의 런을 구하고 해당 런에 코드워드를 부여한다. 즉 런에대해서 이진코드를 부여한다. 예제 AAABAACCAABA 해당.. 2021. 10. 15. [Algorithm] Complete Binary Tree Complete Binary Tree 완전 이진 트리라고 한다. 이번글에는 Insert 와 순회만 구현하려고 한다. Complete Binary Tree 특징 부모는 최대 2개의 자식을 가질 수 있다. 마지막 레벨에서 왼쪽부터 차례대로 채워져 있는 트리다. 중간에 비어있는 트리가 있으면 안된다. 트리는 Root, Parent, Child 로 구성 되어 있다. Complete Binary Tree 완전이진트리이다. 마지막 레벨 에 하나의 노드 만 빼고 꽉 차있다. 구현 사실 트리 구조는 노드와 insert 연산 탐색 연산이면 충분하다. 하지만 insert 할때 순서대로 채우려면 어떻게 해야될까? 고민을좀 했다. queue를 이용해서 다음에 채워야할 노드를 저장하고 있으면 될것 같다. 구현 구현코드 pack.. 2021. 10. 3. 이전 1 2 3 4 ··· 7 다음 728x90 반응형
