Language
-
[JAVA/자료구조] 합병 정렬(Merge Sort)Language/Java 2021. 6. 13. 18:40
평균 수행 시간이 O(logN)인 알고리즘 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort), 힙 정렬(Heap Sort) 한번 수행될때 마다 정렬되어야 하는 수의 범위가 1/2로 줄어드는 경우 사용한다. 퀵 정렬 이외의 다른 알고리즘은 추가적인 메모리가 필요하다. 합병 정렬(Merge Sort) 비교 기반 정렬 알고리즘 분할(divide): 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 정복(conquer): 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 결합(combine): 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다 이때 정렬 결과가 임시 배열에 저장된다. 복사(copy): 임시 배열에 저장된 결과를 원래 배열에 복사한다. 합병..
-
[JAVA/자료구조] 퀵 정렬(Quick Sort)Language/Java 2021. 6. 13. 17:27
평균 수행 시간이 O(logN)인 알고리즘 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort), 힙 정렬(Heap Sort) 한번 수행될때 마다 정렬되어야 하는 수의 범위가 1/2로 줄어드는 경우 사용한다. 퀵 정렬 이외의 다른 알고리즘은 추가적인 메모리가 필요하다. 퀵 정렬(Quick Sort) 퀵 정렬은 n개의 데이터를 정렬할 때 최악의 경우 O(n^2)번의 비교를 수행하고, 평균적으로 O(logN)번의 비교를 수행한다. 퀵 정렬은 찰스 앤터니 리처드호어가 개발한 정렬 알고리즘이다. 원소들 중에 같은 값이 있는 경우 같은 값들의 정렬 이후 순서가 초기 순서와 달라질 수 있기 때문에 불안정 정렬에 속한다. 퀵 정렬(Quick Sort) 구현 퀵 정렬은 분할 정복 방법을 통해 리스트를 정렬한..
-
[JAVA/자료구조] 힙 정렬(Heap Sort)Language/Java 2021. 6. 13. 00:09
평균 수행 시간이 O(logN)인 알고리즘 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort), 힙 정렬(Heap Sort) 한번 수행될때 마다 정렬되어야 하는 수의 범위가 1/2로 줄어드는 경우 사용한다. 퀵 정렬 이외의 다른 알고리즘은 추가적인 메모리가 필요하다. 힙 정렬(Heap Sort) 최대 힙 트리나, 최소 힙 트리를 구성해 정렬을 하는 방법 내림차순 정렬을 위해서 최대 힙을 구성하고, 오름차순 정렬을 위해서 최소힙을 구성한다. 이진 트리를 최대 힙으로 만들기 위해 최대 힙으로 재구성 하는 과정이 트리의 깊이 만큼 이루어지므로 시간 복잡도는 O(log n)이 걸린다. 힙 정렬(Heap Sort) 구현 n개의 노드에 대한 완전 이진 트리를 구성한다. 이때 루트 노드부터 부모노드, 왼..
-
[JAVA/자료구조] 선택 정렬(Selection Sort)Language/Java 2021. 6. 12. 23:11
평군 수행 시간 O(n^2) 알고리즘 버블 정렬(Bubble Sort) 삽입 정렬(Insertion Sort) 선택 정렬(Selection Sort) 각 요소가 다른 요소와 평균 한번 이상 씩 비교를 하여 정렬된다. 선택 정렬(Selection Sort) 제자리 정렬 알고리즘 중 하나이다. 1. 주어진 리스트 중 최솟값을 찾는다. 2. 그 값을 맨 앞에 위치한 값과 교체한다. 3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 시간 복잡도는 O(n^2)으로 느리지만, 메모리가 제한적인 경우 성능상의 이점이 존재한다. 선택 정렬(Selection Sort) 구현 선택 정렬(Selection Sort) 구현 결과 반복 - 1 10 50 70 80 60 20 40 30 반복 - 2 10 20 7..
-
[JAVA/자료구조] 버블 정렬(Bubble Sort)Language/Java 2021. 6. 12. 22:22
평군 수행 시간 O(n^2) 알고리즘 버블 정렬(Bubble Sort) 삽입 정렬(Insertion Sort) 선택 정렬(Selection Sort) 각 요소가 다른 요소와 평균 한번 이상 씩 비교를 하여 정렬된다. 버블 정렬(Bubble Sort) 두 인접한 원소를 검사하여 정렬하는 방법 시간 복잡도가 O(n^2)으로 느리지만, 코드가 단순하여 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기때문에 지어진 이름이다. 버블 정렬(Bubble Sort) 구현
-
[JAVA/자료구조] 삽입 정렬(Insertion Sort)Language/Java 2021. 6. 12. 00:22
평군 수행 시간 O(n^2) 알고리즘 버블 정렬(Bubble Sort) 삽입 정렬(Insertion Sort) 선택 정렬(Selection Sort) 각 요소가 다른 요소와 평균 한번 이상 씩 비교를 하여 정렬된다. 삽입 정렬(Insertion Sort) 삽입 정렬: 이미 정렬된 상태의 요소에 새로운 요소를 추가할 때 정렬하여 추가하는 개념 => ex) 카드게임 두번째 요소부터 이전 요소들과 비교하며 insert될 위치를 찾아가며 정렬하는 알고리즘 삽입 정렬(Insertion Sort) 구현
-
[JAVA] 제네릭(Generic) 프로그래밍Language/Java 2021. 6. 10. 00:13
제네릭(Generic) 자료형 클래스에서 사용하는 변수의 자료형이 여러 개 일 수 있고, 그 메서드는 동일한 경우 클래스의 자료형을 특정하지 않고 추후 해당 클래스를 사용할 때 지정할 수 있도록 선언하는 방식이다. 실제 사용되는 자료형의 변환은 컴파일러에 의해 검증되기 때문에 안정적인 프로그래밍 방식이다. 컬렉션 프레임 워크에서 많이 사용되고 있다. 제네릭 프로그래밍 예 자료형 매개변수 T(type parameter): 해당 클래스를 사용하는 시점에 실제 사용할 자료형을 지정, static 변수는 사용할 수 없다. GenericPrinter: 제네릭 자료형 E: element, K: key, V: value등 여러 알파벳을 의미에 따라 사용할 수 있다. 다이아몬드 연산자 를 다이아몬드 연산자라고 칭한다...