문제

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

예제 입력 1 복사

2

예제 출력 1 복사

3

예제 입력 2 복사

8

예제 출력 2 복사

171

예제 입력 3 복사

12

예제 출력 3 복사

2731

풀이

2xn 타일링 문제와 똑같은 로직이다.

단순히 패턴을 알면 되는데 해당 문제는 dp[3] = dp[1]*2+dp[2] 가 된다.

단순히 코드로 표현하면 된다.

package baekjoon.a11726;

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

public class a11726 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] dp = new int[1001];
        dp[1]=1;
        dp[2]=3;
        for(int i=3;i<=N;i++){
            dp[i]= (dp[i-2]*2+dp[i-1])%10007;
        }
        System.out.println(dp[N]);
    }
}

문제

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

<그림 1>

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.

<그림 2>

계단 오르는 데는 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

예제 입력 1 복사

6
10
20
15
25
10
20

예제 출력 1 복사

75

풀이

dp[1] = arr[1]

dp[2] = dp[2-1]+arr[2] or arr[2]

dp[3] = dp[3-2]+arr[3] or dp[3-1]+arr[3] 

dp[4] = dp[3-3]+dp[4-1]+arr[4] or dp[4-2]+arr[4]

dp[5] = dp[5-3]+arr[5-1]+arr[5]

dp[i] = dp[i-3]+arr[i-1]+arr[i] or dp[i-2]+arr[i]

넘모 쉽죠 ?

계속 반복되는 패턴을 알아내면 풀기 쉽다.

package baekjoon.a2579;

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

public class a2579 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr= new int[N+1];
        int[] dp = new int[N+1];
        for(int i=1;i<=N;i++){
            arr[i]= Integer.parseInt(br.readLine());
        }
        dp[0]=0;
        arr[0]=0;

        for(int i=1; i<=N; i++){
            if(i==1){
                dp[i]=arr[i];
            }else if(i==2){
                dp[i]=Math.max(arr[2],dp[i-1]+arr[i]);
            }else{
                dp[i]= Math.max(dp[i-3]+arr[i-1]+arr[i],dp[i-2]+arr[i]);
            }
        }
        System.out.println(dp[N]);
    }
}

6
6
10
13
9
8
1

33

풀이

해당 문제는 다이나믹 프로그래밍으로 풀이하는 문제이다.

가장 신경써야 할 문제는 마실 수 있는 최대의 포도주의 양을 구하는것이기 때문에

비교를 해야한다.

총 3잔의 포도주가 주어졌을때

1,2 와 2,3 을 마셨을때의 값을 비교해야한다는것이다.

일단 문제에서 주어진것은 6잔의 포도주와 양이 주어졌고 최대의 포도주 양이 주어졌다.

일단 그것들을 토대로 문제를 그려보면 된다.

일단 6잔이 주어졌을때, 공통적으로 못마시는 잔의 수는 2잔이다.

이것을 단순 O 와 X 로 표기해 보았을때

3잔씩 체크를 한다고 치면 OOX, OXO, XOO 가 될 수 있다는 것이다.

따라서 단순히 저 세개의 경우의 수 중 가장 큰 값을 골라서 배열에 넣어주면 된다.

dp[1] 이라면 첫번쨰 와인인 6

dp[2] 이라면 두번째 와인과 첫번째 와인인 16

dp[3] 이라면 Math.max(첫와인+두번째와인, 두번째와인+세번째와인, 첫번째와인+세번째와인) 이 된다.

마찬가지로 더 구해본다면

dp[4] 일때는 첫와인+두번째와인+ 네번째와인  혹은 첫와인+세번째와인+ 네번째와인 이 될 수 있고

dp[5]일때는 첫와인+두번째와인+네번째와인+다섯번째 혹은 첫와인+세번째+네번째 혹은 두번째+세번째+다섯번째 등등 여러 결과가 나올것이다.

이것을 식으로 표기해보았을때

dp[1] = wine[1]

dp[2] = wine[1]+wine[2]

dp[3] = dp[3-1] 혹은 dp[3-2]+wine[3] 혹은 dp[3-3]+wine[2]+wine[3]

dp[4] = dp[4-2]+wine[4] 혹은 dp[4-3]+wine[3]+wine[4]

dp[5] = dp[5-3]+wine[4]+wine[5]

이런식으로 표현이 가능하다.

여기서 공통적으로 나오는 로직이 있다.

dp[i] = dp[i-1] 혹은 dp[i-2]+wine[i] 혹은 dp[i-3]+wine[i-1]+wine[i]

가 공통적으로 등장하게 된다.

단순히 이걸 코드로 풀이하면 된다.

package baekjoon.a2156;

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

public class a2156 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] dp = new int[N+1];
        int[] wine = new int[N+1];
        for(int i=1; i<=N; i++){
            wine[i] = Integer.parseInt(br.readLine());
        }
        dp[0]=0;
        for(int i=1; i<=N;i++){
            if(i ==1){
                dp[i]=wine[i];
            }else if(i==2){
                dp[i]=wine[i]+wine[i-1];
            }else{
                dp[i]= Math.max(dp[i-1],Math.max(dp[i-2]+wine[i],dp[i-3]+wine[i]+wine[i-1]));
            }
        }
        System.out.println(dp[N]);

    }
}

3
4
7
10

7
44
274

풀이

해당 문제도 다이나믹 프로그래밍으로 풀이하는 문제이다.

마찬가지로, 이 유형들은 내가 직접 어떻게 1과 2와 3을 써서 각각 몇번을 사용해 해당 수가 나올 수 있는지~~~ 이딴건 다 필요없다.

문제에서 원하는 답만 가져다주면 된다는 뜻이다.

마찬가지로 문제에서 11보다 작은 수가 나온다고 했으니 11의 크기를 갖는 배열을 생성해준다.

그리고 이미 주어진 답들은 죄다 넣어놓아도 좋다.  

하지만 나는 가장 작은 경우의 수부터 위로 올라갈것이기 때문에

주어진 답중 가장 작은 수인 4에 대한 해답을 배열에 넣어놓고,

1 와 2와 3일때의 경우의 수만 직접 구해준다.

1일땐 1 하나만 더해지기 때문에 답은 1이 되고

2일땐 1+1 과 +2 가 되기때문에 2

3일땐 1+1+1 과 1+2 2+1 , +3 이 되기때문에 4가 된다.

4일땐 문제에서 알려주었으니 7..

오잉? 벌써 패턴이 보인다.

dp[N-3]+ dp[N-2] + dp[N-1]

하면 얼추 맞는것 같다.

그렇게 반복문을 한번 실행해보고 맞으면 바로 제출하면 된다.

참쉽죵?

package baekjoon.a9095;

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

public class a9095 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] dp = new int[11];
        dp[1]=1;
        dp[2]=2;
        dp[3]=4;
        dp[4]=7;
        for(int i=0; i<N;i++){
            int n = Integer.parseInt(br.readLine());
            for(int j=4; j<=n;j++){
                dp[j]=dp[j-3]+dp[j-2]+dp[j-1];
            }
            System.out.println(dp[n]);
        }
    }
}

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

예제 입력 1 복사

2

예제 출력 1 복사

2

예제 입력 2 복사

9

예제 출력 2 복사

55

풀이

다이나믹 프로그래밍 문제들은 대부분 문제에 힌트가 적혀있다.

해당 문제는 2일때의 가지수와 9일때의 가지수를 제시해주고 있다.

보통은 동적계획법 문제들은 문제에서 원하는것처럼 몇가지의 방법이 존재하는지를 직접 구하라는게 아닌

일정한 패턴으로 반복되는 문제의 패턴을 내가 찾아내고, 진짜 말 그대로 어떠한걸 직접 구하라는게 아닌 답만 구해오면 되는 문제들이 대부분인것 같다.

마찬가지로 해당 문제 또한 1000까지의 숫자가 제시된다고 나와있으니 1001의 인덱스를 가진 배열을 생성해준다. (1부터 순회할것이기 떄문)

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] dp = new int[1001];

그리고 문제의 첫부분에 내가 직접 구할 수 있는 답들은 미리 구해본다.

문제에 일정한 패턴이 존재하는지를 알아보는것이다.

N 이 1일때, 단순 2X1 의 직사각형 하나만 들어가기때문에 1이된다.

N 이 2일때는 문제에서 답을 알려주고있으니 2가 되고,

N 이 3일때는 직사각형이 세로로 3개, 가로로 두개 세로로 하나, 직전의 배치를 반전시킨 모습 이렇게 3가 된다.

어? 벌써 뭔가 패턴이 그려진다.

바로 N-2 + N-1 의 값이 N의 가짓수가 될 수 있다는 말이다.

마찬가지로 N이 4일때의 가짓수를 직접 구해본다면 5가 나올것이다.

고러취~ 하고 바로 반복문으로 4부터 돌려준다.

        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=N;i++){
            dp[i]= (dp[i-2]+dp[i-1])%10007;
        }
        System.out.println(dp[N]);

그냥 아예 답에선 10007으로 나눴을때의 나머지를 구해오라고 했기 때문에 답도 그렇게 넣어준다.

너무 짧은 코드로 깔끔하게 풀리는 문제이다.

오늘 진행한 것들 🤔

• 컴퓨터 구조 정리

• 토이프로젝트 리팩토링
• 동적계획법 알고리즘 문제 풀이

오늘의 배운 점 🤔

• 컴퓨터구조를 정리했습니다.
  • 하드웨어, 소프트웨어, 응용소프트웨어 이렇게 크게 3구조로 나누는것을 알게 되었습니다.
  • 하드웨어는 말그대로 부품, 소프트웨어는 하드웨어에 의존적인 운영체제 따위를 구동하기 위한 로우레벨 언어로 이루어진 프로그램, 응용 소프트웨어는 흔히 아는 프로그램 같은 것이라고 할 수 있는것 같습니다.
  • 단순히 하드웨어가 한부품 부품이 단독적으로 동작하는게 아닌 시스템 버스를 통해서 이런저런 데이터가 오가는것을 알게 되었습니다.
  • 살짝 MVC 패턴과 비슷하다고 생각했습니다. 단방향 통신을 하는 주소공간 버스와, 양방향통신을 하는 데이터, 컨트롤버스가 모델 뷰 컨트롤러 사이의 요청응답과 비슷하다고 느꼈습니다.
  • 단순히 키보드 키 하나를 눌렀을때에도 상태레지스터, 데이터 레지스터를 확인해서 입력이 된다고 하니, 어느정도 머릿속으로 구조가 그려지는 기분입니다.
  • 폰노이만 구조에 대해서 살짝 공부했습니다.
  • 폰노이만 구조와 하버드 구조의 차이점에 대해서도 살짝 공부하게 되었습니다.
  • 하지만 아직 한번 본것으로는 이해가 안되니 다시 공부해봐야겠습니다.
• 동적 계획법 알고리즘을 활용하여 문제를 풀이했습니다.
  • 풀이를 하다보니 느낀점은 분할정복은 쪼갤 수 없는 부분을 브레이크 포인트로 정한다면, 동적 계획법은 브레이크 포인트를 정하는 대신에 값을 기억해둬 반복 호출을 멈추는..? 그런 정도로 이해가 되었습니다.
  • 관건은 결과값을 얻으려고 풀이를 하는것이 아닌 문제에서 요구하는 답을 구하기 위한 풀이로 사용된다는 점이었습니다.
  • 일반적으로 배열을 사용하는것 같습니다.
  • 다시 글로 정리하면서 생각해보니 이해가 됩니다. 동적 계획법 같은 경우에는 문제의 규칙성을 찾는것  또한 중요한것 같습니다.
• 토이프로젝트 리팩토링을 하였습니다.
  • 기존에 내 댓글이 아닐때 수정이나 삭제버튼이 등장했던 부분에 대해서 단순 if문을 추가하여 비활성화를 시켰습니다.
  • 그리고 게시글과 댓글 삭제에 대한 고민이 생겼었습니다. 데이터를 백업하고 삭제를 하는것이 일반적일지, 단순히 비활성화를 하듯이 삭제 컬럼을 온오프 하는게 맞는것일지에 대한 고민을 해보았습니다.
  • 전자를 redis 로 구현했다가 레디스는 인메모리 데이터베이스라는것이 떠올라 죄다 삭제해버렸습니다.
    • 만료기한을 1년으로 잡고 레디스에 백업 후 삭제하는 로직을 구현했는데, 메모리에 1년동안 저장이라니.. 끔찍한 방법이었습니다.

내일 목표 🤔

• 동적계획법 문제 2문제 이상 풀이
• 가능하면 토이프로젝트 설계하기
• 컴퓨터 구조 정리

2

1

10

3

풀이

해당 문제또한 마찬가지로 다이나믹 프로그래밍을 활용하여 풀이하는 문제이다.

해당 문제에서 제시하는 기본 조건은 3가지로, 가장 신경써야할것은 X를 최소한의 횟수로 1을 만들어야한다는 것이다.

예로, 제시된 예제가 10을 입력했을때 3을 반환해야한다는 것인데, 아무런 생각 없이 구현한다면 4의 결과값이 나오게 된다.

        int[] dp = new int[N+1];
        dp[0] =0;
        dp[1] =0;

마찬가지로 배열을 생성해 N까지 경우의수를 탐색한다.

그리고 이미 제시가 되어있는 값은 입력한다. 0과 1을 입력하면 어떠한 연산도 하지 않기때문에 횟수는 0이 된다.

        for(int i=2; i<=N;i++){
            dp[i] = dp[i-1]+1;
            if(i%2==0){
            dp[i]= Math.min(dp[i],dp[i/2]+1);
            }if(i%3==0){
                dp[i] = Math.min(dp[i],dp[i/3]+1);
            }
        }

그리고 마찬가지로 2부터 문제를 풀어나가기 위해 반복문을 선언한다.

단순히 10까지의 최소 연산 횟수를 구한다고 치면,

• 0 = 0
• 1 = 0
• 2 = 1 (2-1)
• 3 = 1 (3/3)
• 4 = 2 (4/2/2)
• 5 = 3 ((5-1)/2/2)
• 6 = 2 (6/3/2)
• 7 = 3 ((7-1)/3/2)
• 8 = 3 (8/2/2/2)
• 9 = 2 (9/3/3)
• 10 = 3 ((10-1)/3/3)

이렇게 봤을때 느낄 수 있는건, 원래 단순히 최저 횟수를 생각하지 않고 계산을 했을때 , 생각하고 계산했을때의 횟수를 비교해야 된다는 것이다.

위의 연산을 배열로 표현해본다면

• dp[2] = dp[2-1]+1 혹은 dp[2] = dp[2/2]+1
• dp[3] = dp[3/3]+1
• dp[4] = dp[4-1]+1 혹은 dp[4/2]+1 
• dp[5] = dp[5-1]+1 
• dp[6] = dp[6/3]+1 
• dp[7]= dp[7-1]+1 
• dp[8] = dp[8/2]+1
• dp[9] = dp[9/3]+1
• dp[10] = dp[10-1]+1 혹은 dp[10/2]+1

이렇게 구할 수 있다.

혹은 <이 한번씩 등장한다.

그래서 기본 횟수로 dp[i-1]+1 를 값으로 넣어주고, 비교를 해서 더 작은 값을 넣어주는것이다.

다이나믹 프로그래밍을 구현할때는 어떠한 값을 구한다기 보다는 정말 구해야되는 답을 위해서 편법을 쓴다는 생각으로 풀이해야하는것 같다..

package baekjoon.a1463;

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

public class a1463 {
    public static int count =0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] dp = new int[N+1];
        dp[0] =0;
        dp[1] =0;
        for(int i=2; i<=N;i++){
            dp[i] = dp[i-1]+1;
            if(i%2==0){
            dp[i]= Math.min(dp[i],dp[i/2]+1);
            }if(i%3==0){
                dp[i] = Math.min(dp[i],dp[i/3]+1);
            }
        }
        System.out.println(dp[N]);
    }
}

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

3
0
1
3

1 0
0 1
1 2

2
6
22

5 8
10946 17711

풀이

해당 문제는 다이나믹 프로그래밍으로 풀이하는 문제이다.

다이나믹 프로그래밍은 재귀용법과 관련지어서 생각해볼수 있는데,

재귀용법은 단순히 매 문제마다 더이상 풀 수 없을때까지 풀이하고 넘어간다면

다이나믹 프로그래밍은 메모이제이션 기법을 활용해서 매 문제의 답을 기억해두고 다음 문제를 풀이할때 그 답을 참고하여 풀이한다는 것이다.

기본적인 풀이에는 배열을 생성해 사용하는데,

해당 문제또한 마찬가지로 배열을 사용해 풀이할 수 있다.

그리고 작은 단계부터 점점 풀어나가서 답을 찾는 방식으로 풀이하면 된다.

일단 단순히 바로 답을 구할 수 있는 것들은 답을 저장해둔다.

값이 0이 들어오면 0을 반환하고, 1이 들어오면 1을 반환한다고 문제에 친절하게 힌트가 적혀있다.

해당 문제는 0이나 1을 몇번 출력하는지를 알고싶어하고, 40보다 작거나 같은 수라고 하니 0부터 40 , 즉 41개의 공간을 가진 배열을 생성해

미리 0과 1이 들어올때의 답을 배열에 넣어놓는다.

        Integer[][] arr = new Integer[41][2];
        arr[0][0] = 1;
        arr[0][1] = 0;
        arr[1][0] = 0;
        arr[1][1] = 1;

0일때 0이 반환되니 0번째의 0은 1, 1은 출력되지 않으니 0이 된다.

1일때는 0이 반환되지 않고 1만 반환되니 0 , 1 이 되는것이다.

0 과 1 의 답을 제시해주고 있으니 2부터 반복문을 돌려서  N번 반복하는 반복문을 실행하면 된다.

여기서 메소드를 호출하지 않고 배열로만 계산을 진행한다.

        for (int j = 0; j < N; j++) {
        int n = Integer.parseInt(br.readLine());
        for (int i = 2; i <= n; i++) {
            arr[i][0] = arr[i - 1][0] + arr[i - 2][0];
            arr[i][1] = arr[i - 1][1] + arr[i - 2][1];
        }

여기서 엄청 헷갈릴것이다.

피보나치를 머릿속으로 그리는것도 어려운데.. 반복문으로 저렇게 표현하고 있으니..

arr[i][0]  <- 이것은 피보나치(2)를 했을때 0이 출력되는 횟수가 된다.

arr[1][0] 은 아까 위에서 선언했듯이 0이 될것이고, arr[0][0]은 1이 된다.

그렇다.. 이것은 피보나치 함수의 결과값을 제출해야 하는것이 아닌 피보나치 함수(N) 을 실행했을때 1과 0이 몇번 출력되는지를 구하는것이다..!

package baekjoon.a1003;

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

public class a1003 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Integer[][] arr = new Integer[41][2];
        arr[0][0] = 1;
        arr[0][1] = 0;
        arr[1][0] = 0;
        arr[1][1] = 1;
        for (int j = 0; j < N; j++) {
        int n = Integer.parseInt(br.readLine());
        for (int i = 2; i <= n; i++) {
            arr[i][0] = arr[i - 1][0] + arr[i - 2][0];
            arr[i][1] = arr[i - 1][1] + arr[i - 2][1];
        }
            System.out.println(arr[n][0]+" "+arr[n][1]);
    }
    }

}

이렇게만 풀이하면 어렵게 생각하지 않고 풀이할 수 있다.