태화의 일기장

1. 문제 번호 2751

2. 문제 풀이

한줄 평가

•   퀵 정렬(Quick Sort) : 대규모 데이터의 경우 적절하며 분할정복법을 사용하여 피벗인덱스를 활용
•   병합 정렬(Merge Sort) : 분할 정복법을 이용하여 반씩 쪼개어 나중에 정렬한다. O(N logN)을 보장

문제를 먼저 정확히 파악

나의 문제풀이 방식 및 순서

 * 나의 다양한 학습이 우선이기 때문에 다양한 방법을 생각 *

문제를 틀리시는 모든 분들은 아마 이러한 이유일 듯 합니다.

1. 출력의 시간도 고려 필요

예시 - > 3 7 8 1 5 9 7 10 2 4 

1. 분할 작업 시작 
   1. 왼쪽 [ 3 7 8 1 5 ] 오른쪽 [ 9 7 10 2 4 ]
2. 재귀적 분할 및 정렬
   1. 왼쪽
      1. [ 3 7 8 ] 과 [ 1 5 ] 나눈다.
      2. [ 3 ] [ 7 8 ] 로 나눈다.
      3. [ 7 8 ]로 나눈다.
         
         
      4. [ 3 7 8 ] 로 병합된다.
      5. [ 1 5 ]로 병합된다.
      6. [ 1 3 5 7 8 ] 병합
   2. 오른쪽
      1. [ 9 7 10 ] 과 [ 2 4 ] 나눈다.
      2. [ 9 ] [ 7 10 ]으로 나눈다.
      3. [ 7 10 ] 으로 나눈다.
      4. [ 2 4 ]로 나눈다.
         
      5. [ 7 9 10 ] 으로 병합한다.
      6. [ 2 4 ] 로 병합한다.
      7. [ 2 4 7 9 10 ] 으로 병합한다
3. 최종 병합
   1. [ 1 3 5 7 8 ] 과 [ 2 4 7 9 10 ]을 병합하여 [ 1 2 3 4 5 6 7 7 8 9 10 ]이 된다.

3. 소스 인증

import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());

        int [] numAry = new int[N];
        int [] newAry = new int[N];  // 정렬된 배열을 저장할 임시 배열

        for(int i = 0; i < N; i++){
            numAry[i] = Integer.parseInt(br.readLine());
        }

        mergeSort(numAry, newAry, 0, N - 1);

        StringBuilder st = new StringBuilder();
        for(int i : numAry){
            st.append(i).append("\n");
        }
        bw.write(st.toString());
        bw.flush();
        bw.close();
        br.close();
    }

    /**
     * 두 개의 하위 배열을 병합하는 메소드
     * @param a 원본 배열
     * @param newAry 임시 배열
     * @param m 시작 인덱스
     * @param middle 중간 인덱스
     * @param n 끝 인덱스
     */
    public static void merge(int [] a, int [] newAry, int m, int middle, int n){
        /*numAry = {5, 7, 4, 2} 일때 
          i group = {5 ,7}
          j group = {4, 2}
          k group = {5,7,2,4}
        */
        int i = m;
        int j = middle + 1;
        int k = m;

        // 작은 순서대로 배열에 삽입
        while(i <= middle && j <= n){
            if(a[i] <= a[j]){
                newAry[k] = a[i];
                i++;
            } else {
                newAry[k] = a[j];
                j++;
            }
            k++;
        }

        // 남은 데이터 삽입
        if(i > middle){
            for(int t = j; t <= n; t++){
                newAry[k] = a[t];
                k++;
            }
        } else {
            for(int t = i; t <= middle; t++){
                newAry[k] = a[t];
                k++;
            }
        }

        // 정렬된 배열을 원본 배열에 삽입
        for(int t = m; t <= n; t++){
            a[t] = newAry[t];
        }
    }

    /**
     * 병합 정렬 메소드
     * @param a 원본 배열
     * @param newAry 임시 배열
     * @param m 시작 인덱스
     * @param n 끝 인덱스
     */
    public static void mergeSort(int a[], int newAry[], int m, int n){
        if(m < n){
            int middle = (m + n) / 2;
            mergeSort(a, newAry, m, middle);
            mergeSort(a, newAry, middle + 1, n);
            merge(a, newAry, m, middle, n);
        }
    }
}

- 실패 소스코드 -

4.추가 개념

1. 알고리즘 개요:

•  분할: 배열을 반으로 나누어 더 이상 나눌 수 없을 때까지 반복합니다.
•   정렬 및 병합: 분할된 배열을 정렬하면서 병합합니다.

2. 작동 방식:

• 분할: 배열을 반으로 나누어 더 이상 나눌 수 없을 때까지 반복합니다.
  • 예: [3, 7, 8, 1, 5, 9, 7, 10, 2, 4] → [3, 7, 8, 1, 5], [9, 7, 10, 2, 4]
• 정렬 및 병합: 분할된 배열을 정렬하면서 병합합니다.
  • 예: [3, 7, 8, 1, 5]는 [3, 7, 8]과 [1, 5]로 나누어지고 각각 정렬 후 병합하여 [1, 3, 5, 7, 8]이 됩니다.
  • 같은 방식으로 [9, 7, 10, 2, 4]은 [2, 4, 7, 9, 10]으로 정렬됩니다.
  • 최종적으로 [1, 3, 5, 7, 8]과 [2, 4, 7, 9, 10]을 병합하여 [1, 2, 3, 4, 5, 7, 7, 8, 9, 10]이 됩니다.

3. 시간 복잡도:

• 평균: O(N log₂N)
• 최악: O(N log₂N)
• O(N log₂N)을 보장하는 알고리즘

4. 공간 복잡도:

• O(N) (추가적인 배열 공간 필요)

5. 특징:

• 안정성: 안정 정렬 (같은 값의 원소가 순서를 유지함)

1. 빅 오 표기법 개요:

• 데이터 원소 N개에 대한 알고리즘 단계 수 
  • O(1), O(2), O(3), O(4) 는 모두 데이터 원소가 증가하더라도 1,2,3,4 단계로 고정된 알고리즘 유형
• 데이터가 늘어날 때 단계 수가 어떻게 증가하는가?
  • O(N)은 데이터 원소가 증가할 때 단계 수가 비례(N개) 로 증가하는 알고리즘 유형
• 최악의 시나리오

2. 로그 log :

• 2를 몇 번 곱해야 N이 나올까? = log₂N
  
  • 2를 3번 곱하면 8이 나온다. log₂8 = 3
• 1이 될 때까지 N을 2로 몇 번 곱해야 할까? = log₂N

3. O(logN) == O(log₂N)

• 데이터가 두 배로 증가할 때마다 한 단계씩 증가하는 알고리즘
• 데이터 원소 N개가 있을때 알고리즘에서는 log₂단계가 걸린다.
  • 8개의 원소가 있을때 log₂8 는 3번의 단계를 거쳐야 한다. 

5. 참조 블로그

불편함을 느끼실 경우 연락 주시면 곧 바로 삭제하도록 하겠습니다.

https://youtu.be/O-O-90zX-U4?si=xzvKx12A-w_10F8u

https://velog.io/@on-n-on-turtle/%EB%88%84%EA%B5%AC%EB%82%98-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%99%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B9%85%EC%98%A4%ED%91%9C%EA%B8%B0%EB%B2%95