728x90 반응형 BASE34 알고리즘 - 합병 정렬 (Merge Sort) 알고리즘 - 합병 정렬 (Merge Sort) 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다. 합병 정렬은 분할 - (정복) - 결합의 단계로 이루어진다. 분할 : 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다. 정복 : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용해 다시 분할 정복 방법을 적용한다. 결합 : 정렬된 부분 배열들을 하나의 배열에 합병한다. 합병 정렬은 추가적인 리스트가 필요하며 각 부분 배열을 정렬할 때도 합병 정렬을 순환적으로 호출하여 적용한다. 합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병하는 단계이다. .. 2021. 1. 26. 알고리즘 - 이진 탐색 (Binary Search) 알고리즘 - 이진 탐색 (Binary Search) 오름차순으로 정렬된 리스트에서 특정 값의 위치를 찾는 알고리즘으로, 모든 값을 순회해야하는 일반적인 search보다 더 빠르다. 중앙값을 찾는 값에 비교해서 중앙값이 찾는 값보다 크면 왼쪽을 탐색하고 찾는 값보다 작으면 오른쪽을 탐색한다. 최악의 경우에도 탐색 대상을 절반씩 계속해서 줄여나가기 때문에, 탐색 횟수가 logN이다. 따라서 T(N) = O(logN) [ 예시 ] [ 코드 ] def binary_search(arr, target): low, high = 0, len(arr) - 1 while low target: high = mid - 1 if arr[mid] == target: return mid if arr[mid] < target: l.. 2021. 1. 26. 알고리즘 - 선택 정렬 (Selection Sort) 알고리즘 - 선택 정렬 (Selection Sort) 제자리 정렬 알고리즘 중 하나로, 입력 데이터 이외에 다른 추가 메모리를 요구하지 않는다. 알고리즘이 단순하고 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다. 주어진 리스트 중에서 최소값을 먼저 찾고, 그 값을 맨 앞에 위치한 값과 교체한다. 맨 처음 위치를 뺀 나머지 리스트들을 같은 방법으로 끝까지 교체한다. 모든 경우 시간복잡도 : (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2= O(n^2) [예시] [Code] def selection_sort(arr): for i in range(len(arr) - 1): min_idx = i for j in range(i + 1, len(arr)): if a.. 2021. 1. 11. 알고리즘 - 삽입 정렬 (Insertion Sort) 알고리즘 - 삽입 정렬 (Insertion Sort) 삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. 최악의 경우 시간복잡도 : (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2= O(n&2) (최악의 경우) 최선의 경우 시간복잡도 : O(n) (정렬이 모두 되어있는 경우에는 한 번 씩만 비교하면 되기 때문) [예시] 각 회전 마다 연두색 밑줄이 되어 있는 부분이 이미 정렬된 배열 부분! [ 코드 ] def insertion_sort(arr): for end in range(1, len(arr)): for i in range(end, 0, -1): if arr[i - 1] >.. 2021. 1. 11. 알고리즘 - 버블 정렬 / 거품 정렬 (Bubble Sort) 알고리즘 - 버블 정렬 / 거품 정렬 (Bubble Sort) 버블 정렬은 서로 인접한 두 원소를 검사해 정렬하는 알고리즘이다. 첫 번째 자료와 두 번째 자료, 두번째 자료와 세 번째 자료, ... , 마지막-1 번째 자료와 마지막 자료의 대소를 비교해 교환한다. 1회전 할 때 마다 마지막 자료는 가장 큰 값이 되므로 (조건이 오름차순일 경우) 정렬에서 제외한다. [ 시간복잡도 ] (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2 = O(n^2) [ 예시 ] [ 코드 ] size = int(input()) arr = [] for i in range(size): arr.append(int(input())) for i in reversed(range(size)): for j in ra.. 2021. 1. 8. 자료구조 - 해싱(Hashing) 1. 해싱이란? 해시(Hash)란 데이터를 다루는 기법 중 하나이며, 해시 함수(Hash function)는 데이터를 효율적으로 관리하기 위해서 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 매핑 전 원래 데이터의 값을 Key, 매핑 후 데이터의 값을 Hash Value 또는 해시 코드라고 하며 키와 값으로 매핑되는 과정 자체를 해싱이라고 한다. 탐색, 삽입, 삭제 연산 모두 해시 함수를 거치는 시간만 소요되기 때문에 일반적으로 O(1)의 시간복잡도를 가진다. 2. 해시 테이블이란? 해시 테이블(Hash table)은 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다. Hash table은 Hash 함수를 사용하여 색인(index, Key)을 버킷(bucke.. 2021. 1. 8. 이전 1 2 3 4 5 6 다음 728x90 반응형
