파이썬 알고리즘/분할 정복 알고리즘 (4) 썸네일형 리스트형 최근접 점 사이 거리 구하기 최근접 점 사이 거리 구하기 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.. 합병 정렬 합병 정렬 입력이 2개의 부분 문제로 분할되고, 부분 문제의 크기가 1/2로 감소하는 분할 정복 알고리즘 가장 작은 부분 문제로 계속 쪼갠 뒤 가장 작게 쪼개진 부분문제들을 점차 합병하면서 최종적으로 큰 문제를 해결하는 알고리즘 1. 가장 작은 부분이 될 때까지 반으로 계속 분할 2. 가장 작은 부분들 2개씩부터 합병하면서 최종적으로 정렬된 하나가 됨 import random # 가장 작은 조각이 될 때까지 계속 분할 + 가장 작은 부분이 되면 거기서부터 점차 합병 def merge_sort(A): if len(A) > 1: mid = len(A) // 2 left = A[:mid] # 0부터 mid-1까지 right = A[mid:] # mid부터 끝까지 # 가장 작은 조각이 될 때까지 계속 분할(가장.. 퀵 정렬 (재귀X) 흔히 퀵 정렬에서는 왼쪽에서 오른쪽으로 가면서 피벗값보다 큰 값을, 오른쪽에서 왼쪽으로 가면서 피벗값보다 작은 값을 찾아 서로 바꾸면서 정렬을 진행함 오늘 할 건 재귀를 사용하지 않고 퀵 정렬을 구현하되 왼쪽에서 오른쪽으로만 이동하면서 정렬을 하고자 함 검색해야 하는 위치 정보를 [p, q]로 스택에 넣고 스택이 비워질 때까지 반복문 수행 8 3 11 9 12 2 6 15 18 10 7 14 가장 처음 스택에는 전체 범위 저장(0~11) i = 피벗 인덱스(검색해야 하는 배열의 가장 앞) j = 피벗 제외 배열을 이동하는 인덱스 j가 왼쪽에서 오른쪽으로 이동하면서 피벗보다 작은 값을 만나면 i를 1 증가시킨 후 그 자리의 값과 작은 값의 위치를 서로 바꿈 현재 i=0 j는 피벗(8) 옆부터 작은 값을 찾.. 이전 1 다음
