본문 바로가기

전체 글192

[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.
[JAVA] 퀵정렬(Quick Sort) 개념과 코드 구현 퀵정렬(Quick Sort)은 가장 빠른 정렬 알고리즘 중 하나로 사용되는 정렬 알고리즘이다. 다른 원소와 비교만으로 정렬을 수행하는 비교정렬이다. 값의 정렬이후 순서가 초기 순서와 달라질 수 있는 불안정 정렬이고, 분할 정복 알고리즘에 속한다. 구분 최악 시간복잡도 최선 시간복잡도 평균 시간복잡도 공간복잡도(메모리) 안정성 퀵정렬 O(N^2) O(n log n) O(n log n) 평균적으로 O(log n), 최악의 경우 O(n) N 알고리즘 리스트 가운데에서 하나의 원소를 고른다. 이 원소를 피벗(Pivot)이라고 한다. 피벗 앞에는 피벗보다 작은 모든 원소가 오고 피벗 뒤에는 피벗보다 큰 모든 원소가 오도록 리스트를 둘로 나눈다. 분할된 각 리스트에 대해 피벗 설정과 그룹 나눔을 반복하여 모든 그룹.. 2023. 4. 17.
[JAVA] 병합정렬(Merge Sort) 개념과 코드 구현 병합 정렬(Merge Sort)은 비교 기반 정렬 알고리즘이다. 문제를 작은 여러 문제로 쪼개서 각각을 해결하고 결과를 모아서 원래 문제를 해결하는 방법이다. 안정 정렬이며 분할 정복 알고리즘의 하나이다. 안정 정렬: 반복되는 요소를 입력때와 동일한 순서로 정렬 시키는 정렬(중복된 부분은 순서가 유지되는 정렬) 분할 정복 알고리즘: 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법. 보통 재귀함수를 통해 구현된다. 구분 최악 시간복잡도 최선 시간복잡도 평균 시간복잡도 공간복잡도(메모리) 안정성 합병정렬 O(n log n) O(n log n) O(n log n) O(n) Y 알고리즘 N개의 길이를 가진 배열 리스트를 각각 하나의 원소만 포함하는 N개의 부분 리스트로 분할한다. 부분.. 2023. 4. 17.

티스토리툴바