Nefus - C언어 [BOJ 11729, 24060]

 

 

제가 어려웠던 2개의 문제는 Baekjoon - 11729, Baekjoon - 24060 입니다.

 

 

Baekjoon - 11729

https://www.acmicpc.net/problem/11729

 

이 문제는 하노이탑에 대한 원리를 파악해야하고 원판을 어떤식으로 옮겨야 하는지에 대해서 고민하였고, 이 과정이 생각보다 어려워 추가한 문제입니다.

 

 

#include <stdio.h>

void hanoi(int a, int b, int c, int n){ // a=시작지점, b=중간지점, c=마지막지점, n=원판개수
    if(n==1){
        printf("%d %d\n",a,c);
        return;
    } else {
        hanoi(a,c,b,n-1);
        printf("%d %d\n",a,c);
        hanoi(b,a,c,n-1);
    }
}

void hanoi_count(int n){ // 하노이탑 최소 이동 횟수
    int cnt=2;
    if(n==1){
        cnt=1;
        printf("%d\n", cnt);
        return;
    }

    for(int i=2;i<=n;i++){
        cnt *= 2;
    } cnt-=1;
    printf("%d\n", cnt);
}

int main(){
    int n;
    scanf("%d", &n);
    hanoi_count(n);
    hanoi(1,2,3,n);
}

 

- main 함수

main에서 n을 입력받게 되는데 이는 원판 개수를 의미합니다.

 

- hanoi_count 함수

이 함수에서는 하노이탑의 최소 이동 횟수를 계산하는 코드입니다.

하노이탑에서 '원판 개수 : 최소 이동 횟수' 로 나타내면 '1 : 1', '2 : 3', '3 : 7', ' 4 : 15', '5 : 31' ··· 이런식으로 진행되게 됩니다. 저는 여기서 (2^n)-1이라는 공식을 발견하게 되었고 이를 코드로 나타내서 계산하게 한 코드입니다.

 

- hanoi 함수

이 함수에서는 하노이탑의 원판 이동을 나타낸 코드입니다.

n==1일때 코드 진행을 멈추게 하고, a -> c 를 진행하고 b와 c의 위치를 바꿔 a -> b를 진행시킨 후 b->c로 진행 시키는 과정을 n이 1이 될때 까지 반복시켰습니다. 이를 통해 원판 이동 위치를 출력할 수 있게 되었습니다.

 

 

공식을 도출하는데 그렇게 큰 어려움을 느끼진 못했지만 원판 위치를 출력하는 과정에서 어려움을 느꼈습니다. 배열로 움직인 후 배열의 i 값을 출력하게 할까라는 고민도 하긴 했지만, 재귀함수를 이용하여 a, b, c의 위치를 옮기면서 코드 진행을 하게 만들었습니다. 이 문제를 통해서 코드를 너무 꼬아서 생각하는 저는 발견할 수 있었고, 이를 고쳐나가야겠다는 생각을 하게 되었습니다.

 

 

 

Baekjoon - 24060

https://www.acmicpc.net/problem/24060

 

이 문제는 병합정렬이라는 것을 새로 알게되는 문제이고 병합 정렬 의사코드를 굳이 안쓰고 하려다 꼬여서 하루종일 고민했고 이로 인해 어려웠던 문제이기에 추가하였습니다. 아래는 병합정렬에 대한 설명입니다.

 

병합정렬에서 입력되는 수는 오름차순으로 정렬됩니다. -> 만약 4 5 1 3 2을 입력받으면 1 2 3 4 5로 정렬을 한다는 뜻이다.
이 문제는 병합 정렬을 이용하는 것임으로 가운데를 찾아 왼쪽과 오른쪽을 나눠 정렬을 하는 것입니다.

"4 5 1 3 2"를 예로 들어 설명하자면 4 5 1과 3 2 로 나눠 정렬하여 1 4 5 / 3 2가 되고, 이를 다시 정렬하여 1 2 3 4 5로 정렬합니다.

 

 

#include <stdio.h>

int n,k;
int a[500001];
int tmp[500001];

int count = 0;
int result = -1;


void merge(int *a, int p, int q, int r){
    int i=p; int j=q+1; int t=1;

    while(i<=q && j<=r){
        if(a[i]<=a[j])
            tmp[t++] = a[i++];
        else
            tmp[t++] = a[j++];
    }
    while(i<=q)
        tmp[t++] = a[i++];
    while(j<=r)
        tmp[t++] = a[j++];
    
    i=p; t=1;

    while(i<=r){
        a[i++] = tmp[t++];
        count++;

        if(count==k){
            result = a[i-1];
            break;
        }
    }
}

void merge_sort(int *a, int p, int r){
    if(p<r){
        int q = (p+r) / 2;
        merge_sort(a, p, q);
        merge_sort(a, q+1, r);
        merge(a, p, q, r);
    }
}

int main(){
    scanf("%d %d", &n, &k);

    for(int i=0;i<n;i++){
        scanf("%d", &a[i]);
    }
    merge_sort(a, 0, n-1);

    printf("%d", result);
}

 

[백준에 나와있는 의사코드에 따라서 void merge 함수와 void merge_sort 함수를 그대로 구현하였습니다.]

- main 함수
main에서 첫 줄에 n과 k를 입력받게 되는데, n은 몇까지 입력받을지 저장하는 변수이고, k는 배열에서 몇번째 저장되는 수를 출력하는지 저장하는 변수이다.
merge_sort에 재귀를 할때 a는 배열을 넘겨줘야 하기 때문에 넣었고 0과 n-1은 배열에서 인덱스하기 위해 넣었습니다.

- merge_sort 함수
q = (p+r) / 2;는 p,r의 중간지점을 뜻하고, merge_sort(a, p, q)는 전반부, merge_sort(a, q-1, r)은 후반부 정렬을 의미한다.
그리고 merge(a, p, q, r)은 병합을 하기위한 코드입니다.

- merge 함수
첫번째 while문은 정렬을 하는 코드입니다. 그다음 while(i<=q)은 왼쪽 배열 부분이 남은 경우이고, while(j<=r)은 오른쪽 배열 부분이 남은 경우입니다. 그리고, while(i<=r)은 결과를 a[]에 저장하는 용도입니다. 여기서 count가 k와 같을때 result에 a[i-1]을 넣습니다.
재귀가 끝나고 main으로 돌아와 result에 입력된 결과값을 출력합니다.


너무 복잡하게 생각해서 하루종일 고민하고 어떻게 코드를 짜야할지 고민했지만 그냥 백준 설명에 나와있는 의사코드를 그대로 이용하면 되는 문제였어서 생각보다 허무했지만 병합정렬에 대해 알게 되었습니다.
저는 이 문제를 통해서 너무 복잡하게 꼬아서 생각하지 말고 있는 그대로를 바라보고 코드를 짜라는 교훈을 얻을 수 있게 되어 뜻깊은 문제이였습니다.