***
* *
***

27

***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************
*********         *********
* ** ** *         * ** ** *
*********         *********
***   ***         ***   ***
* *   * *         * *   * *
***   ***         ***   ***
*********         *********
* ** ** *         * ** ** *
*********         *********
***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************

풀이

일단 해당 문제가 어떠한 패턴으로 진행되는지를 먼저 이해하면 된다.

• 가운데를 제외한 모든 칸에 *을 찍어준다.

예제 출력을 보면 패턴이 다 똑같다는것을 알 수 있다.

저 하나의 프린트 

***
* *
***

가 몇개가 반복되어도 똑같이 (1,1) 에는 공백이 들어가게 된다.

해당 부분을 인지한 상태로 풀이하면 된다.

이 문제도 마찬가지로 분할정복과 재귀용법을 활용하여 풀이하는 문제이므로, 브레이크 포인트를 정한다.

단순하다 '더 이상 쪼갤 수 없을 때' 를 브레이크 포인트로 두면 된다.

모든 데이터를 null 로 두고 별을 찍어나가는것 대신 미리 공백으로 채워둔 후 (1,1) 이 아닐때 별을 찍어주면 된다.

package baekjoon.a2447;

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

public class a2447 {
    public static char[][] arr;
    public static StringBuilder sb = new StringBuilder();
    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());
        arr= new char[N][N];
        for(int i=0; i<N;i++){
            Arrays.fill(arr[i],' ');
        }
        func(0,0,N);
        for(int i=0; i<N; i++){
            for(int j=0;j<N;j++){
                sb.append(arr[i][j]);
            }
           sb.append("\n");
        }
        System.out.println(sb);

    }
    public static void func(int row,int col, int N){
        if(N==1){
            arr[row][col]='*';
            return;
        }
        N = N/3;
        for(int i=0; i<3; i++){
            for(int j=0; j<3; j++){
                if(i ==1 && j==1){
                    continue;
                }else{
                    func(row+(i*N),col+(j*N),N);
                }
            }
        }

    }

}

(1,1) 일때는 별을 찍지 않고 패스하기때문에 continue 를 해주면 된다.

4
-6 -8 7 -4
-5 -5 14 11
11 11 -1 -1
4 9 -2 -4

11

8
-1 2 14 7 4 -5 8 9
10 6 23 2 -1 -1 7 11
9 3 5 -2 4 4 6 6
7 15 0 8 21 20 6 6
19 8 12 -8 4 5 2 9
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24

17

풀이

해당 문제는 재귀용법, 분할정복을 활용하여 풀이하면 된다.

마찬가지로 브레이크 포인트를 어디서 잡느냐가 중요하다.

해당 문제는 2X2 배열이 끝이고 그 배열에서 2번쨰로 가장 큰 수를 반환해야하기 때문에

배열의 크기가 N*N 즉 N=2 일때 반환하도록 하면 된다.

다른 문제들과 마찬가지로 상하좌우로 4등분 하는식으로 쪼개기 때문에 

브레이크 포인트에서 크기가 4인 배열을 만들고 정렬 후 2번째로 큰 값 반환

그리고 각 파트별로 (상하좌우) 2번쨰로 큰 값을 구한 후 마지막으로 2번째로 큰 값을 구하는식으로 전개를 하면 된다.

      if(N==2){
            int count=0;
            int[] funcArr= new int[4];
            for(int i=row ; i<row+N;i++){
                for(int j=col ; j<col+N; j++){
                    funcArr[count] = arr[i][j];
                    count++;
                }
            }
            Arrays.sort(funcArr);
            return funcArr[funcArr.length-2];
        }

브레이크 포인트를 이렇게 잡아준다.

    public static int func(int row,int col,int N){
        if(N==2){
            int count=0;
            int[] funcArr= new int[4];
            for(int i=row ; i<row+N;i++){
                for(int j=col ; j<col+N; j++){
                    funcArr[count] = arr[i][j];
                    count++;
                }
            }
            Arrays.sort(funcArr);
            return funcArr[funcArr.length-2];
        }
        N = N/2;
        int[] funcArr = new int[4];
        int count =0;
        for(int i=0; i<2;i++){
            for(int j=0; j<2;j++){
                funcArr[count] = func(row+(i*N),col+(j*N),N);
                count++;
            }
        }
        Arrays.sort(funcArr);
        return funcArr[funcArr.length-2];
    }

함수를 이렇게 호출해주면 된다 .

package baekjoon.a17829;

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

import java.util.Arrays;
import java.util.StringTokenizer;

public class a17829 {
    public static int[][] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        arr = new int[N][N];
        for(int i=0; i<N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        System.out.println(func(0,0,N));
    }

    public static int func(int row,int col,int N){
        if(N==2){
            int count=0;
            int[] funcArr= new int[4];
            for(int i=row ; i<row+N;i++){
                for(int j=col ; j<col+N; j++){
                    funcArr[count] = arr[i][j];
                    count++;
                }
            }
            Arrays.sort(funcArr);
            return funcArr[funcArr.length-2];
        }
        N = N/2;
        int[] funcArr = new int[4];
        int count =0;
        for(int i=0; i<2;i++){
            for(int j=0; j<2;j++){
                funcArr[count] = func(row+(i*N),col+(j*N),N);
                count++;
            }
        }
        Arrays.sort(funcArr);
        return funcArr[funcArr.length-2];
    }
}

문제

흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.

주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다

위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 쿼드 트리 구조를 이용하여 압축하면 "(0(0011)(0(0111)01)1)"로 표현된다.  N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.

출력

영상을 압축한 결과를 출력한다.

예제 입력 1 복사

8
11110000
11110000
00011100
00011100
11110000
11110000
11110011
11110011

예제 출력 1 복사

((110(0101))(0010)1(0001))

풀이

해당 문제는 어떻게 풀이하면 될까?

문제에 주어진 힌트대로 이해하면 된다.

문제를 보면 4분할을 실시할때 괄호가 열리고, 종료될때 괄호가 닫히는것을 볼 수 있다.

단순히 스트링 빌더로 재귀함수 호출시에 그 직전에 "(" 를 더해주고 닫을떄 ")" 를 더해주면 된다.

마찬가지로 브레이크포인트는 모든 부분의 숫자가 일치할때이고, 브레이크 포인트에 해당 숫자를 스트링빌더에 append 후 return 해주면 된다.

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class a1992 {
    static char[][] board;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        board = new char[N][N];
        for(int i=0; i<N; i++){
            String n = br.readLine();
            for(int j=0; j<N; j++){
                board[i][j] = n.charAt(j);
            }
        }

        divide(0,0,N);
        System.out.println(sb);
    }

    public static void divide(int row,int col,int size){
        if(check(row,col,size)){
            sb.append(board[row][col]);
            return;
        }
        sb.append("(");
        int newSize= size/2;
        divide(row,col,newSize);
        divide(row,col+newSize,newSize);
        divide(row+newSize,col,newSize);
        divide(row+newSize,col+newSize,newSize);
        sb.append(")");
    }
    public static boolean check(int row,int col,int size){
        char temp = board[row][col];
        for(int i=row; i<row+size; i++){
            for(int j=col; j<col+size; j++){
                if(temp!=board[i][j]){
                    return false;
                }
            }
        }
        return true;

    }
}

9
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
0 1 -1 0 1 -1 0 1 -1
0 -1 1 0 1 -1 0 1 -1
0 1 -1 1 0 -1 0 1 -1

10
12
11

풀이

해당 문제는 바로 직전에 업로드한 2630번과 거의 같다.

전 문제에 엄청 헤맸었기 때문에 응용을 할 수 있는 문제를 찾아야겠다 하고 찾으니 바로 등장했다.

해당 문제도 단순히 문제에서 제시하는 힌트를 그대로 이해하면 된다.

• 모든 부분의 수가 같다면 나누지 않는다.
• 같지 않다면 9 등분한다. (종이는 보통 9의 배수가 면적으로 주어진다.)

이 두 조건을 두고 봤을 때, 전 문제와 다른 것은 단순히 몇 등분을 하냐 와 조건이 몇 개인가? 를 따지면 된다.

이 문제도 마찬가지로 좌표를 이용해서 풀이해야하기 때문에 어렵게 느껴질 수 있다.

하지만 한번 문제의 유형을 익힌다면 전혀 어렵지 않으니 이해가 어렵다면 자존심을 굽히고 풀이를 참고하자.

마찬가지로 계속 나눌거라는 힌트가 주어졌기 때문에 재귀용법이 사용될 것이다.

브레이크포인트를 먼저 잡아주자. 바로 각각 부분의 숫자가 모두 같아야 한다는 점이다.

말 그대로 기준점을 잡아 2중 반복문으로 순회하면서 데이터가 같다면 true, 아니라면 false를 반환하는 체크용 메서드를 선언하자

    public static boolean check(int row,int col,int size){
        int pivot = paper[row][col];
        for(int i=row; i<row+size;i++){
            for(int j=col;j<col+size;j++){
                if(paper[i][j]!=pivot){
                    return false;
                }
            }
        }
        return true;
    }

마찬가지로 배열과 카운트에 대한 변수는 모두 정적변수로 선언했다.

그리고 브레이크 포인트를 만들었으니 재귀함수를 만들면 된다.

마찬가지로 9 등분이라는 건 각 변을 3으로 나눠서 체크하는 것이기 때문에 사이즈를 3 등분해서 함수를 호출해주면 된다.

그런데 여기서는 9등분이라고 했으면, 메서드를 9번 호출해야 되는데 , 단순히 그냥 한 줄씩 작성해 9번 호출할까..?

에 대한 대답은 그러면 16등분 25등분 이러면 어떻게 하시려고..?

이중 반복문으로 각각 로우와 칼럼에 늘어나는 인덱스*등분 사이즈 (나눠진 사이즈)를 더해가면서 함수를 호출하도록 하면 된다.

마찬가지로 브레이크 포인트를 먼저 선언해주고 통과했을 때 해당 값들이 어떠한 숫자로 이루어져 있는지 (-1,0,1 중에 하나)를 체크해서 카운트를 ++해주도록 하면 된다.

 public static void divide(int row,int col,int size){
        if (check(row, col, size)) {
            if(paper[row][col]==-1){
                minus++;
            }else if(paper[row][col]==0){
                zero++;
            }else{
                plus++;
            }
            return;
        }
        int[] move = {0,1,2};
        int newSize= size/3;
        for(int i=0; i<3;i++){
            for(int j=0; j<3;j++){
                divide(row+(i*newSize),col+(j*newSize),newSize);
            }
        }
    }

이렇게 하면 깔끔하게 표현이 가능하다.

package baekjoon.a1780;

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

public class a1780 {
    public static int minus =0;
    public static int zero =0;
    public static int plus =0;
    public static int[][] paper;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        paper = new int[N][N];
        for(int i=0; i<N;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<N;j++){
                paper[i][j]= Integer.parseInt(st.nextToken());
            }
        }
        divide(0,0,N);
        System.out.println(minus);
        System.out.println(zero);
        System.out.println(plus);
    }

    public static void divide(int row,int col,int size){
        if (check(row, col, size)) {
            if(paper[row][col]==-1){
                minus++;
            }else if(paper[row][col]==0){
                zero++;
            }else{
                plus++;
            }
            return;
        }
        int[] move = {0,1,2};
        int newSize= size/3;
        for(int i=0; i<3;i++){
            for(int j=0; j<3;j++){
                divide(row+(i*newSize),col+(j*newSize),newSize);
            }
        }
    }
    public static boolean check(int row,int col,int size){
        int pivot = paper[row][col];
        for(int i=row; i<row+size;i++){
            for(int j=col;j<col+size;j++){
                if(paper[i][j]!=pivot){
                    return false;
                }
            }
        }
        return true;
    }
}

문제

아래 <그림 1>과 같이 여러 개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.

전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수)이라면 종이를 자르는 규칙은 다음과 같다.

전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색 종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

위와 같은 규칙에 따라 잘랐을 때 <그림 3>은 <그림 1>의 종이를 처음 나눈 후의 상태를, <그림 4>는 두 번째 나눈 후의 상태를, <그림 5>는 최종적으로 만들어진 다양한 크기의 9장의 하얀색 색종이와 7장의 파란색 색종이를 보여주고 있다.

입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다.

출력

첫째 줄에는 잘라진 햐얀색 색종이의 개수를 출력하고, 둘째 줄에는 파란색 색종이의 개수를 출력한다.

예제 입력 1 복사

8
1 1 0 0 0 0 1 1
1 1 0 0 0 0 1 1
0 0 0 0 1 1 0 0
0 0 0 0 1 1 0 0
1 0 0 0 1 1 1 1
0 1 0 0 1 1 1 1
0 0 1 1 1 1 1 1
0 0 1 1 1 1 1 1

예제 출력 1 복사

9
7

풀이

해당 문제를 정말 알고리즘 초보자의 입장에서 보았을 때 어떻게 풀어야 할까..?

남들은 이 문제가 쉬운 편이라고는 하지만 나같이 이런 수학문제를 처음 풀어보는 사람들은 문제를 이해하는 데에도 시간이 꽤 걸릴 것이다.

단순히 이럴 땐 문제를 말 그대로 처음부터 순서를 매겨가며 읽어가면 된다.

색종이의 모든 부분이 색상이 같을 때는 나누지 않는다.

하지만 색상이 같지 않다면 4등분으로 나눈다. (상좌 상우 하좌 하우)

나눈 색종이를 다시 색상이 같은지 구별한다.

나눈 색종이의 색상이 또 다 같지 않다면, 다시 4등분으로 나눈다.

여기서 알 수 있는 부분은 해당 문제는 재귀용법을 사용하는구나! 를 알 수가 있다.

그리고 마찬가지로 재귀용법에서 중요한 어느 부분에서 스탑을 할 것인가 라는 물음에 색종이의 모든 부분의 색상이 같을 때라고 대답할 수 있다.

해당 문제가 어렵게 느껴지는 이유 첫 번째는 2차원 배열을 이용하여 좌표로 나타내야 한다는 것이다.

단순히 생각해 그림을 그리듯이 문제를 풀어나가면 된다.

일단 우리는 스탑에 대한 조건을 모든 부분의 색상이 같을 때로 정해두었다.

그러니 해당 부분을 메서드로 먼저 선언해 준다.

    public static boolean checkColor(int row, int col, int size){
        int color = paper[row][col];
        for(int i=row; i<row+size; i++){
            for(int j=col; j<col+size; j++){
                if(paper[i][j]!=color){
                    return false;
                }
            }
        }
        return true;
    }

배열과 색상에 대한 카운트를 정적 변수로 선언해 주고, 체크하는 함수의 기준을 단순히 맨 첫 데이터로 두고 순회하면 된다.

그리고 해당 함수를 재귀함수의 브레이크 조건으로 넣어둔다.

        if(checkColor(row,col,size)){
            if(paper[row][col]==0){
                white++;
            }else{
                blue++;
            }
            return;
        }

이렇게 재귀함수의 필드에 색상이 다 같다면  을 조건으로 두고 같을 때 첫 데이터의 값이 0이라면 흰색의 카운트를 더해주고, 아니라면 파란색에 카운트를 더해준다.



그리고 그 밑에는 재귀함수를 호출하면 된다.

단순히 말 그대로 문제를 풀이해나가면 되기 때문에 상하좌우로 4등 분해 재귀함수를 호출하면 된다.

이렇게 하면 각 부분별로 모든 부분의 색상이 같을 때까지 나눠서 탐색을 하게 된다.

해당 부분이 분할 정복의 개념을 가지고 있다. (문제를 더 이상 쪼갤 수 없을 때까지 쪼갠 후 문제를 해결해나가는 것)

단순히 색종이를 더 이상 쪼갤 수 없을 때까지 쪼갠다면, 어떠한 부분은 1x1의 크기를 가진 색종이가 될 것이다. 그렇다면 멈추고 카운트를 더하는 식으로 문제를 해결해나가는 것이다.

    public static void divide(int row,int col,int size) {
        if(checkColor(row,col,size)){
            if(paper[row][col]==0){
                white++;
            }else{
                blue++;
            }
            return;
        }
        int newSize = size/2;
        divide(row,col,newSize);
        divide(row,col+newSize,newSize);
        divide(row+newSize,col,newSize);
        divide(row+newSize,col+newSize,newSize);
    }

이렇게 메서드를 호출해주면 각각 알맞은 타이밍에 반복이 멈추게 되면서 결과를 가져온다.

4등분을 해야 하기 때문에 각각 좌표로 나타내었을 때를 생각하며 코드를 작성해주면 된다.

package baekjoon.a2630;

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

public class a2630 {
    public static int white = 0;
    public static int blue = 0;
    public static int[][] paper;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        paper = new int[N][N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                paper[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        divide(0,0,N);
        System.out.println(white);
        System.out.println(blue);
    }

    public static void divide(int row,int col,int size) {
        if(checkColor(row,col,size)){
            if(paper[row][col]==0){
                white++;
            }else{
                blue++;
            }
            return;
        }
        int newSize = size/2;
        divide(row,col,newSize);
        divide(row,col+newSize,newSize);
        divide(row+newSize,col,newSize);
        divide(row+newSize,col+newSize,newSize);
    }
    public static boolean checkColor(int row, int col, int size){
        int color = paper[row][col];
        for(int i=row; i<row+size; i++){
            for(int j=col; j<col+size; j++){
                if(paper[i][j]!=color){
                    return false;
                }
            }
        }
        return true;
    }
}

전체 코드로 나타내면 이렇다.

재귀호출 부분의 코드가 더러워 보일 수 있는데, 이럴 때 다시 2중 반복문으로 i+newSize로 재귀함수를 각각 호출하게 선언하면 깔끔하게 표현할 수 있다.

동적 계획법 / 분할 정복

동적 계획법 (다이내믹 프로그래밍)

• 입력 크기가 작은 부분 문제들을 해결한 후 메모이제이션 기법을 사용해서 (미리 결괏값을 저장하여) 문제를 푸는 것
  • 상향직 접근법 → 해당 문제를 풀기 위해 가장 단순한 형태의 해답을 구한 후 이를 저장 후 해당 결괏값을 가지고 상위 문제를 풀이
  • 메모이제이션 : 프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술

분할 정복

• 큰 문제를 풀기 위해 문제를 잘게 쪼개서 풀이한 후 다시 합병하여 문제의 답을 얻는 알고리즘
  • 하향식 접근법 → 상위의 해답을 구하기 위해 하위의 해답을 구하는 방식
    • 일반적으로 재귀함수로 구현한다.

공통점과 차이점

• 공통점
  • 문제를 잘게 쪼개서, 가장 작은 단위로 분할한다
• 차이점
  • 동적 계획법
    • 메모이제이션 기법 사용
    • 상위 문제 해결시 재활용함
  • 분할 정복
    • 부분 문제는 서로 중복되지 않는다.
    • 메모이제이션 기법을 사용하지 않음

동적 계획법 활용하기

• 기존의 재귀함수를 호출할 땐?
  • 팩토리얼을 구현할 때, 각각의 매개값의 결과를 구하기 위해 매번 다시 처음부터 순회하며 값을 구한 후 더해준다.
    • 동적계획법을 이용한다면, 이미 계산한 값들은 저장해놓고 순서를 넘기기 때문에 불필요한 호출을 하지 않는다.

public static int recur(int n){
        if(n<=1){
            return n;
        }
        return recur(n-1)+recur(n-2);
    } //기존의 재귀함수 호출

public static int dynamicFunc(int n){
		Integer[] cache = new Integer[n+1] //저장용 배열을 생성한다.
		cache[0] = 0; //미리 구할 수 있는 값들은 저장해놓는다.
		cache[1] = 1;
		for(int i=2; i<n+1; i++){
			cache[i] = cache[i-1]+ cache[i-2]; //계산된 값을 저장해가며 올라간다.
		}
		return cache[n]; 
		}
	}

분할 정복을 사용하는 병합 정렬과 퀵 정렬

병합 정렬

• 재귀 용법을 활용한 정렬 알고리즘
  • 리스트를 절반으로 나눠 비슷한 크기의 두 리스트로 나눈다.
  • 각 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
  • 두 리스트를 다시 하나의 정렬된 리스트로 병합한다.
  • 리스트를 더 이상 쪼갤 수 없을 때까지 나눠서 정렬을 하며 다시 합친다.
    • 병합 정렬은 크게 두 가지의 단계를 거친다.
      • 끝없이 분할하는 split 단계
      • 분할한 것들을 병합하는 merge단계
      • 병합 시에 매번 각각의 데이터의 최소값의 인덱스를 저장한다.
      • 병합시에 각각의 데이터를 비교해서 작은 것을 앞에, 큰 것을 뒤에 놓게 된다.
      • 각각의 데이터는 매번 병합 시에 정렬이 되어있는 상태이다.
• 항상 데이터가 들어오면 두 단계로 분리한다.
• 분리한 데이터를 단계별로 합친다.
• 합칠 시에는 데이터를 비교해가면서 병합된 데이터는 정렬이 된 상태를 유지하게 한다.

분할 메서드를 선언해 보자.

public static void split(ArrayList<Integer> list){
        if(list.size()<=1){
            return;
        }
        int medium = list.size()/2;
        List<Integer> leftList = new ArrayList<>(list.subList(0,medium));
        List<Integer> rightList = new ArrayList<>(list.subList(medium,list.size()));
        System.out.println(leftList);
        System.out.println(rightList);
    }

subList() 메서드를 사용하여 사이즈 /2 만큼의 리스트를 두개 생성한다.

해당 메소드를 재귀호출하여 나눈 후 병합한다.

public static ArrayList<Integer> mergeSplitFunc(ArrayList<Integer> list){
        if(list.size()<=1){
            return list;
        }
        else{
            int medium = list.size()/2;
            //재귀 호출로 더 이상 나눌 수 없을때까지 나눈다.
            ArrayList<Integer> leftList = mergeSplitFunc(new ArrayList<>(list.subList(0,medium)));
            ArrayList<Integer> rightList = mergeSplitFunc(new ArrayList<>(list.subList(medium,list.size())));
            return mergeFunc(leftList,rightList);
        }
    } //나누는 부분에서 재귀호출을 실행한다.

그리고 병합 메소드를 선언한다.

• 더 이상 쪼갤 수 없을 때까지 분할 후 차례로 들어오는 것이기 때문에 왼쪽 리스트, 오른쪽 리스트 이렇게 값을 비교한다.
• 반복문이 아닌 while 문으로 포인터에 1씩 더해주면서 값을 비교하고 종료시킨다.
• 3개의 케이스를 만들어서 케이스별로 정렬을 시도한다.
  • 왼쪽 리스트와 오른쪽 리스트가 존재할 때, 왼쪽 리스트만 존재할때, 오른쪽 리스트만 존재할 때를 비교한다.
    • 각각 리스트별로 다른 사이즈가 될 수 있기 때문이다.

public static ArrayList<Integer> mergeFunc(ArrayList<Integer> leftList,ArrayList<Integer> rightList){
        ArrayList<Integer> mergedList = new ArrayList<>();
        int leftPoint = 0;
        int rightPoint = 0;

        //CASE1 : left / right 둘 다 존재할 때
        while(leftList.size() > leftPoint && rightList.size()>rightPoint){
            if(leftList.get(leftPoint)> rightList.get(rightPoint)){
                mergedList.add(rightList.get(rightPoint));
                rightPoint++;
            }
            else{
                mergedList.add(leftList.get(leftPoint));
                leftPoint++;
            }
        }
        //CASE2 : right 데이터가 없을 때
        while(leftList.size()>leftPoint){
            mergedList.add(leftList.get(leftPoint));
            leftPoint++;
            //나머지를 다 넣어준다.
        }
        // 왼쪽 데이터가 처리된 상태이지만 오른쪽 데이터가 아직 존재하는 상태라면
        // case3으로 들어올 수가 있다.
        //CASE3 : left 데이터가 없을 때
        while(rightList.size()>rightPoint){
            mergedList.add((rightList.get(rightPoint)));
            rightPoint++;
        }
        return mergedList;
    }

퀵정렬

• 퀵정렬이란?
  • 정렬 알고리즘의 꽃이라고 할 수 있다.
  • 속도도 빠르고 코드도 간결하게 쉽게 정렬이 가능하다.
    • 피벗(기준점)을 정해서, 각각의 데이터를 확인하면서 피벗보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 배치한다. ****(위치를 잡는다고 생각하면 좋다. 보통 맨 앞에 있는 값을 피벗으로 정한다.)
    • 각 왼쪽 오른쪽의 데이터들은 재귀용법을 사용해서 위 작업을 반복한다.
    • 함수는 각각 왼쪽 + 피벗 + 오른쪽을 리턴한다.
  • 피벗을 정한 후 데이터를 순회하면서 피벗을 기준으로 양쪽에 데이터를 배치한다.
  • 병합 정렬과 차이점은 병합정렬은 분리 후 정렬, 병합 과정을 거친다면 퀵 소트는 분리 시에 정렬하며 나중에 합친다.

코드로 구현해 보기

• 기본적인 split 함수 구현해 보기
  • 재귀함수를 선언한다.
  • 매개값으로 주어지는 배열의 사이즈가 1이라면 아무 동작도 하지 않은 채 배열을 리턴한다.
  • 사이즈가 1 이상이라면 맨 앞의 데이터를 기준점으로 잡고 왼쪽에 배치할 배열과 오른쪽에 배치할 배열을 생성해 인덱스 1부터 순회하여 값이 작다면 왼쪽, 크다면 오른쪽배열로 데이터를 넣어준다.
  • 순회가 끝난 후 각 배열의 데이터를 담을 mergedArr를 생성해 addAll 메서드로 데이터들을 넣어준다.
    • 이때 재귀함수를 호출한다.
    • 왼쪽데이터를 또다시 split 함수로 나눠서 정렬하고, 오른쪽 데이터 또한 마찬가지로 split 함수로 나눠서 정렬한다.
    • 따라서 addAll 메서드 안에 split 함수를 호출하도록 한다.
    • 기준점 (피벗)은 단건만 add 메서드를 통해 삽입한다.

public static ArrayList<Integer> splitFunc(ArrayList<Integer> dataList) {
            if (dataList.size() <= 1) {
                return dataList;
            }
            int pivot = dataList.get(0);
            ArrayList<Integer> leftArr = new ArrayList<>();
            ArrayList<Integer> rightArr = new ArrayList<>();
            for (int i = 1; i < dataList.size(); i++) {
                if (dataList.get(i) > pivot) {
                    rightArr.add(dataList.get(i));
                } else {
                    leftArr.add(dataList.get(i));
                }
            }
            ArrayList<Integer> mergedArr = new ArrayList<>();
            mergedArr.addAll(splitFunc(leftArr));
            mergedArr.add(pivot);
            mergedArr.addAll(splitFunc(rightArr));
            return mergedArr;
        }

• 내림차순으로 정렬하고 싶다면 반대로 동작하도록 하면 된다.

퀵 정렬의 시간복잡도

• 병합정렬과 유사하다. 시간복잡도는 O(n logn) 이 된다.
  • 최악의 경우에는 이미 정렬된 배열에서 pivot 이 가장 크거나 , 가장 작으면 가장 큰 시간이 소요된다.
  • 모든 데이터를 비교해야 하는 상황이 나올 수 있으므로 O(n^2)가 된다.
    • 1,2,3,4,5의 데이터를 퀵 정렬로 정렬한다면, 1 2345 2 345 3 45 이런 식으로 정렬하기 때문에 비효율적이다.

마무리

• 병합정렬과 퀵 정렬은 어떻게 봤을 때 비슷해 보입니다.
  • 병합 정렬은 더 이상 쪼갤 수 없을 때까지 쪼갠 후 정렬하며 병합한다면, 퀵 정렬은 쪼개면서 정렬을 하고 합치는 느낌입니다.
• 검색을 해보니 Collections의 sort는 병합정렬을 기반으로 한 팀 정렬 방식을 사용하고, Arrays의 sort는 듀얼피벗 퀵정렬 방식으로 정렬한다고 합니다.
  • 정렬 방법에 대해서 공부하면서 자바에서 어떠한 api 가 어떤 알고리즘을 구현해 제공해주는지 알고 각각 맞는 상황에 사용하는 게 관건인 것 같습니다 :D