분류 전체보기 (42) 썸네일형 리스트형 최근접 점 사이 거리 구하기 최근접 점 사이 거리 구하기 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) 옆부터 작은 값을 찾.. TypeError: 'list' object is not callable range는 파이썬에서 쓰는 기본적인 함수 이름인데 내가 range라는 변수를 만들어서 거기에 값을 저장하고 출력하려 해서 - object is not callable이라는 에러가 떴다. 파이썬에서 [원래 있던 함수]와 [내가 만든 변수]의 이름이 중복되어 어떤 것을 불러올지 몰라 나타나는 에러 함수 실행 코드가 잘못된 줄 알고 손으로 하나하나 실행과정을 다 따져봤는데도 이상이 없는데 자꾸 저런 에러가 떠서 검색해 보니 파이썬에서는 자주 나타나는 에러임을 알았다. 변수명을 range에서 findRange로 수정하니까 제대로 동작 퀵 정렬(Quick Sort) 동빈나 실전 알고리즘 강좌(Algorithm Programming Tutorial) 참고 https://www.youtube.com/playlist?list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz 실전 알고리즘 강좌 (Algorithm Programming Tutorial) www.youtube.com 퀵 정렬(Quick Sort) 특정한 값(피벗)을 기준으로 큰 숫자와 작은 숫자를 나누자 피벗(Pivot) : 퀵 정렬에서의 기준 값, 보통 첫 번째 원소를 피벗값으로 지정 하나의 큰 문제를 두 개의 작은 문제로 분할하는 방식으로 빠르게 정렬 ▶ 분할 정복 알고리즘의 대표적 예 평균 시간 복잡도 : O(N*logN) 최악의 시간 복잡도 : O(N^2) 분할 정복의 이점을 사용하지 못.. 삽입 정렬(Insertion Sort) 동빈나 실전 알고리즘 강좌(Algorithm Programming Tutorial) 참고 https://www.youtube.com/playlist?list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz 실전 알고리즘 강좌 (Algorithm Programming Tutorial) www.youtube.com 삽입 정렬(Insertion Sort) 각 숫자를 적절한 위치에 삽입하자 다른 정렬방식들은 무조건 위치를 바꾸는 방식이었다면 삽입 정렬은 필요할 때만 위치를 바꿈 시간 복잡도 : O(N^2) 시간 복잡도는 선택 정렬, 버블 정렬과 같으나 거의 정렬된 상태라면 삽입 정렬이 훨씬 효율적으로 동작 만약 1 5 10 8 ... 의 숫자가 있고, 8의 위치를 결정할 경우라면 8은 _1_5_1.. 버블 정렬(Bubble Sort) 동빈나 실전 알고리즘 강좌(Algorithm Programming Tutorial) 참고 https://www.youtube.com/playlist?list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz 실전 알고리즘 강좌 (Algorithm Programming Tutorial) www.youtube.com 버블 정렬(Bubble Sort) 옆에 있는 값과 비교해서 더 작은 값을 앞으로 보내자 시간 복잡도 : O(N^2) 시간 복잡도는 선택 정렬과 같으나 더 비효율적 => 선택 정렬은 가장 작은 하나의 값을 찾아서 맨 앞의 값과 한 번씩 교환하지만 버블 정렬의 경우 서로 값을 교환하는 코드가 더 많이 실행되기 때문 정렬 알고리즘 중 가장 느린 알고리즘 = 버블 정렬 알고리즘 첫 번째 요.. 이전 1 2 3 4 5 6 다음
