(문제보기)

0. 동적계획법의 이해

동적계획법이란 재귀함수를 여러번 호출하다보면 이전에 호출된 함수를 다시 호출하는 경우가 생긴다.

이를 좀더 효율적으로 계산하기 위한 방법이라고 생각하면 된다.

말로만 설명하면 이해하기 힘들기때문에 문제를 살펴보자. 바로 이해가 될 것이다.

1. 문제 분석

피보나치 수를 구하는 문제이다. 다만 기존의 방식에는 개선점이 있다.

위의 경우 fib(5)를 계산하는 과정이다.

재귀적으로 계속 계산하여 깊어지는데, 빨간색 동그라미를 친 부분을 살펴보자.

fib(2)를 구하는 과정인데, 맨 왼쪽에서 2를 구했음에도 불구하고 2번이나 fib(2)를 더 수행하였다.

따라서 이러한 불필요한 계산을 줄이고자 먼저 계산한 fib(2)를 저장하고 다음번에 사용할 때는 계산을 하지 않고 저장된 fib(2)의 값을 불러오자는 것이 동적 계획법의 아이디어다.

이 문제에서는 fib(N)을 계산할 때 0과 1을 몇번을 계산하는지를 묻는 문제이다.

처음에는 0과 1을 카운팅할 배열을 2개를 선언하였으나 시간초과로 인하여 풀지 못했다.

그러다 배열 하나로 풀 수 있도록 만들어주는 한가지 규칙이 있었는데,

각 배열은 앞의 두 수를 더한 값이 된다.

또한 각 배열을 묶어보면 0의 갯수와 1의 갯수로 나타난다.

4의 경우 0이 2, 1이 3개 나타난 모습이다.

이를 활용하여 문제를 해결했다.

2. 소스코드

// #1003

#include<stdio.h>

int array[42] = {1, 0, 1};

int fib(int num){
        if(array[num] != -1) return array[num];
        else if(num == 0)
                return 0;
        else if(num == 1)
                return 1;
        else{
                array[num] = fib(num-1) + fib(num-2);
                return array[num];
        }
}
int main(void){
        /* init array */
        for(int i=3; i<42; i++)
                array[i] = -1;

        int N, T;

        scanf("%d", &T);
        for(int i=0; i<T; i++){
                scanf("%d", &N);
                fib(N+1);
                printf("%d %d\n", array[N], array[N+1]);
        }
        return 0;
}

맨처음에는 배열 2개를 활용하여서 0과 1을 카운팅 하니까 시간초과로 문제를 풀지 못했는데 저러한 규칙을 이용하여서 푸니까 금방 풀렸다.

저런생각은 어떻게 하는지 대단하다..

(문제보기)

1. 문제 파악

기본적으로 제공하는 숫자 자료형은 범위가 정해져있기 때문에 그 범위를 벗어난 연산을 하는 문제이다.

문제에서의 범위는 10^10000, 즉 1하고 0이 만개정도 있는 범위에서의 계산을 처리해야한다.

기본적으로 생각한 방법은 다음과 같다.

계산해야 할 값을 문자열로 받고, 손으로 계산하듯이 계산한다.

이경우 다음과 같은 절차를 밟는다.

• 문자열 2개를 저장할 변수를 생성한다.
• 맨 끝번째 저장된 요소부터 계산을 하며 계산값이 10진수로 10을 넘을경우 다음 자릿수에 1을 더해준다.
• 마지막의 경우 할당된 메모리 영역에서 벗어나므로 flag 변수를 통하여 1을 표현해준다.

2. 소스코드

// #10757

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int main(void){
        char* L = (char*)malloc(sizeof(char)*10002);
        char* S = (char*)malloc(sizeof(char)*10002);
        int flag = 0;
        scanf("%s %s", L, S);

        int len_l, len_s;
        len_l = strlen(L);
        len_s = strlen(S);

        /* swap var */
        if(len_l < len_s){
                int temp = len_l;
                len_l = len_s;
                len_s = temp;

                char* p_temp = L;
                L = S;
                S = p_temp;
        }

        for(int i=0; i<len_l; i++){
                if(i < len_s)
                        *(L+len_l-1-i) += *(S+len_s-1-i)-48;
                if(*(L+len_l-1-i) > 57){
                        *(L+len_l-1-i) -= 10;
                        if(i == len_l-1) flag = 1;
                        else *(L+len_l-2-i)+=1;
                }
        }

        if(flag) printf("1");

        for(int i=0; i<len_l; i++)
                printf("%c", *(L+i));
        return 0;
}

for문의 경우 리버스 인덱싱을 활용하는데, 소스코드를 너무 복잡하게 짠 것 같다.

리버스 인덱싱을 좀더 깔끔하게 구현하도록 노력해야겠다는 생각이 들었다.

(문제보기)

1. 문제 설명

N을 받고, 1부터 N까지의 카드를 쌓는다. 맨 위에 있는 카드는 1이다.

여기서 마지막 한장이 남을때까지 다음의 동작을 반복한다.

• 맨위의 카드를 버리고, 그 다음 카드는 카드뭉치의 맨 밑으로 넣는다.

이는 잘 생각해보면 큐에서 dequeue를 수행하고, 그 다음 값을 dequeue한다음 그 값을 다시 enqueue 한것과 같은 동작이다.

말이 복잡해졌는데 도식화 하면 다음과 같다.

마지막 한장이 남을때까지 반복하고, 한 사이클마다 한장의 카드가 버려지니 pop, pop&push를 N-1번 반복하면 될것이다.

2. 소스코드

// 2164.c

#include<stdio.h>
#include<stdlib.h>

typedef struct Node{
        int data;
        struct Node* next;
}node;

node* queue = NULL;
node* back = NULL;

void push(int data){
        node* new_node = (node*)malloc(sizeof(node));
        new_node->next = NULL;
        new_node->data = data;

        /* empty queue */
        if(queue == NULL){
                queue = new_node;
                back = new_node;
        }
        /* else */
        else{
                back->next = new_node;
                back = new_node;
        }
}

int pop(){
        if(queue == NULL) return -1;

        node* temp = queue;
        queue = queue->next;

        /* save data */
        int ret = temp->data;

        free(temp);
        return ret;
}

int main(void){
        int N;
        scanf("%d", &N);

        /* set data */
        for(int i=0; i<N; i++)
                push(i+1);

        /* pop & push */
        int temp;
        for(int i=0; i<N-1; i++){
                pop();
                temp = pop();
                push(temp);
        }

        printf("%d\n", queue->data);
}

1. 들어가기

우리는 앞선 포스팅에서 스택과 큐에 대하여 간단하게 살펴보았다.

혹시나, 앞 포스팅을 보지 않았더라면 배열파트부터 살펴보는 것을 추천한다.

배열과 링크드리스트를 모른다면 자료구조는 시작할 수 없다.

2.  본론

이번에는 앞에서 배운 자료구조를 응용해보자 한다.

다만, 앞서서 살펴본 간단한 예제들과는 사뭇 다른 느낌이 들것이다.

이는 다음과 같은점 때문이라고 생각한다.

• 이론에서 응용으로의 문제
• 각종 예외처리에 대한 문제

pop, push에 대해서 null pointer 에대한 접근으로 인하여 생기는 segmentaion fault가 자주 발생 할 것이다.

통칭 세그폴트라고 불리는 저 오류는 자료구조를 공부할 때 정말 많이 나올 것이다.

따라서 여러분이 세그폴트를 만났을 때, null pointer에 접근하지 않는지 살펴보면 대부분 해결 될 것이다.

3. 각종 예제

백준 온라인 저지에 있는 스택, 큐,덱 카테고리의 문제를 살펴보자.

exiis-programming.tistory.com/category/%EB%B0%B1%EC%A4%80%20%EC%98%A8%EB%9D%BC%EC%9D%B8%20%EC%A0%80%EC%A7%80%20-%20%EB%8B%A8%EA%B3%84%EB%B3%84%EB%A1%9C%20%ED%92%80%EC%96%B4%EB%B3%B4%EA%B8%B0/%EC%8A%A4%ED%83%9D

exiis-programming.tistory.com/category/%EB%B0%B1%EC%A4%80%20%EC%98%A8%EB%9D%BC%EC%9D%B8%20%EC%A0%80%EC%A7%80%20-%20%EB%8B%A8%EA%B3%84%EB%B3%84%EB%A1%9C%20%ED%92%80%EC%96%B4%EB%B3%B4%EA%B8%B0/%ED%81%90%2C%20%EB%8D%B1

(문제보기)

1. 문제분석

이전에 풀었던 문제 ( www.acmicpc.net/problem/1920 )와 거의 다를게 없는 문제이다.

차이점이 있다면 다음과 같다.

1. N에서 중복 입력 허용한다.

2. M에서 받은 각 수에 대하여 N에서 몇번 나왔는지 센다.

즉, 예를 들어보면

5

[ 1 1 1 1 2 ]

3

[ 1 2 3 ]

-> [ 4 1 0 ]

1 - 4번

2 - 1번

3 - 0번

나왔다는 의미이다.

이전 문제에서 각 노드에 count라는 변수를 추가하였다.

도식화 하면 다음과 같아진다.

7

[ 5 3 7 4 1 1 1 ]

5

[1 3 4 5 7 ]

의 입력을 살펴보자.

먼저 [ 5 3 7 4 1 ] 까지의 입력은 위의 트리 모양을 구성해준다.

여기서 남은 [ 1 1 ]이 관건인데, 이를 위하여 count 라는 새로운 변수를 생성했다.

만약, 기존 tree에 존재했던 값이 트리에 추가 될 경우 노드를 추가하지 않고 그 노드의 count를 1 증가시킨다.

따라서 마지막 1값을 가지고 있는 node는 값이 1 + 1 + 1 이 되었다. ( 1이 3번 insert 됨 )

2. 소스코드

// #10816

#include<stdio.h>
#include<stdlib.h>


typedef struct Node{
        int count;
        int data;
        struct Node* left;
        struct Node* right;
}node;

node* root = NULL;

void insert(int num){
        node* new_node = (node*)malloc(sizeof(node));
        new_node->data = num;
        new_node->left = NULL;
        new_node->right = NULL;
        new_node->count = 1;

        if(root == NULL)
                root = new_node;
        else{
                node* temp = root;
                /* find node */
                while(1){
                        /* already exist */
                        if(temp->data == num){
                                (temp->count)++;
                                return;
                        }

                        if(temp->data > num){
                                if(temp->left == NULL){
                                        temp->left = new_node;
                                        break;
                                }
                                else
                                        temp = temp->left;
                        }
                        else{
                                if(temp->right == NULL){
                                        temp->right = new_node;
                                        break;
                                }
                                else
                                        temp = temp->right;
                        }
                }
        }
}

void find(int num){
        if(root == NULL) return;
        node* temp = root;
        while(temp != NULL){
                if(temp->data == num){
                        printf("%d ", temp->count);
                        return;
                }
                else if(temp->data > num)
                        temp = temp->left;
                else
                        temp = temp->right;
        }
        printf("0 ");
}

int main(void){
        int N, M;
        int num;

        /* input */
        scanf("%d", &N);
        for(int i=0; i<N; i++){
                scanf("%d", &num);
                insert(num);
        }

        /* find */
        scanf("%d", &M);
        for(int i=0; i<M; i++){
                scanf("%d", &num);
                find(num);
        }
        printf("\n");

        return 0;
}

이전문제와 유사해서 큰 어려움은 없을 것이라 생각한다.

(문제보기)

1. 문제 분석

문제는 간단하다.

N이 입력되고 N개의 정수, M이 입력되고 M개의 정수를 받는다.

먼저 입력된 N개의 정수 중에 뒤에 입력된 M개의 정수가 있는지 확인 하는 문제이다.

ex)

3

[ 1 2 3 ]

5

[ 1 3 5 7 9 ]

1, 3, 5 ,7, 9 중 1, 3이 존재하므로 출력은 다음과 같다.

[ 1 1 0 0 0 ]

이분 탐색의 카테고리인만큼 바이너리 서치 트리를 이용하여 구현했다.

2. 소스코드

// #1920

#include<stdio.h>
#include<stdlib.h>


typedef struct Node{
        int data;
        struct Node* left;
        struct Node* right;
}node;

node* root = NULL;

void insert(int num){
        node* new_node = (node*)malloc(sizeof(node));
        new_node->data = num;
        new_node->left = NULL;
        new_node->right = NULL;

        if(root == NULL)
                root = new_node;
        else{
                node* temp = root;
                /* find node */
                while(1){
                        if(temp->data > num){
                                if(temp->left == NULL){
                                        temp->left = new_node;
                                        break;
                                }
                                else
                                        temp = temp->left;
                        }
                        else{
                                if(temp->right == NULL){
                                        temp->right = new_node;
                                        break;
                                }
                                else
                                        temp = temp->right;
                        }
                }
        }
}

void find(int num){
        if(root == NULL) return;
        node* temp = root;
        while(temp != NULL){
                if(temp->data == num){
                        printf("1\n");
                        return;
                }
                else if(temp->data > num)
                        temp = temp->left;
                else
                        temp = temp->right;
        }
        printf("0\n");
}

int main(void){
        int N, M;
        int num;

        /* input */
        scanf("%d", &N);
        for(int i=0; i<N; i++){
                scanf("%d", &num);
                insert(num);
        }

        /* find */
        scanf("%d", &M);
        for(int i=0; i<M; i++){
                scanf("%d", &num);
                find(num);
        }

        return 0;
}

값을 찾는다면 1, 못찾으면 0을 출력한다.

크게 어려움 없는 문제이다.