자료구조+알고리즘

cmp_to_key / 커스텀 정렬

Why? 배열을 정렬할 때, 아래 문제처럼 원하는 기준으로 정렬을 하고 싶을 때가 있을 것이다! https://programmers.co.kr/learn/courses/30/lessons/42746 코딩테스트 연습 - 가장 큰 수 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 programmers.co.kr 이러한 경우에 key에 단순한 lambda식을 넣어서 문제를 해결할 방법이 떠오르지 않는다! 사용법 커스텀 정렬을 하고 싶다면 아래처럼 cmp_to_key를 임포트한 후 커스텀 함수를 만들어서 리턴값을 ..

이진 탐색

Binary search 배열이 정렬되어 있을 경우, 절반씩 줄여나가면서 탐색하는 기법 이진 탐색을 사용하기 위해서 배열이 꼭 정렬되어 있어야 한다!! left = 0, right = 배열의 길이 - 1, mid = (left + right) // 2로 시작해서 만약 찾고자 하는 값이 mid 인덱스에 해당하는 값보다 크면 left = mid + 1로 바꿔주고 찾고자하는 값이 mid 인덱스에 해당하는 값보다 작으면 right = mid - 1로 바꿔주면서 left가 right보다 크거나 같을 때까지 반복해준다! 예시 - 4의 위치 찾기 a = [1, 2, 3, 4, 5, 6, 7, 8] 일 때, left = 0, right = 1, mid = (left + right) // 2 = 3 로 시작한다 a[mi..

정렬 - quick, merge

퀵 정렬 - Quik sort 분할 정복(Divide and Conquer)을 이용해서 배열을 정렬하는 알고리즘 배열에서 기준(pivot)을 정해서 기준보다 작은 집합과 큰 집합으로 나누고(Divide) 그 사이에 기준을 위치시킨다. 작은 집합과 큰 집합을 대상으로 재귀호출하여 정렬(Conquer)한 뒤 결과를 합치면 정렬된 배열을 구할 수 있다! 시간 복잡도는 최선일 때 O(NlogN) 최악일 때(내림차순으로 정렬되어 있거나 오름차순으로 정렬되어있을 때) O(N^2) 예시 1단계 마지막 원소인 4를 기준(pivot)으로 정하고 pivot보다 작은 집합의 인덱스 i를 -1로 설정한다 (맨 왼쪽 인덱스-1) → i보다 같거나 작은 인덱스에 해당하는 값은 전부 pivot보다 작은 값이다 j는 pivot에 해..

정렬 - bubble, selection, insertion

버블 정렬(bubble sort) 첫번째와 두번째, 두번째와 세번째, N-1번째와 N번째 요소를 비교해 나가면서 정렬을 하는 방법 만약 N-1번째와 N번째 요소를 비교했다면 다시 첫번째와 두번째 요소부터 N-2번째와 N-1번째 요소를 비교한다! 만약 오름차순으로 정렬하려면 매번 두 요소를 비교할 때마다 작은 요소와 큰 요소의 위치를 바꾼다 반복문 두개를 중첩해서 사용하므로 시간복잡도는 O(N^2) 예시 소스코드 def bubblesort(lst): lst_len = len(lst) - 1 for i in range(lst_len): j = lst_len - i for k in range(j): if lst[k] > lst[k + 1]: lst[k], lst[k + 1] = lst[k + 1], lst[k..