정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 코드 #1. recursive를 이용함 def binary_search(array, target, start, end): if start>end: return None mid = (start + end) // 2 #찾으려는 target이 array의 중간에 있다면 if target == array[mid]: return array[mid] #중간보다 작다면 -> 끝점을 중간 하나 전으로 옮긴다. elif target 시작점을 중간 다음으로 옮긴다. else: return binary_search(array, target, mid+1, end) n, target = int(input().split()) array = list(ma..

간단하지만 느린 기본 정렬 알고리즘 n-1번의 round가 진행 매 round마다 하나는 sort(비교+교환) 한다. 삽입정렬 코드 삽입정렬 구현 방법 i까지 정렬되어 있다. 그리고 그 다음 i+1이 정렬된 부분에서 자신에게 맞는 자리를 찾아 간다. 아래는 insertion sort의 과정을 나타낸다. 노란 부분은 이미 정렬된 부분으로 핑크 선이 그어진 숫자가 노란 부분에서 자기에게 맞는 자리를 찾는다. 초기상태: 정렬이 필요한 상태 1. 8이 정렬되어있는 부분이고, 그 다음 5가 노란 부분 안에서 자신에게 맞는 위치를 찾는다. 1-1. 5와 8을 비교해보았을때, 5

전형적인 divide-and-conquer알고리즘 퀵 소트의 분할된 크기에 따라 영향을 많이 받는 것을 막기 위한 방법 강제로 절반으로 나누어서 분할하는 방법 Merge Sort 코드 Merge Sort구현 방법 초기상태: 정렬이 필요한 list 1. (대략적인) 절반을 기준으로 나눈다(노랑&파랑) 2. 1번을 반복한다. 3. 모든 수가 각각 하나로 분리되었다. 4. 3에서 각각 분할 된 것을 정렬하여 합친다. 정렬 시, 둘 중 작은 것을 먼저 넣고, 둘 중 하나라도 끝나면 나머지는 그냥 모두 순서대로 넣는다. 5&6. 4번 과정처럼 병합 한다. 시간 복잡도 n/2 n/2 T(n) = 2*T(n/2) + (merge_two_sorted_lists) = 2*T(n/2) + c*n =O(nlogn) 언제 어..

실제 가장 빠른 정렬 알고리즘 전형적인 divide-and-conquer 알고리즘 중 하나 pivot보다 작은 값들을 리스트의 왼쪽으로, 큰 값들은 리스트의 오른쪽으로 재배열 한 후, 양 쪽을 재귀적으로 다시 정렬 퀵 정렬 코드(python) 퀵 정렬 구현 방법 초기상태 입력이 주어진 정렬해야 할 배열이다. 피벗은 arr[0], left와 right도 정의되어 있다. 1. left: 피벗 보다 큰 값이 나올 때까지 left++한다. 5>4이기 때문에 left는 더 이상 이동하지 않는다. right: 피벗보다 작은 값이 나올 떄까지 right --한다. 7>4이기 때문에 right--한다. 2. left: 이동이 없었다. right: 피벗보다 작은 3이 나오니 드디어 멈췄다. 3. left

리스트에 저장된 값들을 크기 순서에 따라 재배열하는 문제 가능한 비교 횟수와 자리바꿈을 최소화 하는 것이 목표 매우 기본적이고 중요한 알고리즘 문제 중 하나 단순 분류 기본 정렬 알고리즘: 느리지만 단순한 정렬 알고리즘 - insertion, selection, bubble정렬 알고리즘 빠른 알고리즘: 빠르지만 복잡할 수도 있는 정렬 알고리즘 - quick, heap, merge정렬 알고리즘 특별한 상황에 맞는 정렬 알고리즘 - count, radix, bucket정렬 알고리즘 정렬 알고리즘의 성질 1. stable & unstable - stable: 크기가 같은 숫자인 경우, 원래 입력 순서를 정렬 후에도 유지하는 알고리즘 2. in-place & not-in-place - in-place: 상수 개..

1. 알고리즘 정의 "어떤 종류의 문제를 풀기 위한 방법", " 어떤 종류의 문제를 컴퓨터를 사용하여 해걀하기 위한 효율적인 방법" --> " 주어진 조건에서 컴퓨터를 사용하여 효율적으로 문제를 해결하는 방법" 2. 알고리즘의 표기 방법 O표기법: 알고리즘의 성능을 평가하기 위해 처리해야 할 데이터의 양에 대한 실행 시간을 수학적으로 계산하는 방법, 최악의 성능에 대한 측정 방법 O(1): 데이터의 양과 무관, 항상 일정한 실행 시간을 가짐 O(N): 실행시간이 처리해야 하는 데이터 양(N)과 비례함 O(logN): 데이터 양이 증가하면 실행시간도 증가. 하지만 logN의 그래프를 갖기 때문에 급격한 증가는 아님, 효율적인 검색 알고리즘의 성능 O(NlogN): 정비례보다 약간 더 증가. 효율적인 정렬 ..