추가 공부/알고리즘 & 코딩테스트9 [Java] 이진검색(BinarySearch) 이진 검색은 데이터가 키 값으로 이미 정렬되어 있을 때 적용할 수 있는 알고리즘이다. 이진검색의 시간복잡도는 O(log N) 이다. 전체 범위를 탐색하는 선형 검색과 달리 검색 범위를 1/2로 줄여가면서 찾아가는 방법이다. 아래와 같이 7개의 요소를 가지는 배열에서 값이 23인 요소의 인덱스를 찾는 과정을 살펴보자. 1. 먼저 중앙값을 검색한다. 2. 중앙값과 타겟값을 비교한다. 중앙값인 15가 타겟인 23보다 작으므로 값이 작은 왼쪽 부분은 탐색하지 않고 오른쪽 부분만 탐색한다. 만약 타겟이 15였다면 더 이상 검색을 하지 않고 종료되었을 것이다. 이처럼 크기 비교 결과에 따라 검색 범위가 달라지므로 이미 정렬되어 있는 대상에만 적용할 수 있다. 3. 타겟을 찾을때까지 1과 2의 과정을 반복한다. 위 .. 2023. 4. 19. [JAVA] 버블정렬(Bubble Sort) 개념과 코드 구현 버블정렬(Bubble Sort)이란 이웃한 두 요소의 대소관계를 비교해서 교환을 반복하는 정렬 알고리즘이다. 시간 복잡도가 느리지만 코드가 단순하다. 구분 최악 시간복잡도 최선 시간복잡도 평균 시간복잡도 공간복잡도(메모리) 안정성 버블정렬 O(n^2) O(n^2) O(n^2) O(1) Y 알고리즘 1. 배열의 첫번째 원소부터 비교를 시작한다. 2. 현재 원소와 다음 요소의 크기를 비교한다. 3. 현재 요소가 다음 원소보다 크다면 두 원소를 교환한다. 4. 이 과정을 배열의 끝까지 반복한다. 5. 배열의 첫번째 자리에서 부터 [마지막 원소 - (반복횟수)] 자리까지 반복한다. 6. 정렬하는 과정을 배열의 길이 -1 번 반복하면 모든 원소가 정렬된다. 소스코드(Ver 1) public static int[].. 2023. 4. 17. [JAVA] 힙정렬(Heap Sort) 개념과 코드 구현 힙정렬(Heap Sort)이란 힙(Heap) 자료구조를 이용한 정렬 알고리즘이다. 보통 내림차순으로 정렬할 때 최대힙을 사용하고, 오름차순으로 정렬할 때 최소힙을 사용한다. 구분 최악 시간복잡도 최선 시간복잡도 평균 시간복잡도 공간복잡도(메모리) 안정성 힙정렬 O(n log n) O(n log n) O(n lon n) O(1) N * 힙(Heap) 힙은 완전 이진트리의 일종으로 최댓값 혹은 최솟값을 빠르게 찾기 위한 자료구조이다. 최대힙(Max Heap)과 최소힙(Min Heap)으로 나뉜다. 최대힙은 '부모의 값이 자식의 값보다 항상 크다'는 조건을 만족하는 완전 이진트리이며 최소힙은 반대로 '부모의 값이 자식보다 항상 작다'는 조건을 만족하는 완전 이진트리이다. 부모 자식간의 관계는 일정하지만 형제 .. 2023. 4. 17. [JAVA] 기수정렬(Radix Sort) 개념과 코드 구현 기수(자릿수)별로 비교 없이 수행하는 정렬 알고리즘이다. 기수에 따라 원소를 버킷에 집어넣기때문에 비교 연산이 불필요하다. 해당 과정을 일의자리부터 가장 큰 자릿수까지 반복하면서 정렬한다. 각 자릿값에 대해 계수정렬을 수행한다. 데이터 크기에 비례하여 추가적인 메모리 공간이 많이 필요하다는 단점이 있다. 구 분 최악 시간복잡도 최선 시간복잡도 평균 시간복잡도 공간복잡도(메모리) 안정성 기수정렬 O(d *(n+k)) O(d*(n+k)) O(d*(n+k)) O(n+k) Y * d: 가장 큰 자릿수의 수, n: 데이터의 개수, k: 버킷의 개수 알고리즘 1. 정렬할 데이터 중 가장 큰 자릿수를 구한다. 2. 데이터의 일의 자리부터 가장 큰 자릿수까지 자릿수 별로 정렬을 수행한다. 3. 각 자릿수 별로 정렬하기.. 2023. 4. 17. [JAVA] 계수정렬(Counting Sort) 개념과 코드 구현 계수정렬(Counting Sort)은 정수 정렬 알고리즘의 하나로 각 숫자(키)가 몇번 등장했는지 계수(카운팅)해서 각 키값의 위치를 정하는 알고리즘이다. 배열의 값의 범위가 제한되어있을때 효율으로 작동하지만, 입력값의 범위가 크면 카운트 배열이 커지므로 메모리 문제가 생길 수 있다. 구분 최악 시간복잡도 최선 시간복잡도 평균 시간복잡도 공간복잡도(메모리) 안정성 계수정렬 O(n + k) O(n + k) O(n + k) O(n + k) Y * n: 정렬할 배열 길이, k: 정수의 범위 알고리즘 1. 입력 배열의 최댓값과 최솟값을 구한다. 2. 최솟값부터 최댓값까지의 범위를 가지는 배열을 만든다. (카운트 배열) 3. 배열의 각 요소들이 몇번 등장하는지를 카운트 배열에 저장한다. 4. 카운트 배열의 누적합.. 2023. 4. 17. [JAVA] 삽입정렬(Insertion Sort) 개념과 코드 구현 삽입정렬(Insertion Sort)은 배열의 각 요소를 자기보다 앞쪽에 위치한 정렬된 배열과 비교하여 올바른 위치에 삽입하는 알고리즘이다. 배열이 길어질수록 효율이 떨어지지만 구현이 간단하다는 장점이 있다. 비교정렬이며 안정 정렬이다. 구분 최악 시간복잡도 최선 시간복잡도 평균 시간복잡도 공간복잡도(메모리) 안정성 삽입정렬 O(N^2) O(N) O(N^2) 1 Y 알고리즘 1. 요소를 하나씩 순회하면서 알맞은 곳에 삽입하는 형태로 정렬을 수행한다. 2. 마지막 요소까지 검토가 완료되면 전체 정렬이 완료된다. 소스코드 public static int[] insertionSort(int[] arr) { // 배열에서 요소를 순회하면서 자기보다 앞에 있는 배열(앞부분은 정렬이 완료되어있음)에서 알맞은 위치에.. 2023. 4. 17. 이전 1 2 다음
