파이썬 알고리즘/그리디 알고리즘 (5) 썸네일형 리스트형 Huffman 압축 및 해제 프로그램 https://needneo.tistory.com/95 [Python] 파이썬 명령 인자값 받는 방법 (sys.argv) 파이썬으로 작성된 파일을 실행할 때 인수(argument, 인자값)를 받아서 처리를 해야 되는 경우가 있다. 예를 들어, 로컬과 개발 등의 환경이 서로 달라서 인자값을 줘야 한다던지 같은 파일을 다른 needneo.tistory.com huffman.py라는 파이썬 프로그램에서 3개의 인자값을 받아 이 값을 해석해 허프만 압축 및 복호화하는 프로그램을 만들고자 한다. 3개의 입력인자 1. -z(압축) / -x(압축해제) : 2개 중 선택 2. 입력 파일명 3. 출력 파일명 위의 세 개의 인자값을 입력받았을 때 첫 번째로 입력받은 인자가 "-z" 면, "입력 파일명"에 해당하는 파일을 .. 허프만 압축 파일 압축 파일의 각 문자가 8bit 아스키(ASCII) 코드로 저장되면 그 파일의 bit 수 = 8 * (파일의 문자 수) 파일의 각 문자는 일반적으로 위와 같이 고정된 크기의 코드로 표현 고정된 크기의 코드로 구성된 파일을 저장하거나 전송할 때 파일의 크기를 줄이고, 필요시 원래의 파일로 변환할 수 있으면, 메모리 공간을 효율적으로 사용할 수 있고, 파일 전송 시간을 단축 허프만 압축 파일에 빈번히 나타나는 문자에는 짧은 이진 코드를 할당, 드물게 나타나는 문자에는 긴 이진 코드를 할당 즉 문자의 빈도수에 기반을 둔 이진 트리를 만들어서, 각 문자에 이진 코드 할당 이렇게 만들어진 이진 코드 = 허프만 코드 허프만 압축 방법으로 변환시킨 문자 코드들 사이에는 접두부 특성(prefix property).. 최단 경로 찾기 (다익스트라 알고리즘) 최단 경로(Shortest Path) 찾기 주어진 가중치 그래프에서 어느 한 출발점에서 또 다른 도착점까지의 최단 경로 다익스트라(Dijkstra) 알고리즘 최단 경로를 찾는 가장 대표적인 알고리즘 주어진 출발점에서 시작 출발점으로부터 최단 거리가 확정되지 않은 점들 중에서 출발점으로부터 가장 가까운 점을 추가하고, 그 점의 최단 거리를 확정 1. 출발점(s) = 서울 D[s] = 0으로 초기화 (여기서 D[v]는 출발점 s로부터 점 v까지의 거리를 저장하는 배열) s를 제외한 D[v] = ∞로 초기화 트리(T)에는 최단 거리가 확정된 지점 저장, 처음에는 T = [출발점(s)]로 초기화 (각 지점v의 인덱스 순서가 아래와 같다고 가정) D = [서울, 천안, 원주, 강릉, 논산, 대전, 대구, 포항 광.. 최소 신장 트리 (Prim MST) 최소 신장 트리 (Minimum Spanning Tree) 주어진 가중치 그래프에서 사이클 없이 모든 점들을 연결시킨 트리들 중 간선들의 가중치 합이 최소인 트리 크러스컬(Kruskal) 알고리즘 프림(Prim) 알고리즘 Prim MST 임의의 점 하나를 선택 후 그 점을 기준으로 연결된 간선들 중 가중치가 가장 작은 간선을 선택해 트리에 추가 1. 임의의 점 하나(ex. c) 선택, 그 점에 대한 D[c] = 0으로 초기화 (여기서 D는 하나의 기준점과 나머지 점들 사이의 거리를 저장하는 배열) 2. c에서 각 점을 사이의 거리를 D[]에 저장, c에 연결되어 있는 점은 가중치로 초기화, 연결되어 있지 않은 점은 ∞로 초기화 D = [∞, 1, 0, ∞, ∞, 1] (a부터 f 순) 3. 트리는 기준점.. 최소 신장 트리 (Kruskal MST) 최소 신장 트리 (Minimum Spanning Tree) 주어진 가중치 그래프에서 사이클 없이 모든 점들을 연결시킨 트리들 중 간선들의 가중치 합이 최소인 트리 크러스컬(Kruskal) 알고리즘 프림(Prim) 알고리즘 Kruskal MST 가중치(거리)의 오름차순으로 간선들을 정렬하여 정렬된 간선들을 리스트에 저장 트리 선언 및 초기화(null로) 트리의 간선 수가 n-1이 될 때까지 아래의 반복문 수행 정렬된 간선들을 저장한 리스트에서 가장 작은 가중치를 가진 간선 선택 및 리스트에서 제거 만약 선택한 간선이 트리에 추가되어 사이클을 만들지 않으면 트리에 선택한 간선 추가 사이클을 만들면 선택한 간선 그냥 버리기 최종적으로 트리를 리턴 선택한 간선이 사이클을 만드는지 확인하는 방법 연결하려는 두 점.. 이전 1 다음
