삽입정렬이란?


Key값과 정렬된 리스트가 주어졌을 때,

Key값을 정렬된 리스트의 알맞은 위치에 삽입하여 하나의 정렬된 리스트를 만드는 것



동작 원리


다음과 같이 숫자 4개가 주어지고 이를 삽입정렬을 이용해 정렬한다면



 5

 4

 2


1. key값을 두번째 숫자 4로 지정


5

 4

3

 2



2. 키값과 그 앞에 있는 값을 비교 후 키값이 작으면 자리를 바꾼다.


4

 5

3

 2



3. 더 이상 비교할 값이 없으므로 정렬 1회전이 끝난 것



4. 세번째 값을 key값으로 지정


4

 5

3

 2



5. 앞의 값과 비교 및 위치 이동


4

 3

5

 2


3

 4

 2



6. 이를 반복하면 모든 값이 정렬된다.


2

 3

 5



예제코드)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.Scanner;
 
public class InsertionSort {
    
    /*
     * 삽입정렬
     * Key값과 정렬된 배열이 주어졌을 때,
     * Key값을 정렬된 배열의 알맞는 자리에 삽입하여 정렬하는 방법
     */
    
    public static void main(String[] args) {
        //값을 입력받고 출력하는 부
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] array = new int[n];
        for(int i=0;i<n;i++) {
            array[i] = scan.nextInt();
        }
        
        InsertSort(array);
        
        for(int i:array) System.out.print(i);
        
        scan.close();
    }
    
    public static void InsertSort(int[] array) {
        for(int i=1;i<array.length;i++) { //주어진 값들 중에서 2번째 값부터 Key값으로 선정
            int key = array[i];           //i번째 수를 Key값으로 설정
            int j = i-1;                   //Key값을 기준으로 왼쪽에 있는 수부터 비교
            while(j>=0 && array[j]>key) { //맨앞까지 비교했거나 key값이 왼쪽수보다 작으면 순회를 멈춤
                array[j+1= array[j];    //비교한 값을 오른쪽으로 한칸 이동
                --j; 
            }
            array[j+1= key;               //알맞는 key값의 위치에 저장
        }
    }
}
 
cs



시간 복잡도 분석


최선의 경우는 모든 수가 이미 정렬된 상태로 수가 들어올 때이다.

이때는 수의 개수인 n의 복잡도를 가진다.


하지만 최악의 경우인 반대 순서로 정렬되어 들어온 경우에는

Key값을 옮기고 그 안에서 전부다 값들을 비교해야 하기에 n제곱을 수행 복잡도를 가진다.



문제

https://www.acmicpc.net/problem/10844



풀이


2차원 배열로 메모이제이션해야 되는 문제였다.

D[N][L]을 N자리수에서 끝자리가 L로 끝나는 수의 계단수의 가지수라고 한다면

N자리 수에서 끝자리가 2로 정해지면, D[N-1][1]과 D[N-1][3]을 구하면 된다.

이를 점화식으로 표현하면

D[N][L] = D[N-1][L-1] + D[N-1][L+1]




'알고리즘 > BaekJoon' 카테고리의 다른 글

[11052]붕어빵 판매하기  (0) 2017.01.11
[9095]1,2,3 더하기  (0) 2017.01.11
[11726]2 x n 타일링  (0) 2017.01.10
[3052]나머지(Modulo)  (0) 2017.01.02

문제

https://www.acmicpc.net/problem/11052


풀이

D[i]이 i개를 팔 때 얻을 수 있는 최대 수익

P[i]는 i개를 팔 때 얻는 수익


총 붕어빵이 i개 있을 때

1개를 팔았을 때 최대값은 P[1] + D[i-1]

2개를 팔았을 때 최대값은 P[2] + D[i-2]

j개를 팔았을 때 최대값은 P[j] + D[i-j]


이렇게 따져서 이들 값중에서 최대값이 D[i]

점화식을 살펴보면

D[i] = max(P[j] + P[i-j])

단, j의 범위는 1<= j <= i


이를 바탕으로 코딩을 해보면 된다.


#아직 프로그래밍적 사고와 다이나믹 프로그래밍적 문제 접근 방식이 익숙하지 않은것 같다.

'알고리즘 > BaekJoon' 카테고리의 다른 글

[10844]쉬운 계단 수  (0) 2017.01.13
[9095]1,2,3 더하기  (0) 2017.01.11
[11726]2 x n 타일링  (0) 2017.01.10
[3052]나머지(Modulo)  (0) 2017.01.02

문제

https://www.acmicpc.net/problem/9095


풀이

다이나믹 프로그래밍으로 풀 수 있었다.

n일때 1,2,3을 더해서 n을 표현하는 방법의 가지수를 d[n]이라고 한다.

마지막에 올 수 있는 숫자는 1, 2, 3 인데 

1이 오면 d[n-1]

2가 오면 d[n-2]

3이 오면 d[n-3] 이 성립된다.


이를 바탕으로 점화식을 세워보면

d[n] = d[n-1] + d[n-2] + d[n-3]


top-down 방식



bottom-up 방식


'알고리즘 > BaekJoon' 카테고리의 다른 글

[10844]쉬운 계단 수  (0) 2017.01.13
[11052]붕어빵 판매하기  (0) 2017.01.11
[11726]2 x n 타일링  (0) 2017.01.10
[3052]나머지(Modulo)  (0) 2017.01.02

문제



풀이 


_M#]



문제

https://www.acmicpc.net/problem/11726


풀이

피보나치 수열과 같다.


bottom-up 방식으로 푸니까 런타임에러가 뜬다.


그래서 top-down방식으로 풀어봄


'알고리즘 > BaekJoon' 카테고리의 다른 글

[10844]쉬운 계단 수  (0) 2017.01.13
[11052]붕어빵 판매하기  (0) 2017.01.11
[9095]1,2,3 더하기  (0) 2017.01.11
[3052]나머지(Modulo)  (0) 2017.01.02

문제

https://www.acmicpc.net/problem/3052



풀이


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int count = 1;
        int[] remain = new int[10];
        for(int i=0;i<10;i++) {
            int num = scan.nextInt();
            remain[i] = num%42;
        }
        Arrays.sort(remain);
        for(int i=0; i<9; i++) {
            if(remain[i]!=remain[i+1]) {
                count++;
            }
        }
        
        System.out.println(count);
    }
}
cs


'알고리즘 > BaekJoon' 카테고리의 다른 글

[10844]쉬운 계단 수  (0) 2017.01.13
[11052]붕어빵 판매하기  (0) 2017.01.11
[9095]1,2,3 더하기  (0) 2017.01.11
[11726]2 x n 타일링  (0) 2017.01.10

+ Recent posts