신뇽이 되어보자

퀵정렬이란?하나의 리스트를 피벗(pivot)을 기준으로 두 개의 부분리스트로 나누어 하나는 피벗보다 작은 값들의 부분리스트, 다른 하나는 피벗보다 큰 값들의 부분리스트로 정렬한 다음, 각 부분리스트에 대해 다시 위 처럼 재귀적으로 수행하여 정렬하는 방법입니다. 구현 방법 3가지 중간 피봇(Median-of-three pivot):장점: 배열의 처음, 중간, 끝 요소 중 중간값(median)을 피봇으로 선택하여 최악의 경우 시간복잡도를 줄일 수 있습니다.단점: 추가적인 계산이 필요하고 구현이 다소 복잡할 수 있습니다.왼쪽 피봇(Leftmost pivot):장점: 구현이 간단하고 메모리 사용이 적습니다.단점: 이미 정렬된 배열이나 역으로 정렬된 배열에서 최악의 성능을 보일 수 있습니다. 오른쪽 피봇(Righ..

안녕하세요. 신뇽이 되고싶은 미뇽입니다!오늘은 1920번 수 찾기를 풀어보겠습니다!문제를 보고 생각한 해결 흐름제한 시간이 1초이고  중앙 피봇 퀵소트로 정렬 + 이분 탐색으로 값 존재 여부 찾기 구현 전역 변수 Main 함수배열에 값을 모두 넣어줍니다. 그런다음 퀵소트 함수를 호출해줍니다. 퀵정렬 함수  중앙값을 피봇으로 한 퀵정렬 코드입니다!private static void quick_sort(int[] arr, int lo, int hi) { if (lo >= hi) { return; } int pivot = partition(arr, lo, hi); quick_sort(arr, lo, pivot); quick_sort(arr, pivot + 1, hi);}..

왼쪽 피봇으로 구현했더니 41%에서 시간 초과했습니다. 그래서 중간 피봇으로 구했더니 통과했습니다. 무슨 차이가 있나했더니 중간 피봇(Median-of-three pivot): 장점: 배열의 처음, 중간, 끝 요소 중 중간값(median)을 피봇으로 선택하여 최악의 경우 시간복잡도를 줄일 수 있음. 단점: 추가적인 계산이 필요하고 구현이 다소 복잡할 수 있음.왼쪽 피봇(Leftmost pivot): 장점: 구현이 간단하고 메모리 사용이 적음. 단점: 이미 정렬된 배열이나 역으로 정렬된 배열에서 최악의 성능을 보일 수 있음. 오른쪽 피봇(Rightmost pivot): 장점: 구현이 간단하고 왼쪽 피봇과 마찬가지로 메모리 사용이 적음. 단점: 이미 정렬된 배열이나 역으로 정렬된 배열에서 최악의 성능을 보일..

안녕하세요. 신뇽이 되고싶은 미뇽입니다!오늘은 정렬 알고리즘 중 거품 정렬에 대해 알아보도록 하겠습니다! 거품 정렬- 두개의 인접한 원소를 비교하여 정렬하는 방식입니다.- 비교정렬이며, 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않기 때문에 제자리 정렬입니다.  정렬 방법1. 앞에서부터 현재 원소와 바로 다음의 원소를 비교합니다.2. 현재 원소가 다음 원소보다 크면 원소를 교환합니다.3. 다음 원소로 이동하여 해당 원소와 그 다음원소를 비교합니다.  이 때, 각 라운드를 진행 할 때마다 뒤에서부터 한 개씩 정렬되기 때문에, 한번씩 줄면서 비교하게 됩니다.  구현public class Bubble_Sort { public static void bubble_sort(int[] a) { ..

안녕하세요. 신뇽이 되고싶은 미뇽입니다!오늘은 정렬 알고리즘 중 삽입 정렬에 대해 알아보도록 하겠습니다! 들어가기에 앞서 앞으로의 정렬은 모두오름차 순으로 정렬한다고 가정하겠습니다삽입 정렬- 데이터를 비교하면서 찾기 때문에 비교 정렬입니다.- 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로하지 않기 때문에 제자리 정렬입니다.- 안정 정렬입니다.정렬 방법1. 현재 타겟이 되는 숫자와 이전 위치에 있는 원소들을 비교합니다.2. 타겟이 되는 숫자가 이전 위치에 있던 원소보다 작다면 위치를 서로 교환합니다.3. 그 다음 타겟을 찾아 위와 같은 방법으로 반복합니다. 첫 번째 원소는 타겟이 되어도 비교할 원소가 없기 때문에 처음 원소부터 타겟이 될 필요가 없고 두번째 원소부터 타겟이 됩니다.  public ..

안녕하세요. 신뇽이 되고싶은 미뇽입니다!오늘은 정렬 알고리즘 중 선택 정렬에 대해 알아보도록 하겠습니다! 들어가기에 앞서 앞으로의 정렬은 모두오름차 순으로 정렬한다고 가정하겠습니다.선택 정렬(Selection Sort)- 입력 배열(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 제자리 정렬 알고리즘입니다. - 현재 위치에 들어갈 값을 찾아 정렬하는 배열입니다. 정렬 방법1. 주어진 배열 중에서 최솟값을 찾습니다.2. 그 값을 맨 앞에 위치한 값과 교체합니다.3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체합니다.4. 하나의 원소만 남을 때까지 위의 1~3 과정을 반복합니다. 예제배열에 9,6,7,3,5가 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 봅시다 1회전:첫 번째..