전체 글
-
[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/Level2] 정렬된 수에서 하나의 수 위치 찾기Algorithm/프로그래머스 2021. 6. 11. 23:33
문제 설명 여러 개의 수가 정렬된 순서로 있을 때 특정한 수를 찾으세요. 수의 예: [12, 25, 31, 48, 54, 66, 70, 83, 95, 108] 단순 반복문을 이용하면 수의 개수에 따라 비교 횟수가 증가하는 O(n)의 수행이 이루어진다. 수가 정렬된 상태에서 이진 탐색을 활용할 경우 매번 비교되는 요소의 수가 절반으로 감소될 수 있으므로 O(logN)의 수행으로 원하는 수를 찾을 수 있다. 입출력 예 찾고자하는 수의 위치를 찾을 경우 배열 내 인덱스의 값을 출력하세요. 찾고자하는 수가 존재하지 않을 경우 "찾는 숫자가 존재하지 않습니다."를 출력하세요. 풀이 수가 정렬된 상태이므로 중간의 값을 하나 선택하고, 찾으려는 값이 그보다 크면 범위를 오른쪽으로 그보다 작으면 범위를 왼쪽으로 좁히며..
-
[JAVA/Level1] 최솟값과 최댓값Algorithm/프로그래머스 2021. 6. 11. 23:01
문제 설명 여러 개의 수가 배열에 있을 때 그 중 가장 큰 값과 가장 작은 값을 찾는다. 배열의 몇 번째에 있는지 순서를 찾는다. 반복문을 한번만 사용하여 문제를 해결한다. 수의 예 : [10, 55, 23, 2, 79, 101, 16, 82, 30, 45] 풀이 1. 배열 내 인덱스 0에 위치한 값을 maxNumber변수와 minNumber변수에 저장한다. 2. 배열의 크기만큼 반복문을 이용하여 더 큰수나 작은 수가 나올 경우 maxNumber의 값과 minNumber의 값을 변경시켜준다. 3. 변경될 경우 해당 인덱스의 위치를 저장한다. 코드