[ 정렬 ] 삽입 정렬, 퀵 정렬(백준 11399, 11004)

[ STUDY ]/CodingTest

[ 정렬 ] 삽입 정렬, 퀵 정렬(백준 11399, 11004)

김강니 2024. 11. 7. 05:00

삽입 정렬(Insertion Sort) : O(n²)

이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬

1️⃣ 현재 index에 있는 데이터 값을 선택한다.

2️⃣ 현재 선택한 데이터가 정렬된 데이터 범위에 삽입될 위치를 탐색한다.

3️⃣ 삽입 위치부터 Index에 있는 위치까지 shift연산을 수행한다.

4️⃣ 삽입 위치에 현재 선택한 데이터를 삽입하고 index++연산을 수행한다.

5️⃣ 전체 데이터의 크기만큼 index가 커질 때까지, 즉 선택할 데이터가 없을 때까지 반복한다.

6️⃣ 비교 대상이 없을 때까지 1️⃣ ~ 5️⃣ 를 반복한다.

☝🏻 적절한 삽입 위치를 탐색하는 부분에서 이진 탐색등과 같은 탐색 알고리즘을 사용하면 시간 복잡도를 줄일 수 있다.
O(N) -> O(log N)

11399 : ATM

문제

인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.

사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다. 4번 사람은 3+1+4+3 = 11분, 5번 사람은 3+1+4+3+2 = 13분이 걸리게 된다. 이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이 된다.

줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 2번 사람은 1분만에, 5번 사람은 1+2 = 3분, 1번 사람은 1+2+3 = 6분, 4번 사람은 1+2+3+3 = 9분, 3번 사람은 1+2+3+3+4 = 13분이 걸리게 된다. 각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.

줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)

출력

첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.

입력	출력
5 3 1 4 3 2	32

문제 풀이

삽입 정렬로 정렬 후 누적합구하기
이진 삽입 정렬로 구해보기

실행 코드

1. 삽입 정렬에서 삽입위치를 선택 : O(n)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class P11399 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        // 입력받기, 필요한 변수와 배열 선언
        int N = Integer.parseInt(br.readLine());
        int[] A = new int[N]; // P(i)값
        int[] S = new int[N]; // 누적합
        st = new StringTokenizer(br.readLine());
        for(int i = 0;i<N;i++)
            A[i] = Integer.parseInt(st.nextToken());

        // 삽입 정렬(Selection Sort)
        for(int i=1;i<N;i++){
            int select = A[i];
            for(int j=0;j<i;j++){
                if(select<=A[j]){
                    for(int k=i-1;k>=j;k--)
                        A[k+1] = A[k];
                    A[j] = select;
                    break;
                }
            }
        }

        // 누적합
        for(int i=0;i<N;i++){
            if(i==0)
                S[i] = A[i];
            else
                S[i] = S[i-1]+A[i];
        }

        // 누적합의 합 계산
        int time = 0;
        for(int i=0;i<N;i++)
            time+=S[i];

        // 출력
        System.out.print(time);
    }
}

2. 이진 삽입 정렬을 사용해 삽입위치를 선택 : O(log n)

💡 이진삽입정렬을 해도 데이터를 이동시키기때문에 전체 시간복잡도는 O(n2)이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class P11399 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        // 입력받기, 필요한 변수와 배열 선언
        int N = Integer.parseInt(br.readLine());
        int[] A = new int[N]; // P(i)값
        int[] S = new int[N]; // 누적합
        st = new StringTokenizer(br.readLine());
        for(int i = 0;i<N;i++)
            A[i] = Integer.parseInt(st.nextToken());

        // 삽입 정렬(Selection Sort)
        for(int i=1;i<N;i++){
            int select = A[i];
            // 이진탐색
            int idx = BinarySearch(A, 0, i-1, select);
            for(int j=i-1;j>=idx;j--)
                A[j+1] = A[j];
            A[idx] = select;
        }

        // 누적합
        for(int i=0;i<N;i++){
            if(i==0)
                S[i] = A[i];
            else
                S[i] = S[i-1]+A[i];
        }

        // 누적합의 합 계산
        int time = 0;
        for(int i=0;i<N;i++)
            time+=S[i];

        // 출력
        System.out.print(time);
    }

    // 이진탐색
    private static int BinarySearch(int[] A, int left, int right, int select) {
        int mid=0;
        while(left<=right){
            mid = (left+right)/2;
            if(A[mid]<=select)
                left = mid+1;
            else if(A[mid]>select)
                right = mid-1;
        }
        return left;
    }
}

퀵 정렬(Quick Sort)

기준값(pivot)을 선정해서 해당 값보다 작은 데이터와 큰 데이터로 분류를 반복해 정렬하는 알고리즘

평균 시간 복잡도 : O(nlogn)
최악 시간 복잡도 : O(n2)

1️⃣ 데이터를 분할하는 pivot을 설정한다.

2️⃣ pivot을 기준으로 다음 a~e 과정을 거쳐 데이터를 2개의 집합으로 분리한다.

ⓐ start가 가리키는 데이터가 pivot이 가리키는 데이터보다 작으면 start를 오른쪽으로 1칸 이동한다.

ⓑ end가 가리키는 데이터가 pivot이 가리키는 데이터보다 크면 end를 왼쪽으로 1칸 이동한다.

start, end가 가리키는 데이터를 swap하고 start는 오른쪽, end는 왼쪽으로 1칸씩 이동한다.

ⓓ start가 end가 만날 때까지 ⓐ ~ ⓒ를 반복한다.

ⓔ start와 end가 만나면 만난 지점에서 가리키는 데이터와 pivot이 가리키는 데이터를 비교하여 pivot이 가리키는 데이터가 크면 만

난 지점의 오른쪽에, 작으면 만난 지점의 왼쪽에 pivot이 가리키는 데이터 삽입한다.

3️⃣ 분리 집합에서 각각 다시 pivot을 선정한다.

4️⃣ 분리 집합이 1개 이하가 될 때까지 과정 1️⃣ ~ 3️⃣ 을 반복한다.

11004 : K번째 수 구하기

문제

수 N개 A₁, A₂, ..., A_N이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 5,000,000)과 K (1 ≤ K ≤ N)이 주어진다.

둘째에는 A₁, A₂, ..., A_N이 주어진다. (-10⁹ ≤ A_i ≤ 10⁹)

입력값이 500만개이기때문에 O(n²)시간복잡도의 알고리즘은 사용하면 시간초과남

출력

A를 정렬했을 때, 앞에서부터 K번째 있는 수를 출력한다.

첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.

입력	출력
5 2 4 1 2 3 5	2

문제 풀이

퀵정렬로 정렬 후 K번째 있는 수를 구하기
pivot을 정하는 방법
- pivot == k : k번째 수를 찾은 것이므로 알고리즘 종료
- pivot > k : pivot의 왼쪽부분에서 값을 찾는다.
- pivot < k : pivot의 오른쪽부분에서 값을 찾는다.

슈도 코드

N = 배열 길이
K = 찾을 인덱스
A = 저장할 배열

1. 퀵정렬 함수 호출(A:배열, 0:배열 시작 인덱스, N-1:배열 마지막 인덱스, K:찾을 인덱스)

2. 퀵정렬
	if(시작인덱스가 마지막인덱스보다 작을때)
    	pivot위치 반환 함수(partition)
        if(pivot==k)
            찾음!
        else if(pivot>k)
	    pivot 왼쪽부분에서 다시 퀵정렬 실행
        else
            pivot 오른쪽부분에서 다시 퀵정렬 실행

3. pivot을 기준으로 분할하고 pivot위치 반환
	랜덤값, 처음값, 중간에 있는 값 상관없음 하나 골라서 맨 처음 인덱스랑 swap
        i = start + 1;
        j = end;

        while(i<=j)
            while(i가 배열 끝 인덱스보다 작거나 같고 pivot값보다 작으면) i위치 한 칸 오른쪽으로;
            while(j가 배열 시작 인덱스보다 크고 pivot값보다 크면) j위치 한 칸 왼쪽으로;
            if(i<j)
                i의 값이 pivot보다 크고 j의 값이 pivot보다 작은 경우임
                둘의 자리를 바꿈 그러면 작은 값은 왼쪽으로 큰 값은 오른쪽으로 가게 됨

        j와 i가 교차하게 되면 j와 start(맨처음 기준) swap함
        그리고 j의 위치를 반환 -> 이게 pivot의 위치가 정해진거임

실행 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class P11004 {
    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())-1;
        int[] A = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++)
            A[i] = Integer.parseInt(st.nextToken());
        int pivot = 0;

        // 퀵정렬
        quickSort(A, 0, N-1, K);
        System.out.println(A[K]);
    }

    // 퀵정렬 이용해서 K번째 수 찾기
    private static void quickSort(int[] A, int start, int end, int k) {
        if(start<end){
            int pivot = partition(A, start, end);
            if(pivot==k)
                return; //k번째 찾음
            else if(pivot>k)
                quickSort(A, start, pivot-1, k);
            else
                quickSort(A, pivot+1, end, k);
        }
    }

    // 피벗을 기준으로 분할
    private static int partition(int[] A, int start, int end) {
        int mid = (start+end) / 2;
        swap(A, start, mid); // 중간값을 index1로 이동
        int pivot = A[start]; // 맨처음 i=0
        int i = start+1;
        int j = end;

        while(i<=j){
            while(i<=end && A[i] <= pivot) i++;
            while(j>start && A[j] >= pivot) j--;
            if(i<j){
                swap(A, i, j);
            }
        }
        swap(A, start, j); //피벗을 적절한 위치로
        return j; //피벗 위치
    }

    // 배열 요소 교환
    private static void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}

먼가 쉬운거같은데 엄청 헷갈린다....

근데 이거 시간초과난다....퀵정렬 최악이 엔제곱이어서 나는거같은데....그냥 공부할라고 짠거니까 일단 넘어감..

Arrays.sort사용하면 아마 nlogn이라서 풀릴듯(?)

'[ STUDY ] > CodingTest' 카테고리의 다른 글

[ 탐색 ] DFS 깊이 우선 탐색(백준 11724) (0)	2024.11.07
[ 정렬 ] 병합 정렬, 기수 정렬(백준 1517, 2750) (0)	2024.11.07
[ 정렬 ] 버블 정렬, 선택 정렬 (백준 2750, 1427) (1)	2024.11.06
[ 자료구조 ] 스택과 큐(백준 1874, 2164, 11286) (0)	2024.11.01
[ 자료구조 ] 슬라이딩 윈도우(백준 12891) (1)	2024.10.31

현재글[ 정렬 ] 삽입 정렬, 퀵 정렬(백준 11399, 11004)

나다김강니

험나난세상속에뛰어든건나니까암오케....

dfs, 백준, BFS, 다익스트라, HTTP, CodeUp, VMware Fusion, 티스토리챌린지, linux, 오블완, dp, 우선순위 큐, React, Spring Security, Redux, redux-persist, JWT, spring boot, 모두의 리눅스, Troubleshooting,

Today :
Yesterday :

나다김강니