본문 바로가기

Basic Computer Science18

17. 정렬(Sort) - 퀵 정렬(Quick Sort) 1. Quick Sort 개념 리스트에서 Pivot 값을 정하고 Pivot을 기준으로 나머지 값들의 크기를 비교하여 왼쪽과 오른쪽을 나눈다. 나눠진 리스트에서 다시 Pivot을 정하고 반복하여 정렬한다. 분할 정복 (Divide and Conquer) 알고리즘 - 재귀함수 사용 시간 복잡도 O(NlogN)으로 Merge Sort와 같으나 Locality of reference에 의해 실제로는 더 빠르다. (메인 메모리에 접근하지 않고 캐쉬에서 데이터를 불러오도록 유도한다) 최악의 시나리오 일 때 시간복잡도는 O(N2)으로 정렬된 리스트에서 가장 양끝에서 Pivot값이 정해질 때이다. 추가적인 메모리 공간을 사용하지 않는다. 불안정 정렬 Pivot값은 규칙을 정하기 나름인데 인덱스 가운데 값으로 설정하여 .. 2023. 9. 2.
16. 정렬(Sort) - 합병정렬(Merge Sort) 1. Merge Sort 개념 하나의 리스트를 두 개의 균등한 크기의 리스트로 분할하고(서브리스트의 크기가 1이 될때까지), 부분 리스트를 합치면서 정렬하여 전체가 정렬되도록 함. 분할 정복 (Divide and Conquer) 알고리즘 - 재귀함수 사용 분할 합병 시간복잡도 O(NlogN) 2. Merge Sort 구현 - JAVA In-place 방식 구현 package sort; public class MergeSort implements ISort { // 안정 정렬 @Override public void sort(int[] arr) { mergeSort(arr, 0, arr.length - 1); } //mergesort 배열 초기화 // 분할 private void mergeSort(int[].. 2023. 8. 24.
15. 정렬(Sort) - 삽입정렬(Insert Sort) 1. Insert Sort 개념 리스트의 앞에서부터 이미 정렬된 서브 리스트의 값들과 비교하여 자신의 위치에 값을 삽입한다. 단순한 알고리즘 시간복잡도 O(n^2) 안정 정렬 데이터의 이동이 많음 2. Insert Sort 구현 - JAVA package sort; public class InsertionSort implements ISort { @Override public void sort(int[] arr) { int n = arr.length; for (int i = 1; i = 0 && arr[j] > key) { // key 값보다 .. 2023. 8. 23.
14. 정렬(Sort) - 버블정렬(Bubble Sort) 0. 정렬의 특징 시간복잡도 안정(Stable) 정렬 VS 불안정(Unstable) 정렬 중복된 값의 순서를 보장하느냐 안하느냐의 여부 In-place 정렬 VS Out-of-place 구현방식에 따라서 원본 데이터 내에서 정렬하는가 아니면 정렬된 새로운 배열을 만드는가 1. Bubble Sort 개념 앞에서부터 비교연산을 수행하여 큰 값을 오른쪽에 위치시키는 비교연산을 수행 후 한 칸씩 옮겨가며 반복한다. 한 사이클이 돌면 배열 내에 가장 큰 값이 오른쪽에 위치하고 종료된다. 이러한 사이클을 (배열의 크기 - 1) 만큼 수행해주면 정렬이 완료된다. 직관적이고 단순한 알고리즘 / 느리고 비효율적 시간 복잡도 O(N^2) 안정정렬 In-place 정렬 2. Bubble Sort 구현 - JAVA packa.. 2023. 8. 23.
13. 정렬(Sort) - 이진탐색(Binary Search) 1. 이진탐색(Binary Search)의 개념 오름차순 정렬되어 있는 리스트 내에서 특정 값의 인덱스를 찾는 알고리즘 O(N)의 시간복잡도에 비하여 빠른 속도를 가지는 시간복잡도 O(logN) 그러나, 정렬된 리스트에서만 사용이 가능하다. 2. 이진탐색(Binary Search) 구현 - JAVA package sort; public class BinarySearch { public int search(int[] arr, int target) { // 정렬된 리스트 , 타겟 데이터를 받는다. // 1. 데이터의 중간 인덱스 값을 찾는다. // 2. 중간 인덱스 위치를 기준으로 arr을 절반으로 나눈다. // 3. 나눠진 절반의 리스트에서 target 값을 찾는다. int l = 0; // 리스트의 가장.. 2023. 8. 3.
12. 해시 - 알고리즘 문제 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에.. 2023. 8. 2.

티스토리툴바