JArchive 프로그래밍 일기

문제

카드구매하기2 백준 16194번

리뷰

이전에 풀었던 카드구매하기 문제와는 반대로 '최소값'을 구하는 문제다.

[P[i] 에는 카드팩의 값을 저장한다.

MinCost[i] 에는 i장을 샀을 때의 최소값을 저장하는데, 처음에는 P[i] 값을 저장하고 시작한다.

4장을 산다면,

MinCost[1] + P[3] 와 MinCost[4] 를 비교한다.

MinCost[2] + P[2] 와 MinCost[4] 를 비교한다.

MinCost[3] + P[1] 와 MinCost[4] 를 비교한다.

코드

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

int P[10001];
int MinCost[1001];

int main(void){

    freopen("input.txt", "rt", stdin);

    int n = 0, input = 0;

    scanf("%d", &n);

    for(int i = 1; i <= n; i++){
        scanf("%d", &input);
        P[i] = input;
    }    

    MinCost[1] = P[1];    

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

        MinCost[i] = P[i];

        for(int j = 1; j <= i; j++){

            int temp = min(MinCost[i], MinCost[i-j] + P[j]);

            if(temp < MinCost[i]){
                MinCost[i] = temp;
            }
        }
    }

    printf("%d", MinCost[n]);

    return 0;
}

문제

1,2,3 더하기 백준 9095번

리뷰

정수 1 부터 "1, 2, 3 의 합으로 나타내는 방법의 수" 를 전부 적어봤다.

정수 i의 경우, 방법의 수를 D[i] 에 저장한다.

D[1] = 1

D[2] = 2

D[3] = 4

D[4] = 7

D[5] = 13

이렇게 되니까, 7 = 4 + 2 + 1 이었고, 13 = 7 + 4 + 2 였다.

[ 점화식 ]

D[i] = D[i-1] + D[i-2] + D[i-3]

코드

#include <stdio.h>
using namespace std;

int arr[12];

int sum_case(int num){

    int i = 0;

    for(i = 4; i <= num; i++){
        arr[i] = arr[i-1] + arr[i-2] + arr[i-3];
    }

    return arr[num];
}

int main(void){

    freopen("input.txt", "rt", stdin);

    int test_case = 0, num = 0;

    scanf("%d", &test_case);

    arr[1] = 1;
    arr[2] = 2;
    arr[3] = 4;

    while(test_case--){
        scanf("%d", &num);
        printf("%d\n", sum_case(num));
    }

    return 0;
}

문제

이친수 백준 2193번

리뷰

0 뒤에는 0, 1 둘 다 올 수 있고, 1 뒤에는 반드시 0이 와야한다. (1이 연속되면 안되는 규칙 때문)

앞서 풀었던 쉬운계단수문제 와 비슷한 아이디어로 풀었다.

N자리 수의 마지막 자리 숫자가 0인 경우, N자리 수의 마지막 자리 숫자가 1인 경우의 규칙을 찾는 것이다.

1자리, 2자리 , ... 7자리 까지 이친수 경우를 써보면 발견할 수 있었다.

1자리 -> 1 arr[1] [1] = 1

2자리 -> 10 arr[2] [0] = 1

3자리 -> arr[3] [0] = 1 , arr[3] [1] = 1 100, 101

4자리 -> arr[4] [0] = 2, arr[4] [1] = 1 1000, 1001, 1010

5 자리 -> arr[5] [0] = 3, arr[5] [1] = 2 10010, 10001, 10000, 10101, 10100

6자리 -> arr[6] [0] = 5, arr[6] [1] =3

아래와 같은 점화식을 만들 수 있다.

    arr[i][0] = arr[i-1][0] + arr[i-2][0];
    arr[i][1] = arr[i-1][0];

코드

#include <stdio.h>
using namespace std;

 // 이친수 (2193)

long long arr[91][2];

int main(void){

    int n = 0;
    int i = 0;

    scanf("%d", &n);

    arr[1][1] = 1;

    arr[2][0] = 1;

    arr[3][0] = 1;
    arr[3][1] = 1;

    for(i = 4; i <= n; i++){
        arr[i][0] = arr[i-1][0] + arr[i-2][0];
        arr[i][1] = arr[i-1][0];
    }

    printf("%lld", arr[n][0] + arr[n][1]); // 답 출력할 때 long long 자료형 

    return 0;
}

문제

오르막 수 백준 11057번

리뷰

'쉬운 계단 수' 문제 보다 고려할 것이 적었다.

숫자가 반드시 1씩 연속되어야 하는것도 아니고, 인접한 수가 같아도 오름차순으로 친다.

ex) 2234, 3678, 11119

[ 점화식 ]

자리수 N의 숫자들의 마지막 자리 숫자가 L이라고 한다.

**arr [2] [3] 은 2자리 숫자 중에 마지막 자리 숫자가 3인 계단 수의 개수다. ex) 13, 23, 33

arr [N] [L] 을 구할 때, arr[N-1] [k]의 개수를 누적하는데, 이 때 k는 0부터 j이다.

2자리 숫자들 중에 마지막 자리 숫자가 '7' 이라면, k는 0부터 7까지다.

arr [N] [L] = arr [N-1] [0] + arr [N-1] [1] + arr [N-1] [2] + ... + arr [N-1] [6] + arr [N-1] [k]

오르막 수는 0부터 시작 가능하다.

코드

#include <stdio.h>
using namespace std;

// 오르막 수  (BOJ 11057) 

int arr[1001][10];

int main(void){

    freopen("input.txt", "rt", stdin);

    int n = 0, i = 0, j = 0;
    int sum = 0;

    scanf("%d", &n);

    for(i = 0; i <= 9; i++){ // 1자리 수는 전부 1개  
        arr[1][i] = 1;
    }

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

        for(j = 0; j <= 9; j++){ // 0 부터 시작 가능 

            for(int k = 0; k <= j; k++){ 
                // j=3 이라면, 마지막 수k로 0, 1, 2, 3 올 수 있다.  
                arr[i][j] += arr[i-1][k];
            }    

            arr[i][j] %= 10007;
        }    
    }

    for(i = 0; i <= 9; i++){
        sum += arr[n][i];
    }    

    printf("%d", sum % 10007);

    return 0;
}

문제

쉬운 계단 수 백준 10844번

리뷰

자리수 N이 1일 때, 2일 때의 계단 수들을 써봤다.

자리수 마다의 계단 수 합계에 규칙성이 있을 것 같았는데, 그렇지 않았다.

'0'은 반드시 앞에 1이 와야 하는 제한이 있고, ex) 10, 210

'9'는 반드시 앞에 8이 와야 하는 제한이 있었다. ex) 89, 789

0, 9와는 달리, '1'은 앞에 2가 와도 되고 0이 와도 된다. (이렇게 1부터 8까지는 제한이 없다.)

마지막 자리 숫자가 L인 계단수가 몇개인지를 기준으로 점화식이 필요하다.

[ 점화식 ]

자리수 N의 숫자들의 마지막 자리 숫자가 L이라고 한다.

arr [2] [3] 은 2자리 숫자 중에 마지막 자리 숫자가 3인 계단 수의 개수다. ex) 23, 43 이 된다.

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

이 때, L의 범위는 1 <= L <= 8 이다.

왜냐하면 '0'은 앞에 1이 와야만 하고, '9'는 앞에 8이 와야만 하니까 따로 관리한다.

(계단 수는 0으로 시작하지 않음)

1자리 수과 2자리 수의 계단 수 개수

2자리 수 중에서(N = 2) , 마지막 자리 숫자가 2인 경우(L = 2)를 보면, 12와 32가 있다.

2 앞에는 1과 3이 올 수 있다.

즉, 1자리 숫자에서 마지막 자리 숫자가 1인 계단수의 개수, 마지막 자리 숫자가 3인 계단수의 개수 가 몇 개냐에 따라 결정된다.

식으로 정리하면 , arr [2] [2] = arr [1] [1] + arr [1] [3]

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

그리고 유의할 점.

1000000000 으로 나눈 값을 출력해야 하니까, 배열에 저장할 때 부터 mod 연산을 해야 한다.

처음에는 sum을 int로 선언했었는데, 1000000000 때문에 long long을 바꾸니까 맞았다.

코드

#include <stdio.h>
#define MODNUM 1000000000 
using namespace std;

int arr[101][11];

int main(void){

    int n = 0, i = 0, j = 0;
    long long sum = 0;

    scanf("%d", &n);

    for(i=1; i<=9; i++){  // 0을 제외한 1자리 수들은 모두 계단 수가 1개.
        arr[1][i] = 1;
    }

    for(i = 2; i <= n; i++){ //  n : 몇 자리 수 인지  

        for(j=0; j <= 9; j++){ //  숫자의 마지막 자리 수  

            if(j == 0) 
                arr[i][0] = arr[i-1][1] % MODNUM;
            else if(j == 9) 
                arr[i][9] = arr[i-1][8] % MODNUM;
            else 
                arr[i][j] = ( arr[i-1][j-1] + arr[i-1][j+1] ) % MODNUM;
        }
    }

    for(i = 0; i <= 9; i++){  
        sum += arr[n][i];
    }

    printf("%lld", sum % MODNUM); // 마지막에 mod 연산 

    return 0;
}

문제

카드 구매하기 백준 11052번

리뷰

유념해야 할 것은 카드 i개 들어있는 카드팩 가격이 P[i] 원 이라는 것이다.

점화식을 세우는 게 쉽지 않았다.

입력받은 카드팩 가격 배열 P[i]와 i장 샀을 때 최대값을 기억하는 배열 M[i]를 사용한다.

예제 입력 n = 4 , P[i] = [1, 5, 6, 7] 일 때, 예제 출력은 10이다.

카드 a 장을 살 때 최대 지불하는 금액을 배열 M[a] 에 넣고, 최종 답 M[n]을 구한다.

M[1] = max(P[1], M[1])

M[2] = max(M[1] + P[1] , M[2])

i = 5 인 경우,

M[1] + P[4], M[2] + P[3], M[3] + P[2] , M[4]+P[1] 인 경우를 비교해야 한다. -> 2중 for문

코드

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

// 카드 구매하기  (BOJ 11052) 

vector<int> P(10001);
int max_value[1001];

int main(void){

    freopen("input.txt", "rt", stdin);

    int n = 0, num = 0;
    int i = 0, j = 0;

    scanf("%d", &n);

    for(i = 1; i <= n; i++){
        scanf("%d", &num);
        P[i] = num;
    } // 카드팩 n개의 값을 입력받는다. 

    for(i = 1; i <= n; i++){

        for(j = 1; j <= i; j++){ //   

            max_value[i] = max(max_value[i-j] + P[j], max_value[i]);

        }
    }

    printf("%d", max_value[n]);

    return 0;
}

펜윅 트리

Fenwick Tree, Binary Indexed Tree(BIT) 라고도 한다.

구간 트리는 구간 합을 빠르게 구하는 데 주로 사용된다. 구간 트리의 진화형태가 펜윅 트리다.

펜윅 트리의 아이디어

"구간 합 대신, 부분 합만을 빠르게 구하는 자료구조를 만들어 두면 구간 합을 계산할 수 있다"

구간 합(range sum) : [3, 6] 과 같은 연속된 구간 합

부분 합(partial sum) : [0, 3] , [0, 8] 과 같이 0번 부터 i까지 합

부분 합 psum의 표현 psum[pos] = A[0] + A[1] + A[2] + ... + A[pos] 로 표현할 수 있다.

구간 [3, 6] 에 대한 합은 psum[6] - psum[2] 로 계산할 수 있다.

구간 [i, j] 에 대한 합은 psum[j] - psum[i-1] 로 계산할 수 있다.

구간 트리와 펜윅 트리의 비교

부분 합(0부터 i까지의 합)만 구한다면, 구간 트리가 미리 계산해 저장하는 상당 수는 필요가 없다.

그림 (a) 는 구간트리, (b)는 펜윅 트리이다.

즉, 하나의 긴 구간 밑에 두 개의 작은 구간이 있을 때 두 구간 중 오른쪽 구간은 항상 지워도 된다.

펜윅 트리는 이 대응을 이용해 1차원 배열 하나에 각 구간의 합을 저장한다.

공간복잡도 O(n)

tree[i] = 그림 (b)에서 오른쪽 끝 위치가 A[i]인 구간의 합

구간 합 을 어떻게 계산할까?

A[pos] 까지의 구간합 psum[pos]를 계산하고 싶으면 그림 (b)에서 pos에서 끝나는 구간의 합 tree[pos]를 답에 더한다.

즉, 그림 (b)에서 색칠한 구간 tree[12], tree[11], tree[7]들은 psum[12]를 계산하기 위해 더해야 하는 구간들이다.

• 어떤 부분 합을 구하든 O(logN) 개의 구간 합만 있으면 된다

pos에서 끝나는 구간 다음으로 더해야 할 구간을 어떻게 찾을까?

• 이제 문제는 pos에서 끝나는 구간 다음으로 더해야 할 구간을 어떻게 찾을까 하는 것입니다.
• 펜윅 트리는 각 숫자의 이진수 표현을 이용해 이 문제를 해결합니다.
• 우선 이진수 표현을 위해 배열 A[]와 tree[]의 첫 원소의 인덱스를 1로 바꾼다.
• 모든 원소의 인덱스에 1을 더해 주는 것이다.

각 구간의 길이는 이진수 표현에서 오른쪽 끝에 있는 0의 개수가 하나 늘 때마다 두 배로 늘어난다.

• psum[7]을 구하기 위해 더해야 하는 숫자는
  • 7에서 끝나는 구간의 합 tree[7] 111
  • 6에서 끝나는 구간의 합 tree[6] 110
  • 4에서 끝나는 구간의 합 tree[4] 100
• 오른쪽 끝 위치의 이진수 표현에서 마지막 비트를 지우면 다음 구간을 쉽게 찾을 수 있음

펜윅 트리 초기화

펜윅 트리를 처음 생성하면 모든 부분 합이 0으로 초기화되므로, 모든 원소가 0인 배열을 표현하게 된다.

• ex) A[5]를 3 늘리고 싶다. 이때 늘려 줘야 할 값들은
  • tree[5] 101
  • tree[6] 110
  • tree[8] 1000
  • tree[16] 10000
• 다른 경우들도 하나하나 시도해 보면 맨 오른쪽에 있는 1인 비트를 스스로에게 더해 주는 연산을 반복하면 해당 위치를 포함하는 구간들을 모두 만날 수 있음
• 예를 들어 110 에서 가장 오른쪽에 있는 비트는 10 이므로, 이를 스스로에게 더하면 1000을 얻을 수 있음

// 펜윅 트리의 구현. 가상의 배열 A[]의 부분 합을 빠르게 구현할 수 있도록 한다. 
// 초기화시에는 A[]의 원소가 전부 0이라고 생각한다.
struct FenwickTree{
    vector<int> tree;
    FenwickTree(int n) : tree(n+1) {}
    // A[0 .. pos]의 부분 합을 구한다.
    int sum(int pos){
        // 인덱스가 1부터 시작한다고 생각 (비트연산 활용을 위해서)
        ++pos;
        int ret = 0;
        while(pos > 0){
            ret += tree[pos];
            // 다음 구간을 찾기 위해 최종 비트를 지운다
            pos &= (pos-1);
        }
        return ret;
    }
    // A[pos]에 val을 더한다
    void add(int pos, int val){
        ++pos;
        while(pos < tree.size()){
            tree[pos] += val;
            pos += (pos & -pos); // -pos : 음수 표현을 위해 비트별 NOT연산을 하고 1을 더한다
        }
    }
};

참고

beakjoon 펜윅트리 포스팅

펜윅트리 vs 구간트리

알고리즘 문제해결전략 (구종만 저)