***
* *
***

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];
    }
}

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

• 알고리즘의 시작은 다양한 정렬 알고리즘을 공부하는 것부터 시작이 된다.
• 알고리즘을 연습할땐 유명한 알고리즘을 따라 해보면서 알고리즘을 이해하고 스스로 만들어봐야 한다.
• 알고리즘 연습 방법
  • 문제를 읽고 분석한 후 간단한 경우부터 복잡한 경우 순서대로 생각해보면서 알고리즘을 생각해 본다. (직접 작성해가면서 생각해봐도 좋다.)
  • 가능한 알고리즘이 보인다면, 구현할 알고리즘을 세부 항목으로 나누고, 문장으로 세부 항목을 나누어서 적어본다.
  • 코드화하기 위해서 데이터 구조 또는 사용할 변수를 정리하고 각 문장을 코드 레벨로 적는다.

정렬이란?

• 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것이다.
• 정렬은 프로그램 작성 시 빈번하게 필요로 한다.

버블 정렬 이란?

• 두 인접한 데이터를 비교해 원하는 순서에 따라 swap 하고, 데이터의 전체 값이 원하는 순서로 정렬이 될 때까지 반복한다. (2개의 데이터를 계속 비교해가며 인덱스를 교환한다.)
  • [1,2] 일때 원하는 정렬 방식이 내림차순이라면 1과 2의 위치를 스왑 한다.
  • [3,6,1,2] 일 때 처음부터 두 데이터씩 값을 비교해 내림차순이라면
    • 3과 6을 비교해 6을 앞으로 보낸다.
    • 바뀌어진 3과 1을 비교해 순서가 맞다면 내버려둔다.
    • 1과 2를 비교해 2를 앞으로 보낸다.
    • 이렇게 스왑 한다면 [6,3,2,1] 내림차순으로 정렬이 된다.
    • 하나의 배열에 버블정렬을 적용한다면, 최대 배열의 사이즈 -1번의 정렬이 필요하다.
      • 로직이 한번 적용이 될 때마다, 맨 뒤의 데이터가 원하는 순서의 값이 오게 된다. (내림차순이라면 가장 작은 값, 오름차순이라면 가장 큰 값)
      • 이중 반복문으로 사이즈-1의 상수회를 반복하는 반복문 안에 앞 데이터와 뒷 데이터의 값을 비교해 swap을 한다.
      • 불필요한 체크를 피하기 위해 boolean 변수를 선언해 이미 정렬이 다 되었다면 break 해준다.
      • 따라서 버블정렬은 O(n^2)의 시간복잡도를 가진다. (완전 정렬이 되어있는 상태라면 O(n)이 된다.)

선택 정렬 이란?

• 모든 데이터를 순회하면서 원하는 순서(가장 작거나 크거나) 별로 값을 선택해서 맨 앞 인덱스로 swap 한다.
  • 가장 작거나 큰 데이터를 기억하고 있다가 모든 순회가 끝난다면 앞으로 스왑 한다.
  • 마찬가지로 두 번째로 작거나 큰 데이터를 기억하고 있다가 맨 앞+1으로 스왑 한다.
  • 이런 식으로 마찬가지로 크게는 n개의 데이터가 있다면 n-1번 반복을 한다.
    • 맨 처음에는 맨 앞 인덱스를 저장한 후, 해당 인덱스 +1부터 순회를 하면서 값을 비교한다.
    • 반복문을 다 끝낸 후, 저장된 인덱스와 맨 앞 인덱스를 스왑 하는 식으로 정렬을 진행한다.
  • 마찬가지로 n번 반복하는 반복문이 2개 이므로 O(n^2)의 시간복잡도를 가진다.

삽입 정렬 이란?

• (오름차순 기준) 데이터를 처음 인덱스부터 순회하면서 해당 인덱스의 데이터보다 앞의 인덱스의 데이터가 값이 크다면 스왑하는 식으로 앞의 인덱스의 값과 비교하며 스왑 하여 작은 데이터가 앞에 존재할 때 멈춘다.
  • 맨 앞의 인덱스 +1 부터 앞의 값과 비교를 한다.
    • 안에 속해있는 반복문은 밖의 반복문 +1 부터 맨앞의 인덱스까지 순회한다.
      • 어떻게 보면 버블 정렬과 반대되는 정렬 방법 같다는 생각이 든다.

세 정렬 방법의 차이점

• 버블 정렬
  • 버블 정렬 같은 경우엔 앞, 뒤 데이터를 비교하며 계속 swap 메서드를 실행한다.
  • 최악의 경우 모든 앞 뒤 데이터를 스왑 하는 경우가 발생한다. (n번의 스왑 * 사이즈-1)
  • 셋 중에 가장 느리지만 단순하다.
• 선택 정렬
  • 선택 정렬의 경우 단순히 모든 데이터를 순회 후 가장 작거나 큰 데이터의 인덱스를 기억해놓고 한 번의 스왑만 실행한다. 버블 정렬보다 훨씬 빠르다.
• 삽입 정렬
  • 삽입 정렬의 경우는 모든 데이터를 순회하지 않고 각 인덱스 별로 앞으로 순회하며 해당 인덱스의 데이터보다 작은 값이 존재할 때까지 검색 후 스왑을 실행한다.
  • 선택 정렬 같은 경우엔 사이즈 n만큼의 검색 후 스왑을 진행한다면 삽입 정렬은 1++ <n 이런 식으로 검색 시간도 적게 걸린다.

마무리

• 버블정렬은 잘 안 쓰인다고 합니다. (정렬할 때 많이 써왔던 거 같은데..)
• 삽입 정렬과 선택 정렬 중에서 잘 골라서 사용하면 된답니다.
  • 삽입 정렬이 선택 정렬보다 빠른 이유가 모든 아이템을 순회하지 않기 때문에라고 하는데..  그러면 선택 정렬은 한 번의 스왑만 진행하지만 삽입 정렬은 앞에 작은 값이 존재할 때까지 스왑을 진행하는데 이런 거에 대한 성능상 차이는 없을까..?라는 생각이 듭니다.
    • 그래서 누가 삽입 정렬은 배열의 크기가 클수록 효율이 떨어진댔는데 그게 그 말이었나? 싶습니다.
    • 그러면 차라리 선택정렬만 쓰는 게 낫겠다는 생각이 듭니다.
• 이름이 어려워서 겁먹었는데 생각보다 별거 없는 것 같습니다. 훗훗

공간복잡도 → 얼마나 많은 저장 공간이 필요할까 ?

좋은 알고리즘은 실행 시간도 짧고, 저장 공간도 적게 쓴다.

• 시간 복잡도와 공간 복잡도를 둘다 적게 가져가기는 어렵다.
  • 시간과 공간은 반비례적 경향이 있다.
  • 최근 대용량 시스템이 보편화 되면서, 공간 복잡도 보다는 시간 복잡도가 우선이 되었다.

공간 복잡도의 계산

• 기존에는 공간 복잡도도 고려해야 하는 경우도 있었다.
• 기존 알고리즘 문제들은 공간 복잡도 제약 사항이 있는 경우가 있다.
• 기존 문제들에 영향을 받아 면접시에도 공간 복잡도를 묻는 경우가 있다.
  • 현업에서는 최근 빅데이터를 다룰 때 저장 공간을 고려해서 구현을 하는 경우도 있다.
  • 그 외의 경우라면 보통은 시간복잡도만 생각을 한다.
• 공간 복잡도란?
  • 프로그램을 실행 및 완료하는데 필요한 저장공간의 양을 뜻한다.
  • 총 필요 저장 공간
    • 고정 공간 ⇒ 코드 저장 공간, (알고리즘과 무관한 공간)
    • 가변 공간 ⇒ 실행 중 동적으로 필요한 공간 (알고리즘 실행과 관련있는 공간)
  • 빅 오 표기법을 생각해볼 때, 고정 공간은 상수이므로 공간 복잡도는 가변 공간에 좌우된다.
  • 메소드를 호출할때의 예제
    • 매개 변수로 어떠한 값을 리턴해줄때, 매개변수의 값에 상관없이 고정된 코드 저장 공간이 존재할때 ⇒ O(1)
    • 매개 변수의 값에 따라서 메모리에 차지하는 공간이 많아진다 → 가변 공간 ⇒ O(n)

마무리

• 공간복잡도에 대해서 짧게 정리해보았습니다.
• 단순히 메모리를 얼마나 잡아먹느냐가 관건인것같습니다.
• 제대로 정리가 된 기분은 아니지만 그래도 강의를 들었으니 코딩을 하다가 깨닫게 되는 날이 올거라 생각이 듭니다.

So when I die (the [first] I will see in (heaven) is a score list).
[ first in ] ( first out ).
Half Moon tonight (At least it is better than no Moon at all].
A rope may form )( a trail in a maze.
Help( I[m being held prisoner in a fortune cookie factory)].
([ (([( [ ] ) ( ) (( ))] )) ]).
 .
.

yes
yes
no
no
no
yes
yes

풀이

해당 문제는 스텍 자료구조를 이용해서 풀이하면 된다.

똑같이 구현을 했는데도 메소드로 추출해서 풀이했을때와 단순히 메인에 다 때려박았을때 메인은 20퍼센트에서 계속 틀렸다고 떴었다.

왜인지 아직까지도 이해가 안간다 (?)

여기서 제일 신경써야 할것은 ([)] 와 같이 ()() [][] 이런식으로 마무리되는 문자열만 yes 를 출력해야 된다는 것 이다.

그리고 마지막에도 스택이 비어있을때 yes 아니면 no 로 체크를 한번 더해준다. (해당 부분때문에 오답이 나온건가 싶기도 하다.)

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

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

        while(true){
            String str =br.readLine();
            if(str.equals(".")){
                break;
            }
            System.out.println(check(str));
        }
    }
    public static ArrayDeque<Character> deque = new ArrayDeque<>();
    public static String check(String str){
        deque.clear();
        for(int i=0; i<str.length();i++){
            char c = str.charAt(i);
            if(c=='(' || c=='[') {
                deque.push(c);
            }else{
                if(c==')'){
                    if(deque.isEmpty() || deque.peek()!='('){
                        return "no";
                    }else{
                        deque.pop();
                    }
                }else if(c==']'){
                    if(deque.isEmpty() || deque.peek()!='['){
                        return "no";
                    }else{
                        deque.pop();
                    }
                }
            }
        }
        if(deque.isEmpty()){
            return "yes";
        }else{
            return "no";
        }
    }

해당 문제의 시간 복잡도는 반복문이 상수회 실행되고 한 반복문 안에 조건문이 존재하기 때문에 O(n) 으로 표기하나..? 해당 부분은 배우지 않아서 아직 모르겠다. (정리된 글을 보아도 조건문이 존재할때의 시간복잡도는 아직 이해가 덜 되었다.)