본문 바로가기

Computer Science/Algorithm

 (6)
이진 탐색(Binary Search) 탐색할 크기를 절반씩 줄여나가며 값을 탐색해나가는 알고리즘 1. 전체 배열의 중간값을 기준으로 앞 뒤를 나눈다. 2. 탐색하는 값이 중간값보다 크다면 뒤의 배열에서 다시 중간값을 나누고 탐색 3. 탐색하는 값이 중간값보다 작다면 앞의 배열에서 다시 중간값을 나누고 탐색 시간복잡도 매번 절반씩 나눠가며 탐색하므로 O(logn) 공간복잡도 O(logn) Code 반복문 class Main { public static void main(String[] args) { int[] data = {7,9,10,14,17,19,26}; int idx = binarySearch(data, 14); System.out.println("idx " + idx); } public static int binarySearch(in..
계수정렬(Counting Sort) 각 숫자가 몇번 나오는지 count를 한 후 앞 순서대로 차례대로 다시 내보내 정렬 시키는 정렬 알고리즘 0. [3,4,0,1,2,4,2,4], [개수를 count한 후 저장할 공간] 1. 개수를 저장할 공간을 0으로 초기화 시켜준다. 배열의 크기는 데이터 배열의 최대값 [3,4,0,1,2,4,2,4], [0,0,0,0,0] // 2. 처음부터 개수를 세어 저장합니다. 0은 1개, 1은 1개, 2는 2개, 3은 1개, 4는 3개 [3,4,0,1,2,4,2,4], [1,1,2,1,3] 3. 개수를 저장한 것을 누적합시킨다. [3,4,0,1,2,4,2,4], [1,2,4,5,8] 4. 누적합을 바탕으로 숫자를 결과에 넣어줌. 0은 1에, 1은 2에, 2는 3~4에 3은 5에, 4는 6~8에 넣어준다. 결과 ..
기수정렬(Radix Sort) 1,10,100... 등 각 자리수를 기준으로 비교없이 정렬을 수행하는 정렬 알고리즘 각 원소들 중 최대 자리수를 구한다. [1,2,3,10,157] 이라면 157, 세자릿수인 3이 최대 자리수가 된다. 0 ~ 9까지의 Queue를 만든다. 각 원소별 자리수의 숫자를 해당하는 번호의 Queue에 집어 넣는다. 0 ~ 9 까지의 Queue를 순회하며 원소를 뽑아 기존 배열에 교체해준다. 최대 자리수만큼 2 ~ 4를 반복해준다. 시간복잡도 최대자릿수 d만큼 반복하며 원소의 개수 n만큼 돌게 되므로 O(dn) 이므로 O(n)의 시간복잡도를 가지게 된다. 공간복잡도 기존원소 배열 크기 n에 추가적으로 자리수 Queue배열이 추가되므로 O(n) 왜 잘 안쓰지? 시간복잡도 O(n)이라는 빠른 속도를 가지고 있는데 ..
병합정렬(Merge Sort) 데이터 집합을 절반으로 쪼개어 나간 뒤 쪼개진 부분집합들을 다시 정렬된 형태로 합치는 방식의 분할정복 정렬 https://ko.wikipedia.org/wiki/합병_정렬 시간 복잡도 데이터를 균등하게 절반씩 쪼개나가기에 총 n개의 데이터가 logn 단계만큼의 연산을 수행하므로 O(NLogN)이 된다. 공간 복잡도 데이터를 정렬함에 있어 추가적인 데이터 리스트 공간이 필요하기 때문에 O(n)의 공간 복잡도를 가지지만 다른 정렬보다 n만큼의 메모리를 더 차지하게 된다. Code public class MergeSort { public static void mergeSort(int[] data) { if (data.length < 2) { return; } int mid = data.length / 2; i..
퀵정렬(Quick Sort) 분할정복 기반의 정렬 정렬방법 데이터 집합에서 기준점이 될 피벗 값 선정 피벗을 기준으로 피벗보다 작은 값을 왼쪽, 큰 값을 오른쪽으로 2개의 부분 집합을 만들어냄 왼쪽, 오른쪽 각각의 부분집합에서 앞선 1,2번 반복 부분집합내 데이터가 1이 될때까지 반복한다. 시간복잡도 최선 : NLogN 재귀 호출이 일어날 때 마다 부분 리스트의 크기가 절반씩 줄어들게 되므로 n개의 원소에 대해 logN만큼 연산을 하기때문에 시간복잡도는 NLogN이 된다. 최악 : n^2 피벗 선택이 항상 데이터 집합의 최소값을 선정했다고 가정한다면 부분집합의 크기가 절반씩 줄어드는 것이 아닌 n n-1 n-2 ... 로 줄어드므로 n번의 연산을 거치게 되면 O(n^2)이 되게 된다. 공간복잡도 정렬을 함에 있어 분할된 데이터 공간..
삽입정렬, 선택정렬, 버블정렬 버블정렬 인접한 숫자끼리 대소 비교를 통해 큰 수를 뒤로 이동시키는 방식의 정렬 # 시간복잡도 n-1, n-2 .... 1까지 총 n(n-1)/2번의 결과가 나오므로 O(n^2)의 시간복잡도를 가지게 된다. # 공간복잡도 다른 공간을 활용하지 않고 현재 데이터 내에서 자리를 switch하는 것이기에 O(n)의 공간복잡도를 가지게 된다. # Code 1. python 1 2 3 4 5 6 def bubbleSort(data): for i in range(len(data)-1): for j in range(len(data)-1-i): if data[j] > data[j+1]: data[j], data[j+1] = data[j+1], data[j] return data Colored by Color Scrip..

티스토리툴바