꿈을 보는 개발자

10844번: 쉬운 계단 수 (acmicpc.net)

쉬운 계단 수 문제였지만 마냥 쉽지만은 않았습니다. 우선 2차원 배열을 활용하여서 자리수가 낮은 수부터 결과값을 갱신해 나가는 형태를 보였습니다. 2차원 배열을 활용한 이유는 자리수와 자리수에 나오는 숫자에 따라서 결과가 나누어 지기때문에 자리수와 자리수에 나오는 숫자에 따른 결과를 구분해주기 위해서 2차원 배열을 사용했습니다. 

이때, 문제가 되는 부분은 숫자 0과 9입니다. 숫자가 0일 경우 다음에 나올 수는 계단수 조건을 충족하기 위해서는 1만 나오고 9일 경우에는 8만 나올수 있습니다. 따라서 값을 갱신 할 때, 이 두개의 숫자가 나올 경우의 조건을 따로 설정해주어야할 필요가 있었습니다. 

Bottom - up 방식을 통해서 아래의 코드를 작성하였습니다. 

package com.company;

import java.util.Scanner;




public class Main {
    static long number[][] = new long[101][10];

    public static long cal(int level , int num){

        long sum = 0;
        for(int i =1; i<10; i++){
            number[1][i] = 1;
        }

        for(int i=2; i<=level; i++){
            for(int j = 0; j<num; j++){
                if(j == 0){
                    number[i][j] = (number[i-1][1])%1000000000;
                }
                else if(j == 9){
                    number[i][j] = (number[i-1][8])%1000000000;
                }
                else{
                    number[i][j] = (number[i-1][j+1] + number[i-1][j-1])%1000000000;
                }
            }
        }

        for(int k =0; k<10; k++){
            sum += number[level][k];
        }
        return sum;
    }



    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
            System.out.println(cal(n,10)%1000000000);
    }
}

이때, 값을 갱신해줄 때마다 문제의 조건처럼 1000000000의 나머지값을 갱신 해주었습니다. 

부족했던 점

이전과 같이 Top-down 방식으로 풀어보고 싶었으나 갈피를 잡지 못하였습니다. 계속 생각해도 풀리지 않아서 다른 풀이를 참고하여서 2차원 배열을 사용해야 함을 알았고 이를 통해서 문제를 풀어나갔습니다. 위와 비슷한 경우의 문제도 이를 참고하여서 풀 수 있어야 합니다. 

9095번 제출 (acmicpc.net)

적절한 점화식을 찾는것이 중요합니다. 1,2,3만을 통해서 합을 나타내는 수를 출력해야하므로 4에 대한 합을 찾는다 가정하였을때 

4일 경우 경우의 수는 

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

즉, 7 = 4 + 2 + 1 -> f(4) = f(3) + f(2) + f(1)다음과 같이 바꿀 수 있습니다. 

5일 경우까지 해본다면, 

• 1+1+1+1+1
• 2+1+1+1
• 1+2+1+1
• 1+1+2+1
• 1+1+1+2
• 2+2+1
• 2+1+2
• 1+2+2
• 3+1+1
• 1+3+1
• 1+1+3
• 3+2
• 2+3

총 13가지가 나오고 

13 = 7 + 4 +2 -> f(5) = f(4) + f(3) + f(2)라는 결과가 나옵니다.

점화식으로는  f(n) = f(n-1) + f(n-2) + f(n-1)으로 나타 낼 수 있습니다. 이를 재귀방식으로 코드를 짠다면,

package com.company;

import java.util.Scanner;




public class Main {
    static int result[] = new int[1001];

    public static int cal(int n){

        result[0] = 1;
        result[1] = 1;
        result[2] = 2;
        result[3] = 4;

        if(result[n] != 0 ){
            return  result[n];
        }
        else {
            result[n] = (cal(n - 1) + cal(n - 2) + cal(n-3)) % 10007;
        }

        return result[n];
    }



    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int i = 0; i<n; i++){
            int num = sc.nextInt();
            System.out.println(cal(num));
        }


    }
}

다음과 같은 코드를 만들 수 있습니다. 

본 문제는 2xn 타일링 문제입니다. 이 문제의 핵심은 적절한 점화식을 찾아내는 것입니다.

11726번: 2×n 타일링 (acmicpc.net)

우선 그림으로 타일들을 나타낸다면,

다음과 같은 패턴을 볼 수 있습니다. 이 경우에 점화식을 찾아내게 된다면 

F(n) = F(n-1) +F (n-2) 의 점화식을 구할 수 있고 이를 이번에는 재귀함수를 통해서 TOP-DOWN 방식을 통해 풀어내게 된다면, 다음과 같은 코드가 나오게 됩니다.

package com.company;

import java.util.Scanner;

public class Main {
    static int result[] = new int[1001];

    public static int domino(int n){

        result[0] = 1;
        result[1] = 1;
        result[2] = 2;

        if(result[n] != 0){
            return result[n];
        }
        else{
            result[n] = (domino(n-1) + domino(n-2))%10007;
        }

        return result[n];
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(domino(n)%10007);

    }
}

이와 연계 하여서 11727문제도 점화식 변경하는 식으로 풀어냈습니다. 

11727번: 2×n 타일링 2 (acmicpc.net)

부족했던 점

처음 시도를 하였을때는 아래의 코드와 같이

package com.company;

import java.util.Scanner;




public class Main {
    static int result[] = new int[1001];

    public static int domino(int n){

        result[0] = 1;
        result[1] = 1;
        result[2] = 2;
        if(n == 0) return result[0];
        if(n == 1) return result[1];
        if(n == 2) return result[2];


        result[n] = (domino(n-1) + domino(n-2))%10007;


        return result[n];
    }



    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(domino(n)%10007);

    }
}

이미 결과값을 구한 배열일때도 연산을 다시 하도록 해주서어서 시간이 더 오래걸려 시간제한조건을 충족하지 못했습니다. 이를 해결하기 위해서 점화식 결과값을 리턴하기전 다음과 같은 조건을 삽입해주 이미 배열속에 값이 있는 경우에는 바로 값을 리턴해주도록 하였습니다. 

        if(result[n] != 0){
            return result[n];
        }

1463번: 1로 만들기 (acmicpc.net)

처음으로 풀어볼 DP문제입니다. 

우선은 DP문제이기 때문에 인접한 값들의 영향을 받는 구조가 나옵니다.

따라서 해당 문제에 해당하는 알맞은 점화식을 구하는 것을 가장 최우선으로 생각했습니다.

정수 X에 대하여 사용할 수 있는 연산은 

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

최소값을 구하기 위해서 가장 먼저 생각했던것은 숫자를 3으로 최대한 나누고 2로 최대한 나눈후 1로 빼는 방식을 사용했습니다. 다만, 10일 경우에는 최우선으로 10에 1을 빼고 계산을 하는 것이 2로 먼저나누는 경우보다 더 적은 연산값을 가집니다. 

그렇기 때문에 이같은 방식 보다 2부터 시작하여서 2나 3으로 나누어지기전 1을 빼는 연산을 하는 경우를 미리 결과값을 넣어줄 배열에 넣어놓은후 min 함수를 통해서 2혹은 3으로 나누는 경우와 -1을 하는 경우의 최소값을 구해서 연산값이 더 적은 경우를 선택하는 방식을 사용하였습니다. 

package com.company;

import java.util.Scanner;
import java.lang.Math;



public class Main {

    public static int one(int n){
        int num[] = new int[n+1];
        num[0] = 0;
        num[1] = 0;

        for(int i=2; i<=n; i++){

            num[i] = num[i-1] + 1; 
            if(i%2 == 0){ num[i] = Math.min(num[i], num[i/2]+1); }
            if(i%3 == 0){ num[i] = Math.min(num[i], num[i/3]+1); }

        }
        return num[n];
    }



    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(one(n));

    }
}

알고리즘 문제 풀이 (tistory.com)

위의 글처럼 

알고리즘 문제 풀이 (tistory.com)

해당 블로그의 커리큘럼에 따르면서 문제풀이를 하고자 합니다. 

가장 처음으로 시작할 부분은 입출력 파트입니다.

간단해보였지만 문제풀이를 하면서 프로그래밍언어별로 각각 조금씩 다른 언어들의 특징들을 알아보고 해당언어에 적응해나가기에 아주 좋은 문제들이었다고 생각합니다. 

<입출력>

2557, 1000, 2558, 10950, 10951, 10952, 10953, 11021, 11022, 11718, 11719, 11720, 11721, 2741, 2742, 2739, 1924, 8393, 10818, 2438, 2439, 2440, 2441, 2442, 2445, 2522, 2446, 10991 10992

입출력관한 문제들을 풀어보았습니다. 

입출력파트를 풀어보면서 막히거나 크게 부족한 점은 없었지만 중간중간 짚고 넘어갈 부분이 있었기에 해당 파트는 

통합해서 개인적으로 알아두어야 할 점을 적어보자 합니다. 

• 10951

글 읽기 - ★☆★☆★ [필독] A+B - 4 FAQ ★☆★☆★ (acmicpc.net)

해당 파트는 프로그래밍 언어별 EOF가 어떻게 처리되는가에 대한 문제였습니다. 언어별로 다르게 표현되는 EOF에 대해서 알아두어야 합니다. 또한, try - catch와 같은 예외처리가 필요한 경우도 있습니다. 

• 10953

해당 파트는 string토큰 분리에 관한 내용이였습니다. 파이썬, 자바등 다양한 언어에서 다른 방식을 사용하고 있기때문에 언어별로 한번씩 알아두면 좋을것 같습니다. 

• 1720

비슷한 유형입니다. 제가 사용한 java의 경우에는 

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n;
        int result = 0;
        String st;
        n = sc.nextInt();

        st = sc.next();
// nextline()하면 에러

        for(int i = 0; i < n; i++){

            result += st.charAt(i) - '0';
        }
        System.out.println(result);
        }
    }

다음과 같이 next , nextline에 따라서 결과가 달라졌습니다. 

이 밖에도 배열선언 및 이용 별찍기 문제들을 통한 반복문 사용등으로 기본적인 알고리즘 뿐 만 아니라 언어별 특성에 관해서도 간단하게 다루어 보기 좋은 문제들이었습니다.

알고리즘 문제풀이를 할 게시판 입니다. 

앞으로 포스팅할 알고리즘 커리큘럼은 

plzrun's algorithm :: 알고리즘 문제풀이(PS) 시작하기 (tistory.com)

해당 블로그의 커리큘럼을 따라가겠습니다!

해당 게시판에서는 이런식으로 커리큘럼별로 카테고리를 만들고 포스팅해나가고자 합니다.

부족한 실력이기에 다른분들에게 해답을 알려주기 위한 포스팅보다는 개인적으로 부족하다고 생각하거나 피드백 해야 할 부분을 소스코드와 함께 포스팅해 나가도록 하고자 합니다!