본문 바로가기

분류 전체보기

 (42)
기수 정렬 (Radix Sort) 기수 정렬 (Radix Sort) 제한적인 범위 내에 있는 숫자(ex. 주민등록번호, 학번, 계좌번호)에 대해서 각 자릿수 별로 정렬하는 알고리즘 기(radix) : 특정 진수를 나타내는 숫자들 10진수의 기 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 2진수의 기 : 0, 1 LSD 기수 정렬 Least Significant Digit(LSD) 기수 정렬 1의 자리부터 k자리로 정렬 수행 RL(Right-to-Left) 기수 정렬이라고도 함 MSD 기수 정렬 Most Significant Digit(MSD) 기수 정렬 k자리부터 1의 자리로 정렬 수행 LR(Left-to-Right) 기수 정렬이라고도 함 # LSD(RL) 기수 정렬 from collections import deque def..
힙 정렬 (Heap Sort) 이진 힙 (Binary Heap) 힙 조건(각 노드의 우선순위가 자식 노드의 우선 수위보다 높음)을 만족하는 완전 이진트리 최대 힙(Maximum Heap) : 가장 큰 값을 루트에 저장 최소 힙(minimum Heap) : 가장 작은 값을 루트에 저장 힙에서 부모와 자식 관계 A[i]의 왼쪽 자식 = A[2i] A[i]의 오른쪽 자식 = A[2i+1] A[i]의 부모 = A[i/2] (i가 홀수면 i/2에서 정수 부분만) 힙 정렬 (Heap Sort) 정렬할 입력으로 최대 힙을 만들어 가장 큰 수가 저장되어 있는 루트와 힙의 가장 마지막 노드를 교환(가장 큰 수를 배열의 맨 뒤로 옮김) 힙 크기를 1개 줄인 후 위배된 힙 조건을 해결하여 다시 힙 정렬 수행 루트 90과 힙의 마지막 노드 40을 바꾼 후..
쉘 정렬 쉘 정렬 삽입 정렬을 이용하여 배열 뒷부분의 작은 숫자를 앞부분으로 빠르게 이동시키고, 동시에 앞부분의 큰 숫자는 뒷부분으로 빠르게 이동시키는 정렬 알고리즘 간격(gap)을 이용 30 60 90 10 40 80 40 20 10 60 50 30 40 90 80 ◼ 간격(gap)이 5인 숫자 그룹 그룹1 : [30, 80, 50] 그룹2 : [60, 40, 30] 그룹3 : [90, 20, 40] 그룹4 : [10, 10, 90] 그룹5 : [40, 60, 80] 각 그룹 별로 삽입 정렬 수행 ▶ 30 30 20 10 40 50 40 40 10 60 80 60 90 90 80 처음보다 비교적 큰 숫자가 뒷부분으로, 작은 숫자가 앞부분으로 이동 그 다음에는 간격을 전에 설정한 것보다 작게 하여 다시 그룹별 삽..
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이 될 때까지 아래의 반복문 수행 정렬된 간선들을 저장한 리스트에서 가장 작은 가중치를 가진 간선 선택 및 리스트에서 제거 만약 선택한 간선이 트리에 추가되어 사이클을 만들지 않으면 트리에 선택한 간선 추가 사이클을 만들면 선택한 간선 그냥 버리기 최종적으로 트리를 리턴 선택한 간선이 사이클을 만드는지 확인하는 방법 연결하려는 두 점..

티스토리툴바