본문 바로가기

파이썬 알고리즘

 (20)
쉘 정렬 쉘 정렬 삽입 정렬을 이용하여 배열 뒷부분의 작은 숫자를 앞부분으로 빠르게 이동시키고, 동시에 앞부분의 큰 숫자는 뒷부분으로 빠르게 이동시키는 정렬 알고리즘 간격(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이 될 때까지 아래의 반복문 수행 정렬된 간선들을 저장한 리스트에서 가장 작은 가중치를 가진 간선 선택 및 리스트에서 제거 만약 선택한 간선이 트리에 추가되어 사이클을 만들지 않으면 트리에 선택한 간선 추가 사이클을 만들면 선택한 간선 그냥 버리기 최종적으로 트리를 리턴 선택한 간선이 사이클을 만드는지 확인하는 방법 연결하려는 두 점..
최근접 점 사이 거리 구하기 최근접 점 사이 거리 구하기 2차원 평면에 n개의 점이 입력으로 주어졌을 때 가장 가까운 점 사이의 거리를 구하는 문제 제일 먼저 입력값을 x축을 기준으로 오름차순 정렬 n개의 점을 반씩 분할(n // 2)하여 각각의 부분에서 최근접 점 사이의 거리를 구하고, 그 두 부분에서 각각 구한 거리를 비교해 더 짧은 거리를 dist라는 변수에 저장 여기서 주의할 점은 기준선 사이의 점들에 대한 거리값도 구해봐야 한다는 것 기준선(x축: n // 2, y축:0) 근처 x축 좌표 ± dist 안에 속하는 점들을 배열에 담고 그 속에서 dist보다 더 짧은 거리가 존재하는지 검사 후 작은 값을 dist_strip이라는 변수에 저장 기준선 사이 영역의 거리를 구할 때 x의 거리는 배열에 담으면서 추렸으니까 y를 기준으..
선택 문제 선택 문제 n개의 숫자들 중에서 k번째로 작은 숫자를 찾는 문제 ▶ 숫자들을 정렬한 후, k번째 숫자 찾기 퀵 정렬을 수행하면서 피벗의 위치를 기준으로 k번째의 숫자를 찾을 것 k는 1부터 배열의 길이까지 선택 가능 인덱스는 0부터 시작하므로 내가 3번째 위치의 수를 찾고자한다면 인덱스로는 2에 위치한 수를 출력하면 됨 k = 피벗인덱스 + 1 일 때 피벗의 값을 출력하면 됨(피벗[인덱스]) ex) k = 3 이면 피벗인덱스가 2일 때 그 값을 출력 import random # 퀵정렬을 수행하며 k번째 작은 숫자 찾기 # 피벗의 인덱스 + 1 이 k면 피벗 출력 def selection_k_min(arr, k): if 0 < k and k end): continue pivot = arr[start] pi..

티스토리툴바