huhsae's day huhsae's day

Huffman Coding Huffman Coding허프만 코드는 손실이 적은 데이터 압축 알고리즘이다. 기본 아이디어는 가변길이 코드를 문자로 할당하는 것이다. 할당된 코드의 길이는 일치하는 문자의 빈도에 기본으로 한다. 가장 빈도수가 많은 문자는 가장 작은 코드를 할당 받고 가장 빈도가 적은 문자는 큰 코드를 할당 받는다. 입력문자에 할당 된 가변 길이 코드는 접두사 코드이다. 이는 한 문자에 할당된 코드가 다른 문자에 할당 된 코드의 접두사가 아닌 방식으로 코드가 할당되었음을 의미한다. 이것은 허프만 코딩가 생성 된 비트 스트림을 디코딩 할 때 애매함이 없는지 확인하는 방법이다. 카운터 예제로 접두사 코드를 이해해보자. a,b,c,d의 카운터가 있고 각각 일치하는 코드는 00, 01, 0, 1이다...

GeeksforGeeks의 글을 해석한 포스트 입니다.Optimal Substructure Property in dynamic Programing / DP-2 이전 글에서 살펴 본것 처럼, 다음은 다이나믹 프로그래밍을 사용해서 풀수 있는 문제의 특성이다. 1) Overlapping Subproblems2) Optimal Substructure 먼저 이전 글에서 첫번째 특성은 알아 보았다. 다음으로 두번째 속성에 대해서 알아보도록 하자2) Optimal Substructure: 부문문제의 최적의 솔루션을 사용해서 주어진 문제의 최적의 해를 구할 수 있다면 이를 최적의 하부구조 속성이라고 한다. 예를 들어 최소 길이 문제는 Optimal substructure 속성을 따른다. 만약에 노드 x가 시작점 u에서..

GeekforGeek-dp1 페이지를 해석한 포스트입니다. 다이나믹 프로그램에서 부문문제 오버랩핑 특성 다이나믹 프로그래밍은 주어진 복잡한 문제를 부분문제로 나눠 문제를 해결하고 같은 결과를 다시 계산하는 것을 피하기 위해 부문문제의 답을 저장하는 알고리즘 패러다임이다. 다음은 다이나믹 프로그래밍으로 풀 수 있는 문제의 두가지 특징이다. 이번 포스트에서는 첫번째 특징( Overlapping Subproblems)을 자세히 살펴볼 것이다. 두번째 특징은 다음장에서 알아볼 것이다.Overlaping SubproblemsOptimal Substructure 1) Overlapping Subproblems: 분할 정복처럼, 다이나믹 프로그래밍은 부분문제의 해결책을 조합한다. 다이나믹 프로그램은 주로 반복되는 부..

BufferedReader자바에서 사용되는 입력 받는 방법에 대해서 알아보자. 알고리즘을 풀 때 Scanner를 사용하면 입력이 느린경우가 있다. 최적하를 위해서 어떤 방법이 있는지 알아보자.Scanner​xScanner sc = new Scanner( System.in );int T = sc.nextInt(); 자바에서 가장 흔하게 입력받는 방법이다. nextInt()의 경우 개행문자를 받지 않기 때문에 입력받을 때 신경써주어야 한다. BufferedReaderxxxxxxxxxxBufferedReader br = new BufferedReader( new InputStreamReader(System.in));int T = Integer.parseInt( br.readLine()); BufferedRea..

ListView ListView 리스트뷰는 안드로이드에서 기본인데, 매번까먹는다. 이 포스팅은 listview에 대한 설명이 아니라 내가 이해하려고 적은 글이기 때문에 자세한 사용법은 다른 글에서 찾으시길 바란다. 커스텀 리스트뷰 만드는 방법과 동작에 관해서 매번 까먹어서 그림으로 기억하려고 한다. 1. BaseAdapter를 상속한 커스텀 adapter를 만들자Adapter를 상속해서 오버라이드 해야하는 모든 메소드들을 불러오자. ( alt+insert )어댑터는 아이템(즉 리스트뷰에 보여주고자 하는 것)을 가지고 있다. 아이템리스트에 아이템을 추가하는 메소드를 만들자 addAll(List a), add(item i);getView() 메소드가 가장 중요하다getView()에서 전달 받은 view가 없..

2188 축사 2188 축사https://www.acmicpc.net/problem/2188 분류네트워크 유량애드몬드-카프 알고리즘BFS이분 매칭 TIPS포드 - 풀거슨 알고리즘을 풀 때, v -> u로 가는 용량이 주어진다면, u -> v로 가는 용량 0의 간선을 만들어 주어야 한다.코드에서는 capacity[][] 배열을 사용해서 그래프를 나타내준다면, 초기값이 0이기 때문에 1번의 내용을 생각해줄 필요가 없다. 하지만 간선 찾는 시간을 단축시키기 위해 인접리스트로 그래프를 표현했다면, 꼭 인접리스트에 반대로 가는 가상의 간선을 만들어주어야한다. 처음부터 그래프를 배열로 했다면 상관없다.이분 매칭은 source와 sink가 여러개인 네트워크 유량문제에서 super source와 super sink를 ..

vogella[Android Architecture with MVP or MVVP Tutorial] http://www.vogella.com/tutorials/AndroidArchitecture/article.html MVP MVVM 모델을 활용한 안드로이드 설계안드로이드 아키텍쳐 이 튜토리얼은 테스트가능성을 증진시킬 수 있는 안드로이드 어플리케이션 아키텍쳐에 대하여 설명하고 있다. 1. 안드로이드를 위한 설계 안드로이드의 기본 탬플릿은 대규모의 액티비티 나 프래그먼트의 사용을 기본으로 한다. 이 요소들은 일반적으로 비지니싀와 UI로직을 포함하고 있다. 이 것은 테스트와 안드로이드의 유지보수를 어렵게 한다. 다음은 테스트 가능성을 향상시킬 수 있는 유명한 패턴들이다.Model View Presenter ..

1504 특정한 최단 경로백준 특정한 최단 경로 Tip다익스트라 알고리즘 활용다익스트라 알고리즘은 출발점에서 모든 정점에 대한 최단거리를 구하는 알고리즘이다.꼭 들려야 하는 정점을 끝나는 지점으로 하는 다익스트라를 여러번 돌려 원하는 값을 찾을 수 있다. CODE​ximport java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;​public class BOJ_1504 {​ static final int INF = 800000; static List[] map; static int node; static int edge;​ public static void main(Strin..