본문 바로가기
반응형

CS/알고리즘

 (10)
[알고리즘] Heap Sort Heap Sort 최대 힙, 최소 힙 구조를 통해 정렬하는 알고리즘 Heap 이란? 최솟값이나 최댓값을 빠르게 찾아내기 위해 사용되는 구조로 완전 이진 트리를 기반으로 하는 트리이다 각 노드의 값이 자신의 자식노드가 가진 값보다 크거나 같다면 최대 힙 (Max Heap) 각 노드의 값이 자신의 자식노드가 가진 값보다 작거나 같다면 최소 힙 (Min Heap) Process 1. 완전 이진트리 형태의 최대 힙을 만든다 2. 힙에서 하나씩 데이터를 꺼내어 배열의 맨 뒤에 저장한다 이 때 최댓값부터 꺼내지므로 내림차순으로 정렬된다 3. 남겨진 데이터는 최대 힙을 유지한다 heapify 힙 성질을 만족하도록 하는 연산을 heapify 라고 한다 예를 들어 최대 힙의 경우 루트 노드부터 리프 노드까지 부모 노드가..
[알고리즘] Counting Sort Counting Sort 데이터의 크기 범위가 양의 정수이며, 값의 범위가 메모리 사이즈를 넘지 않는 경우 값을 카운팅해 정렬하는 알고리즘 Process 1. 최댓값을 찾는다 2. 최댓값 + 1 크기의 카운팅 배열을 만든다 3. 데이터를 카운팅 배열의 인덱스와 매핑해 갯수를 센다 4. 카운팅 배열을 조회하며 카운트만큼 출력한다 Code numbers = [1, 0, 3, 2, 4, 3, 2, 2, 1, 1, 1, 1, 5, 3, 3, 4, 5] k = 5 counts = [] result = [] length = len(numbers) counts = [0] * length for num in numbers: counts[num] += 1 for num, cnt in enumerate(counts): f..
[알고리즘] Merge Sort Merge Sort Divide and Conquer(분할정복) 방법을 통해 구현 Pivot 없이 정확히 반씩 나누어 나중에 정렬하는 알고리즘 Process 1. 리스트 길이가 2 이상일 때 절반으로 분할한다 (divide) 2. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다 (conquer) 3. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병하며, 정렬 결과를 임시배열에 저장한다 (combine) 4. 임시 배열에 저장된 결과를 원래 배열에 복사한다 (copy) Code numbers = [] length = 100 for i in range(length, 0, -1): numbers.append(i) def merge(start, middle, end): temp = [] i, j =..
[알고리즘] Quick Sort Quick Sort Divide and Conquer(분할정복) 방법을 사용 기준 데이터인 Pivot을 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 알고리즘 Process 1. 기준 데이터(Pivot)를 고른다 2. 피벗 앞에는 피벗보다 값이 작은 데이터, 피벗 뒤에는 피벗보다 값이 큰 데이터들이 오도록 배열을 둘로 나눈다 이 때 피벗값은 위치가 정해진다. 3. 분할된 두개의 배열에 대해 재귀(Recursion)적으로 이 과정을 반복한다 Code numbers = [] length = 100 for i in range(length, 0, -1): numbers.append(i) def quickSort(start, end): global numbers if start >= end: re..
[알고리즘] Insertion Sort Insertion Sort 처리되지 않은 데이터 중 하나씩 골라 적절한 위치에 삽입하는 알고리즘 Process 1. 먼저 두번째 데이터와 첫번째 데이터의 대소를 비교해 두번째 원소가 더 작다면 교환한다 2. 다음 인덱스는 이전 데이터들과 비교해 적절한 위치에 둔다 Code numbers = [] length = 100 for i in range(length, 0, -1): numbers.append(i) for idx, num in enumerate(numbers): for n_idx in range(idx, 0, -1): if numbers[n_idx] < numbers[n_idx - 1]: numbers[n_idx], numbers[n_idx - 1] = numbers[n_idx - 1], numbe..
[알고리즘] Selection Sort Selection Sort 처리되지 않은 데이터 중 가장 작은 데이터를 선택해 처리되지 않은 데이터 중 맨 앞의 데이터와 바꿔가는 알고리즘 Process 1. 처리되지 않은 데이터 중 최소값을 찾는다 2. 처리되지 않은 데이터 중 맨 앞에 위치한 값과 교체한다 3. 그 다음 인덱스 부터 같은 방법으로 교체한다 Code numbers = [] length = 100 for i in range(length, 0, -1): numbers.append(i) for idx, num in enumerate(numbers): min_idx = idx for n_idx in range(idx + 1, length): if numbers[n_idx] < numbers[min_idx]: min_idx = n_idx num..
[알고리즘] Bubble Sort Bubble Sort 서로 인접한 두 데이터의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 Process 1. 첫번째 원소부터 마지막 원소까지 인접한 데이터를 비교해 조건에 맞지 않다면 서로 교환 2. 1번 수행 후엔 가장 큰 원소가 맨 뒤로 이동하게 되어 정렬에서 제외되고 (배열의 크기 - 1)만큼 반복하면 모든 데이터가 정렬됨 Code numbers = [] length = 100 for i in range(length, 0, -1): numbers.append(i) for _ in range(length): for i in range(length - 1): if numbers[i] > numbers[i + 1]: numbers[i], numbers[i + 1] = num..
[알고리즘] Floyd Warshall Algorithm Floyd Warshall Algorithm 이란? 모든 정점에서 모든 정점으로 가는 최단거리를 구하는 알고리즘 특징 가중치/비가중치 그래프 모두에서 최단거리를 도출해낼 수 있다 음수 가중치를 가져도 사용가능하다 (단, cycle이 있고 가중치의 총 합이 음수인 경우엔 성립하지 않는다) 시간복잡도가 O(V³) 이다 다이나믹 프로그래밍(DP)을 사용하는 알고리즘이다 Floyd Warshall Algorithm 동작 과정 1. 모든 노드 무한대로 초기화 2. 자기 자신에게 가는 간선의 가중치는 0으로 설정 ( i -> i ) 3. 나머지 노드 방문하며 주변 노드에 방문하는 최단거리 갱신 - i 에서 j 로 가는데에 크게 두가지 경우로 나뉘고, 이 두가지 경우 중 최소값을 선택 1) i 에서 j 로 가는 경로..
반응형

티스토리툴바