Java10 [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. 문자열을 요소로 갖는 배열의 가장 긴 글자, 작은 글자 제거하기 문제 자체는 아주 간단했는데, 처음 풀이 방향을 잡을때 놓친 부분때문에 한참을 헤맨 문제이다. String 타입의 요소를 갖는 배열에서 가장 길이가 짧은 문자열과 가장 길이가 긴 문자열을 제거한 배열을 리턴하는 메서드를 작성하는 문제였다. List를 사용한 방법과 arraycopy를 사용한 방법 두가지로 작성했는데, 동일한 부분을 놓쳐서 정답이 맞기도/틀리기도한 결과를 계속 냈다. public static String[] removeExtremes(String[] arr) { // --------------------------- 1안 --------------------------- if (arr.length == 0) return null; int[] lengths = new int[arr.lengt.. 2023. 3. 21. 이전 1 2 다음
