태화의 일기장

1. 문제 번호 -번

2. 문제 풀이

한줄 평가

• 난 이런게 은근히 어렵다.

문제를 먼저 정확히 파악

• Step1 까지 하면 출력만을 목적 or ArrayList로 동적으로 순서대로 넣어서 완성시킬수 도 있다.
  • Step2부터 하는 것은 배열에 넣기 위함이다.
•  누적 합을 해주는 이유는 이전의 원소와 현재의 원소를 뺴면 갯수가 나오는데 그 갯수만큼이 차지하는 자리 개수이다. (궁금증2)
•  countArray[num]--; 을 하는 부분이 잘 이해가 가지 않았다. (지금도 그렇게 잘 이해는 안간다.) (궁금증3)

나의 문제풀이 방식 및 순서

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

3. 소스 인증

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

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args)throws IOException {
        int[] array = {5, 6, 2, 2, 1, 4};
        int maxValue = Arrays.stream(array).max().getAsInt(); // maxValue = 6
        int[] countArray = new int[maxValue + 1]; 
        int[] sortedArray = new int[array.length];

        // Step 1: Count the occurrences of each value in the input array
        // countArray = [0, 1, 2, 0, 1, 1, 1]
        // 출력만이 목적이면 2번부터는 진행할 필요없이 출력해버리면 된다.
        for (int num : array) {
            countArray[num]++;
        }

        // Step 2: Modify the count array by adding the previous counts
        // countArray = [0, 1, 3, 3, 4, 5, 6] 누적 합을 만들어준다.
        // 1은 1개자리 차지, 3-1=2 는 2개자리 차지, 4-3=1개자리 차지, 5-4=1개자리 차지, 6-5=1개자리 차지
        for (int i = 1; i < countArray.length; i++) {
            countArray[i] += countArray[i - 1];
        }

        // Step 3: Build the sorted array using the count array
        // int[] array = {5, 6, 2, 2, 1, 4}; 맨뒤 index의 value값을
        // countArray = [0, 1, 3, 3, 4, 5, 6]; index 자리에 
        // sortedArray[3] = 4
        // sortedArray[0] = 1
        for (int i = array.length - 1; i >= 5; i--) {
            int num = array[i];
            sortedArray[countArray[num] - 1] = num;
            countArray[num]--;
        }
        for(int i : sortedArray){
            System.out.println(i);
        }
    }
}

- 실패 소스코드 -

4.추가 개념

카운팅 정렬 동작

카운팅(계수) 정렬 수행 과정은 다음의 단계로 이루어진다.

1. 입력 배열의 최댓값, Counting Array 생성
   배열의 각 원소의 최대 값을 구하여 +1을하여 배열을 만든다.
   그 이유는 6까지 만들어야 1 2 3 4 5 6 까지 갯수를 셀 수 있다.
   만약 1,2,2,2,2,2,2 일때는 3자리의 Counting Array를 생성
   
   
2. 입력 배열 원소 개수의 누적합
   1번 과정에서 Counting Array 생성 및 원소 Count를 마쳤다면 이전 좌표의 원소 개수를 더해나가 누적합 배열로 만들어준다.
   난 이부분이 제일 이해가 안됐음
   
   
   
3. 입력 배열과 누적합 배열을 이용한 정렬 수행
   입력 배열의 각 원소에 대해 Counting Array에 조회하여 어느 좌표에 들어가야 하는지 체크한 뒤 조회된 원소의 개수를 1 감소시켜 앞의 좌표로 입력받을 수 있게 한다.
   
   

이제 입력 배열과 동일 크기의 정렬될 배열을 준비한다.

정렬될 값을 넣기 앞서 누적합 배열의 각 원소의 의미는 다음과 같다.

• c1=𝑐1=1 :  𝑏1에서  𝑏1까지 1개 자리 차지
• c2=𝑐2=2 : 𝑏2에서 𝑏3까지 2개 자리 차지
• c3=𝑐3=1 : 𝑏4에서 𝑏4까지 1개 자리 차지
• c4=𝑐4=1 : 𝑏5에서 𝑏5까지 1개 자리 차지
• c5=𝑐5=1 : 𝑏6에서 𝑏6까지 1개 자리 차지

 Counting Array 0,1,3,4,5,6 에 의미를 찾지 말고 아래의 숫자를 보고 의미를 찾아라
  1-0 = 1자리
  3-1 = 2자리

  4-3 = 1자리

  5-4 = 1자리

  6-5 = 1자리

for (int i = 1; i < countArray.length; i++) {
    countArray[i] += countArray[i - 1];
}

입력 배열의 값을 차례대로 순회하여 누적합 배열에 조회하면 해당 원소가 어느 좌표로 가야 하는지 알 수 있고 출력 배열에 삽입 후 Counting Array의 값을 1 감소시켜 앞의 좌표에 넣을 수 있게끔 한다.

여기서 주의깊게 봐야할 Arr 2,2일때 Counting Array가 어떻게 변하는지 보면 나의 궁금증 3이 해결이 된다.

for (int i = array.length - 1; i >= 5; i--) {
    countArray[num]--;
}

for (int i = array.length - 1; i >= 5; i--) {
    int num = array[i];
    sortedArray[countArray[num] - 1] = num;
    countArray[num]--;
}

5. 참조 블로그

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

아래의 블로그를 내용을 아예 베껴왔다. 

필요하시면 아래 블로그가서 자세히 보시기 바랍니다. 

저는 제가 보기 위해서 적는 블로그라서..

https://8iggy.tistory.com/123

1. 문제 번호 1427번

2. 문제 풀이

한줄 평가

•   

문제를 먼저 정확히 파악

나의 문제풀이 방식 및 순서

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

3. 소스 인증

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

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int lengthN = (int)(Math.log10(N)+1);
        List<Integer> newAry = new ArrayList<>();
        

        for(int i = 0; i < lengthN; i++ ){
            newAry.add(N % 10);
            N = N / 10 ;
        }
        // int lengthN = newAry.size();
        Collections.sort(newAry);

        for(int i = lengthN - 1; i >= 0; i--){
            System.out.print(newAry.get(i));
        }
        
    }
}

- 실패 소스코드 -

4.추가 개념

5. 참조 블로그

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

1. 문제 번호 10989

2. 문제 풀이

한줄 평가

•   병합 정렬(Merge Sort) : 분할 정복법을 이용하여 반씩 쪼개어 나중에 정렬한다. O(N logN)을 보장
•  카운팅 정렬/계수 정렬 : 배열에 중복 횟수를 카운팅 해서 한정된 범위에 있을때 가장 효과적이다. O(N)

문제를 먼저 정확히 파악

나의 문제풀이 방식 및 순서

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

3. 소스 인증

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

// The main method must be in a class named "Main".
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()); // 4,2,5,7 
        }
        mergeSort(numAry,newAry, 0, N - 1);

        StringBuilder sb = new StringBuilder();
        for(int i : numAry){
            sb.append(i).append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
    public static void mergeSort(int [] numAry,int [] newAry, int start, int end){
        if (start < end){
            int middle = (start + end) / 2 ;
            mergeSort(numAry, newAry, start, middle);
            mergeSort(numAry, newAry, middle+1, end);
            merge(numAry, newAry, start, middle, end);

            // 첫 번째 호출: mergeSort(numAry, newAry, 0, 3)
            // middle = (0 + 3) / 2 = 1
            // mergeSort(numAry, newAry, 0, 1)
            // mergeSort(numAry, newAry, 2, 3)
            
            // 두 번째 호출: mergeSort(numAry, newAry, 0, 1)
            // middle = (0 + 1) / 2 = 0
            // mergeSort(numAry, newAry, 0, 0) (기저 조건, 리턴)
            // mergeSort(numAry, newAry, 1, 1) (기저 조건, 리턴)
            // merge(numAry, newAry, 0, 0, 1)

            // 세 번째 호출: mergeSort(numAry, newAry, 2, 3)
            // middle = (2 + 3) / 2 = 2
            // 호출: mergeSort(numAry, newAry, 2, 2) (기저 조건, 리턴)
            // 호출: mergeSort(numAry, newAry, 3, 3) (기저 조건, 리턴)
            // 병합: merge(numAry, newAry, 2, 2, 3)


        }
    }
    public static void merge(int [] numAry, int [] newAry, int start, int middle, int end){
        int i = start; //왼쪽 배열 인덱스
        int j = middle + 1; //오른쪽 배열 인덱스
        int k = start; //새배열의 인덱스
        
        //1. i = 0, j = 1, k = 0
        //2. 여기서 4 2를 비교하여 -> newAry[ 2 ], i = 0, j = 2, k = 1
        while(i <= middle && j <= end){
            if(numAry[i] <= numAry[j]){ //작은값을 넣기 위해서
                newAry[k] = numAry[i];
                i++;
            } else { 
                newAry[k] = numAry[j]; //작은값을 넣기 위해서
                j++;
            }
            k++;
        }
        
        // 3. 4를 붙인다. newAry[ 2, 4 ], i = 0, j = 2, k = 2
        // 즉 왼쪽 하위 배열의 모든요소가 newAry가 복사되었으면(i>middle) 오른쪽 하위 배열의 남은 요소들 newAry에 복사 
        if(i > middle){ 
            for(int t = j; t <= end; t++){
                newAry[k] = numAry[t];
                k++;
            }
        } else {
            for(int t = i; t <= middle; t++){
                newAry[k] = numAry[t];
                k++;
            }
        }

        
        // 정렬된 배열을 원본 배열에 삽입 -> 4 2 5 7 에 2 4 를 덮어씌워서 2 4 5 7 로 만들어준다.
        for(int t = start; t <= end; t++){
            numAry[t] = newAry[t];
        }
    }
}

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

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        int cntNumAry[] = new int [10001]; //0~10까지면 총 11개의 숫자 

        while(N > 0){
            cntNumAry[Integer.parseInt(br.readLine())]++;
            N--;
        }
        
        for(int i = 1; i <= 10000; i++){
            while(cntNumAry[i] > 0){
                sb.append(i).append('\n');
                cntNumAry[i]--;
            }
        }
        System.out.print(sb);
    }
}

- 실패 소스코드 -

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번의 단계를 거쳐야 한다. 

출처 : welloff_jj님의 hyeojung.log블로그

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

1. 문제 번호 25305

2. 문제 풀이

한줄 평가

•   퀵 정렬(Quick Sort) : 대규모 데이터의 경우 적절하며 분할정복법을 사용하여 피벗인덱스를 활용

문제를 먼저 정확히 파악

나의 문제풀이 방식 및 순서

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

3. 소스 인증

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

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        int [] numAry = new int[N];
        
        for(int i = 0; i < N; i++){
            numAry[i] = Integer.parseInt(st2.nextToken());
        }

        quickSort(numAry, 0, N -1 );
        
        System.out.println(numAry[N - (k)]);

        
    }
    public static void quickSort(int [] numAry, int start, int end){
        if(start >= end){
            return;
        }
        
        int key = numAry[start];
        int i = start + 1;
        int j = end;

        /*
        ex) 40, 60, 20, 30, 50
        첫 번째 ipvot은 40, i = 1, j = 3

        i = 1 j = 4 일때 if(i < j)로 swap => 40 30 20 60 50
        i = 3 j = 2 일때 swap(num, start, j) => 20 30 40 60 50 

        i = 3 j = 2 일때 아래 실행
        quickSort(numAry, start, j-1);
        quickSort(numAry, j+1, end);

        quickSort(numAry, start, j-1); 
            => start = 0, j = 1 로 실행된다.
            => int i = start +1 이기 때문에 i = 1, j = 1 
            => while(i <= end && key >= numAry[i]){}  는 종료됌
            => while(j > start && key <= numAry[j]){} 는 종료됌

            => quickSort(numAry, 0, -1);
            => quickSort(numAry, 1, 1);
            
        quickSort(numAry, 3, 4);
            => 
        */
        
        while(i <= j){
            while(i <= end && key >= numAry[i]){
                i++;
            }
            while(j > start && key <= numAry[j]){
                j--;
            }

            if(i < j){ 
                swap(numAry, i, j);
            }
        }
        swap(numAry, start, j);
        
        quickSort(numAry, start, j-1);
        quickSort(numAry, j+1, end);
    }
    
    public static void swap(int [] numAry, int a, int b){
        int temp = numAry[a];
        numAry[a] = numAry[b];
        numAry[b] = temp;
    }
}

예시 - > 40 60 20 30 50

1. 40 60 20 30 50 (피벗인덱스 start로 설정)
2. 40 30 20 60 50 ( i = 1 (=index) value = 60, j = 4 (=index) value = 50 ) 
3. 역전 발생!!!  ( i = 3 (=index) value = 60, j = 2 (=index) value = 20 )
4. 20 30 40 60 50 
5. quickSort(numAry, 0, j-1 ) , quickSort(numAry, j + 1 , end )

- 실패 소스코드 -

4.추가 개념

1. 알고리즘 개요:

•  퀵 정렬은 분할 정복 알고리즘의 일종으로, 평균적으로 매우 빠른 정렬 알고리즘입니다.
•  배열을 피벗(pivot) 기준으로 두 부분으로 나누고, 각 부분을 재귀적으로 정렬합니다.

2. 작동 방식:

• 피벗 선택: 배열에서 임의의 요소를 피벗으로 선택합니다.
• 분할: 피벗을 기준으로 작은 값과 큰 값으로 배열을 분할합니다.
• 재귀 호출: 분할된 두 부분에 대해 재귀적으로 퀵 정렬을 적용합니다.

3. 시간 복잡도:

• 평균: O(n log n)
• 최악: O(n^2) (피벗 선택이 매번 최악일 경우)
• 평균은 2^10000 은 상수 10000과 같기 때문에 매우 빠름.
• 최악은 선택,버블,삽입과 동일하다.(난 이번 문제를 pivotIndex를 랜덤하게 뽑았다.)

4. 공간 복잡도:

• O(log n) (재귀 호출의 스택 공간)

5. 특징:

• 평균적으로 빠른 정렬 알고리즘.
• 제자리 정렬(In-place Sort)로 추가적인 메모리 사용이 적음.
• 불안정 정렬(Unstable Sort).

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

1. 문제 번호 2587

2. 문제 풀이

한줄 평가

•   퀵 정렬(Quick Sort) : 대규모 데이터의 경우 적절하며 분할정복법을 사용하여 피벗인덱스를 활용

문제를 먼저 정확히 파악

나의 문제풀이 방식 및 순서

1. 1. 퀵 정렬을 통해서 사용

3. 소스 인증

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

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int [] numAry = new int[5];
        int i = 0;
        
        while(i < 5){
            numAry[i] = Integer.parseInt(br.readLine());
            i++;
        }
        quickSort(numAry, 0, 4);

        int sum_numAry = 0;
        int middle = numAry[2];
        for(int z = 0; z < numAry.length; z++){
            sum_numAry += numAry[z];
        }
        System.out.println(sum_numAry/5);
        System.out.println(middle);

        
    }
    public static void quickSort(int [] numAry, int start, int end){
        if(start>=end){
            return;
        }
        
        int pivotIndex = new Random().nextInt(end - start + 1) + start;
        swap(numAry, start, pivotIndex);

        int key = numAry[start];
        int i = start+1;
        int j = end;

        while(i <= j){
            while(i <= end && numAry[i] <= key){
                i++;
            }
            while(j > start && numAry[j] >= key){
                j--;
            }

            if(i > j){
                swap(numAry, start, j);
            }else {
                swap(numAry, i, j);
            }
            
        }
        quickSort(numAry, start, j-1);
        quickSort(numAry, j + 1, end);
    }
    public static void swap(int [] numAry, int start, int pivotIndex){
        int temp = numAry[start];
        numAry[start] = numAry[pivotIndex];
        numAry[pivotIndex] = temp;
    }
    
}

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

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

1. 문제 번호 2751

2. 문제 풀이

한줄 평가

•   퀵 정렬(Quick Sort) : 대규모 데이터의 경우 적절하며 분할정복법을 사용하여 피벗인덱스를 활용

문제를 먼저 정확히 파악

나의 문제풀이 방식 및 순서

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

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

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

2. 배열의 경우 주소값을 공유하기 때문에 return 값 불 필요(이건 나만 해당)

3. 퀵 정렬 pivotIndex를 꼭 맨앞부터 할 필요 없음(퀵 정렬일때)

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

1. 3 7 8 1 5 9 6 10 2 4 ( 3 이 pivotIndex 시작)(왼쪽에서는 pivotIndex보다 큰 값, 오른쪽에서는 pivotIndex보다 작은 값)
2. 3 2 8 1 5 9 7 10 7 4 ( 7 < - > 2 ) 
3. 3 2 1 8 5 9 6 10 7 4 ( 8 < - > 1 )
4. 1 2 3 8 5 9 6 10 7 4 ( 엇갈릴 경우 왼쪽을 기준으로 값을 교환한다.) (더 이상은 없다는 뜻임)
5. 1 2 3 8 5 9 6 10 7 4 ( 9 < - > 4 )
   ( 1,2 를 그룹1, 8~4까지 그룹2 )
   ( 그룹1 에서는 왼쪽부터 큰값 , 오른쪽부터 작은 값을 고르면 엇갈리니 1은 확정된다. 자동적으로 2도 확정된다 )
   ( 그룹2 에서는 
6. 1 2 3 8 5 4 6 10 7 9 ( 10 < - > 7 )
7. 1 2 3 8 5 4 6 7 10 9 ( 7 < - > 8   )( 엇갈릴 경우 왼쪽을 기준으로 값을 교환한다.) 
8. 1 2 3 7 5 4 6 8 10 9 
   ( 7~6를 그룹1, 10,9까지 그룹2)
   
   
9. 1 2 3 7 5 4 6 8 10 9 ( 7 < - > 6 )
10. 1 2 3 6 5 4 7 8 10 9 

예시 - > 7 2 1 6 8 

1. 6 2 1 7 8 (피벗인덱스 1을 설정)
2. 6 2 1 7 8 ( i = 3 (=index) value = 7, j = 2 (=index) value = 1 ) 
3. 1 2 6 7 8 ( pivotIndex < - > j (=index) ) 
4. quickSort(numAry, 0, j-1 ) , quickSort(numAry, j + 1 , end ) 

3. 소스 인증

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

// The main method must be in a class named "Main".
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];
        
        for(int i = 0; i < N; i++ ){
            numAry[i] = Integer.parseInt(br.readLine());
        }
        quickSort(numAry, 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();
    }

    public static void quickSort(int [] data, int start, int end){ 
        /*start : 분할하려는 부분 집합의 시작
          end   : 분할하려는 부분 집합의 시작*/
        if(start>=end){
            return;
        }

        int pivotIndex = new Random().nextInt(end - start + 1) + start;
        swap(data, start, pivotIndex);
        //start 0 , End 100 = 101 즉 0~100까지 중 하나 생성
        //start 3 , End 80  일때 0~77인데 +start로 인해 3~77 중 하나 생성
        //그 랜덤 값 중 하나(pivotIndex)를 맨 앞자리로 가져온다.
        
        int key = start; //키는 첫 번째 인덱스
        int i = start+1; //왼쪽 출발 인덱스
        int j = end; //오른쪽 출발 인덱스
        int temp;

        while(i <= j){ //1. 전체 배열의 index 엇갈리 여부 확인
            while (i <= end && data[i] <= data[key]) {
                i++;
            }    
            while (j > start && data[j] >= data[key]) {
                j--;
            }
            
            if(i > j){ //1. 내부 배열의 엇갈린 상태일때는 키 값과 교체
            	swap(data, j, key); //j는 작은 값 i는 큰 값이니, pivotIndex를 j와 교체하여 작은 값을 맨 앞자리 확정
                //temp = data[j];
                //data[j] = data[key];
                //data[key] = temp;
            } else { //i의 큰값과 j의 작은값을 교체
            	swap(data, j, i);
                //temp = data[j];
                //data[j] = data[i];
                //data[i] = temp;
            }
        }
        quickSort(data, start, j - 1);
        quickSort(data, j + 1, end);
    }
    
    public static void swap(int[] data, int a, int b) {
        int temp = data[a];
        data[a] = data[b];
        data[b] = temp;
    }
}

예시 - > 7 2 1 6 8 

1. 6 2 1 7 8 (피벗인덱스 1을 설정)
2. 6 2 1 7 8 ( i = 3 (=index) value = 7, j = 2 (=index) value = 1 ) 
3. 1 2 6 7 8 ( pivotIndex < - > j (=index) ) 
4. quickSort(numAry, 0, j-1 ) , quickSort(numAry, j + 1 , end )

- 실패 소스코드 -

4.추가 개념

1. 알고리즘 개요:

•  퀵 정렬은 분할 정복 알고리즘의 일종으로, 평균적으로 매우 빠른 정렬 알고리즘입니다.
•  배열을 피벗(pivot) 기준으로 두 부분으로 나누고, 각 부분을 재귀적으로 정렬합니다.

2. 작동 방식:

• 피벗 선택: 배열에서 임의의 요소를 피벗으로 선택합니다.
• 분할: 피벗을 기준으로 작은 값과 큰 값으로 배열을 분할합니다.
• 재귀 호출: 분할된 두 부분에 대해 재귀적으로 퀵 정렬을 적용합니다.

3. 시간 복잡도:

• 평균: O(n log n)
• 최악: O(n^2) (피벗 선택이 매번 최악일 경우)
• 평균은 2^10000 은 상수 10000과 같기 때문에 매우 빠름.
• 최악은 선택,버블,삽입과 동일하다.(난 이번 문제를 pivotIndex를 랜덤하게 뽑았다.)

4. 공간 복잡도:

• O(log n) (재귀 호출의 스택 공간)

5. 특징:

• 평균적으로 빠른 정렬 알고리즘.
• 제자리 정렬(In-place Sort)로 추가적인 메모리 사용이 적음.
• 불안정 정렬(Unstable Sort).

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

1. 문제 번호 2750

2. 문제 풀이

한줄 평가

•   선택정렬 (배열중 최소값을 찾아 맨 앞자리와 스왑)
•   버블정렬 (1회의 반복이 0...부터 끝까지 옆의 수와 큰 수를 반복적으로 뒤로 보낸다.)
•   삽입정렬 (1회의 반복이 1...부터 앞의 값과 비교하여 작으면 반복적으로 앞으로 보낸다.) 

문제를 먼저 정확히 파악

나의 문제풀이 방식 및 순서

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

1. 이중 for문을 활용한다. 두 번째 for문은  최소값을 찾아서 첫 번째 for문에서 스왑처리

       for문의 형태 + 선택 정렬하는 로직 주의

for (int i = 0; i < numAry.length; i++) {
    minValue = Integer.MAX_VALUE;
    temp = Integer.MAX_VALUE;
    index = Integer.MAX_VALUE;

    for (int j = i; j < numAry.length; j++) {
        if(minValue > numAry[j]){
            minValue = numAry[j];
            index = j;
        }
    }
    temp = numAry[i];
    numAry[i] = numAry[index];
    numAry[index] = temp;
}

1. 이중 for문을 활용한다. 첫 번째 for문은 반복횟수를 나타내고 두 번째 for문으로 버블정렬 처리
   
   인덱스 주의 + for문의 형태 + 버블 정렬하는 로직 주의

 for(int i = 0; i < numAry.length - 1 ; i++){
    for(int j = 0; j < numAry.length -1 - i; j++){
        if(numAry[j] > numAry[j+1]){
            int temp = numAry[j];
            numAry[j] = numAry[j+1];
            numAry[j+1] = temp;
        }
    }
}

1. 이중 for문을 활용한다. 첫 번째 for문은 반복횟수를 나타내고 두 번째 for문으로 버블정렬 처리
   
   인덱스 주의 + for문의 형태 + 버블 정렬하는 로직 주의

for(int i = 1; i < numAry.length; i++){
    int j = i;
    int temp = numAry[j];

    while(j > 0 && numAry[j-1]>numAry[j]){
        temp = numAry[j-1];
        numAry[j-1] = numAry[j];
        numAry[j] = temp;
        j--;
    }
}

3. 소스 인증

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

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        //Integer N = Integer.valueOf(); //wrapper객체로 반환
        //String str1 = Integer.toString(123);
        //String str1 = String.valueOf(123);
        /*
        String.valueOf는 내부적으로 Integer.toString()을 사용하지만
        null값의 경우 에러가 발생하지 않는다.
        */
        
        
        int [] numAry = new int[N];

        for (int i = 0; i < N;i++ ) {
            numAry[i] = Integer.parseInt(br.readLine());
        }
        int index, temp, minValue;
        
        for (int i = 0; i < numAry.length; i++) {
            minValue = Integer.MAX_VALUE;
            temp = Integer.MAX_VALUE;
            index = Integer.MAX_VALUE;
            
            for (int j = i; j < numAry.length; j++) {
                if(minValue > numAry[j]){
                    minValue = numAry[j];
                    index = j;
                }
            }
            temp = numAry[i];
            numAry[i] = numAry[index];
            numAry[index] = temp;
        }
        
        for (int i = 0; i < numAry.length; i++){
            System.out.println(numAry[i]);
        }
    }
}

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

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int [] numAry = new int[N];

        for (int i = 0; i < N;i++ ) {
            numAry[i] = Integer.parseInt(br.readLine());
        }
        for(int i = 0; i < numAry.length - 1; i++){ //맨 끝은 계산할 필요 없으니
            for(int j = 0; j < numAry.length - 1 - i; j++){ //맨 끝은 numAry[j+1]로 계산한다 + 뒤에서 i 자리는 이미 정렬 
                if(numAry[j] > numAry[j+1]){
                    int temp = numAry[j];    //대각선 스왑 
                    numAry[j] = numAry[j+1]; //대각선 스왑
                    numAry[j+1] = temp;      //대각선 스왑
                }
            }
        }
        
        for (int i = 0; i < numAry.length; i++){
            System.out.println(numAry[i]);
        }
    }
}

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

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        for(int i = 1; i < numAry.length; i++){
            int j = i;
            
            /*
                int j = i 는 그 앞들의 모든 값과 비교해서 작으면 맨 앞으로 보내야 하기 때문에 
                while     는 그 앞들의 모든 값과 비교해서 작으면 맨 앞으로 보내야 하기 때문에 
                j > 0     는 j-- 떄문에 필요함
                
            */
            while(j > 0 && numAry[j] < numAry[j-1]){ 
                int temp = numAry[j-1];  //대각선스왑
                numAry[j-1] = numAry[j]; //대각선스왑
                numAry[j] = temp;        //대각선스왑
                j--;
            }
        }

        for(int i : numAry){
            System.out.println(i);
        }
    }
}

- 실패 소스코드 -

4.추가 개념

1. 알고리즘 개요:

• 선택 정렬은 주어진 리스트를 순차적으로 정렬하는 비교 기반 정렬 알고리즘입니다.
• 리스트에서 최소값을 찾아 첫 번째 요소와 교환하고, 다음 최소값을 찾아 두 번째 요소와 교환하는 방식으로 진행됩니다.

2. 작동 방식:

• 첫 번째 루프: 리스트의 첫 번째 요소부터 마지막 요소까지 반복합니다.
• 두 번째 루프: 최소값을 찾기 위해 현재 위치에서 끝까지 탐색합니다.
• 교환: 최소값을 현재 위치에 있는 요소와 교환합니다.

3. 시간 복잡도:

• 평균 및 최악의 경우: O(n^2)
• 최선의 경우: O(n^2)
  • 예 ) 5,4,3,2,1 의 순차로 배열되어 있는경우
    • 5+4+3+2+1  첫 자리 5는 5번 , 두번째 자리는 4번, 3번째 자리는 3번, ... 이렇게 반복해서 살펴봐야 한다.
    • 등차수열의 공식으로 풀어서 보면 N * ( N + 1 ) / 2 이므로 5 * ( 5 + 1 ) / 2 = 15번 이다.
    • 근데 무한히 큰 수를 대입해보면 1000000*(1000000+1) / 2 에서 +1과 / 2는 큰 의미가 없다.
      이미 1000000 * 1000000이 시간을 다잡아먹는다. 
    • 그래서 결론은 O(N^2) 이다.
    • N이 많아질수록 속도가 2차 함수 형태로 증가한다.

4. 공간 복잡도:

• O(1) (제자리 정렬 알고리즘)

5. 특징:

• 간단하고 구현이 쉬움.
• 작은 데이터셋에 적합.
• 안정적이지 않음(같은 값의 원소가 순서를 유지하지 않음).

1. 알고리즘 개요:

• 버블 정렬은 인접한 두 요소를 비교하여 정렬하는 비교 기반 정렬 알고리즘입니다.
• 배열을 반복적으로 순회하며, 인접한 두 요소를 비교하고 필요에 따라 교환하여 정렬을 완료합니다.

2. 작동 방식:

• 첫 번째 루프: 배열의 끝에서 끝까지 반복합니다.
• 두 번째 루프: 각 요소를 인접한 요소와 비교하여 필요하면 교환합니다.
• 가장 큰 요소가 배열의 끝으로 ‘버블’처럼 올라옵니다.

3. 시간 복잡도:

• 평균 및 최악의 경우: O(n^2)
• 최선의 경우: O(n) (이미 정렬된 경우)
• 선택정렬과 복잡도는 동일하지만 매번 버블정렬을 해주기 때문에 가장 효율이 안좋다.

4. 공간 복잡도:

• O(1) (제자리 정렬 알고리즘)

5. 특징:

• 간단하고 이해하기 쉬움.
• 작은 데이터셋에 적합.
• 안정적인 정렬(같은 값의 원소가 순서를 유지함).

1. 알고리즘 개요:

• 삽입 정렬은 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누고, 정렬되지 않은 요소를 하나씩 정렬된 부분에 삽입하여 정렬하는 알고리즘입니다.

2. 작동 방식:

• 두 번째 요소부터 시작하여, 현재 요소를 정렬된 부분과 비교하면서 올바른 위치에 삽입합니다.
• 정렬된 부분은 항상 오름차순을 유지합니다.

3. 시간 복잡도:

• 평균 및 최악의 경우: O(n^2)
• 최선의 경우: O(n) (이미 정렬된 경우)
• 선택,버블 정렬과 복잡도는 동일하지만 "거의 정렬된 상황에서는" 가장 효율이 좋다. 2,3,4,5,1 일때 ..

4. 공간 복잡도:

• O(1) (제자리 정렬 알고리즘)

5. 특징:

• 단순하고 구현이 쉬움.
• 작은 데이터셋에 적합.
• 안정적인 정렬(같은 값의 원소가 순서를 유지함).

5. 참조 블로그

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