[알고리즘] C언어 간단한 알고리즘 문제

며칠 전에 C언어 과제를 대신 해줬는데, 단순하지만 꽤 재밌었다.

문제는 다음과 같다.

1번 문제

주사위 두 개를 36,000번 던져서 나오는 모든 경우의 수를 계산하는 프로그램을 작성하세요.

주사위 각각은 1부터 6까지의 정수 값을 표시할 수 있으므로 합계는 2부터 12까지입니다.

7이 나올 확률이 가장 크고, 2와 12가 나올 확률이 가장 적습니다.

주사위 2개를 던지는 과정을 수행하기 위해 rand() 함수를 각각 사용합니다.

[ 아래의 출력 값과 유사한 값이 출력되어야 합니다. ]

Output :
 
 2 : 1026 (0.028500)
 3 : 2023 (0.056194)
 4 : 2988 (0.083000)
 5 : 4086 (0.113500)
 6 : 5018 (0.139389)
 7 : 5978 (0.166056)
 8 : 4928 (0.136889)
 9 : 3992 (0.110889)
10 : 3096 (0.086000)
11 : 1907 (0.052972)
12 :  958 (0.026611)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
const int REPEATED = 36000;
 
int main(void) {
    int i, arr[11] = {0, };
 
    srand(time(NULL));
    for (i = 1; i <= REPEATED; i++) {
        arr[rand() % 6 + rand() % 6]++;
    }
 
    printf("Output : \n\n");
    for (i=0; i<11; i++) {
        printf("%2d : %4d (%f)\n", 2+i, arr[i], (float)arr[i] / REPEATED);
    }
 
    return 0;
}

실행 결과

Output :
 
 2 :  959 (0.026639)
 3 : 2019 (0.056083)
 4 : 3034 (0.084278)
 5 : 3941 (0.109472)
 6 : 5020 (0.139444)
 7 : 6004 (0.166778)
 8 : 4955 (0.137639)
 9 : 4020 (0.111667)
10 : 3100 (0.086111)
11 : 1983 (0.055083)
12 :  965 (0.026806)

2부터 12까지의 빈도수를 저장할 배열을 만들었다.

0부터 10까지의 인덱스를 가진 정수형 배열을 만들어 모두 0으로 초기화를 해줬다.

현재 time 값으로 난수 발생의 씨드(seed)를 지정해줬다.

rand() 함수를 두 번 사용함으로써, 두 개의 난수로 2부터 12까지의 합계를 만들었다. 그러나 인덱스는 0부터 10까지다. 0 <= rand() % 6 <= 5 이므로, 0 <= rand() % 6 + rand() % 6 <= 10 이다. 따라서 정확히 매칭된다. 매칭된 인덱스에 빈도수를 누적한다.

결과를 출력할 때, 확률은 당연히 빈도수 / 36000 이 된다.

2번 문제

키보드에서 -1을 입력 받을 때까지의 양의 실수(float)를 임의로 얻고, 입력된 값들의 평균과 표준편차를 출력하는 프로그램을 작성하세요. 표준편차는 아래의 공식을 참고하기 바랍니다.

[ 예상 실행 화면 ]

> a.exe
1.5
2.3
4.7
-1
mean = 2.833333 , standard dev = 1.359738

#include <stdio.h>
#include <math.h>
 
int main(void) {
    float float_val;
 
    float float_sum = 0, float_sum_square = 0, float_mean = 0, float_std = 0;
    int count = 0;
 
    while(1) {
        scanf("%f", &float_val);
        
        if (float_val == -1) {
            break;
        } else if (float_val < 0) {
            printf("[Error] float_val must be positive!\n");
            continue;
        }
 
        float_sum += float_val;
        float_sum_square += float_val * float_val;
        count++;
    }
 
    float_mean = float_sum / count;
    float_std = sqrt(float_sum_square / count - (float_mean * float_mean));
 
    printf("mean = %f, standard dev = %f\n", float_mean, float_std);
 
    return 0;
}

[ 실행 결과 ]

> ./main
1.5
2.3
4.7
-1
mean = 2.833333, standard dev = 1.359738

-1을 입력받을 때 까지, 입력 받은 값들을 누적해야 한다. 사실 주어진 공식에서는, 입력된 값들을 하나하나 저장하고 있어야 한다. 언제까지 입력받을 지도 모를 데이터를 담아두는 방법은 다음 두 가지다.

첫 째, 큰 배열을 하나 만들어서 차곡차곡 저장한다. 두 번째는, 연결 리스트 자료구조로 메모리 동적생성하여 담아두는 방법이 있다. 위 두 가지 방법 모두 비효율 적이다.

첫번째 방법은, 메모리를 낭비할 가능성이 크다. 즉, 큰 공간을 다 쓰지도 않을 수 있다. 반대로 그 크기를 넘어갈 수도 있다. 배열의 범위에 넘어서는 대입은 오버플로우 에러를 발생한다. 두번째 방법은, 오버 코딩이다. 소스 코드 길이를 복잡하게 만든다.

처음에 연결 리스트로 만들어 데이터를 저장하려고 했다. 생각해보니 표준편차를 구하는 식에, 각 데이터를 이용하지 않아도 된다. 다음의 식을 보자.

편차 제곱의 합을 위와 같이 바꿀 수 있다. 각 데이터의 제곱의 합과 평균의 제곱을 빼는 방법이다.

위 공식이 좋은 점은, 각 데이터를 저장할 필요가 없다.

평균을 구하기 위해 각 데이터를 합한 것과, 표준편차를 계산할 때 필요한 각 데이터의 제곱을 합한 값만 필요로 한다.

3번 문제

국제스케이팅연맹(ISU)에서 피겨스케이팅의 공평성을 높이기 위해 점수체계를 단순화시키려 한다.

이전 시스템에서는 5명의 심사위원이 1에서 10까지의 점수를 부여했다. 최대와 최소 점수를 제외한 점수의 합계가 최종 점수가 되었다. 이 시스템을 개선하기 위해 5개 점수에서 최대, 최소 점수를 제거한 뒤, 나머지 3개의 점수 중에서 최대/최소 점수의 차이가 5 이상이면 재 평가를 해야 한다.

- 5개의 점수를 입력 받아 총점을 출력하는 프로그램을 작성하세요. 점수를 재평가해야 하는 경우, KIN(Keep In Negotiation)을 출력하세요.

[ 예상 실행 화면 ]

Input Example : 10 8 5 7 9
Output Example : 24
 
Input Example : 10 3 4 9 10
Output Example : KIN

#include <stdio.h>
 
int main(void) {
    int arr[5], i, minIndex = 0, maxIndex = 0, count = 0, sum = 0;
 
    printf("input > ");
    for (i=0; i<5; i++) {
        scanf("%d", &arr[i]);
        if (arr[minIndex] >= arr[i]) {
            minIndex = i;
        }
        else if (arr[maxIndex] <= arr[i]) {
            maxIndex = i;
        }
    }
 
    for (i=0; i<5; i++) {
        if (i != minIndex && i != maxIndex) {
            arr[count++] = arr[i];
        }
    }
 
    maxIndex = minIndex = 0;
 
    for  (i=0; i<3; i++) {
        if (arr[minIndex] >= arr[i]) {
            minIndex = i;
        }
        else if (arr[maxIndex] <= arr[i]) {
            maxIndex = i;
        }
 
        sum += arr[i];
    }
 
    if (arr[maxIndex] - arr[minIndex] >= 5) {
        printf("KIN\n");
    } else {
        printf("%d\n", sum);
    }
 
    return 0;
}

[ 실행 결과 ]

>  ./main
input > 10 8 5 7 9
24
> ./main
input > 10 3 4 9 10
KIN

이 문제를 풀기 위해서는 최대값과 최소값을 찾아야 한다. 5개의 입력을 받을 예정이므로, 크기가 5인 정수형 배열을 만든다. 그리고, 최대값과 최소값, 이 둘의 인덱스를 저장할 두 변수(minIndex, maxIndex)를 만들었다.

최대값과 최소값을 제외한 나머지 3 점수를 알아야 한다. 보기 쉽게 본 배열을 정리하려 한다. 최대 최소 인덱스가 아닌 값을 다시 인덱스 0부터 채운다. 그리고 인덱스 0부터 2까지 3개의 값에서 다시 최대값과 최소값을 찾는다. 그 차이를 계산해 판단한다.

나머지 세 개의 정수의 최대값과 최소값, 세 합계를 구할 때, 따로 원본 배열을 정리하지 않아도 구할 수 있다. 그렇게 했을 때, 원본 배열의 최대값과 최소값이면, continue 키워드로 반복문을 넘겨, 나머지 3개의 최대값과 최소값을 반복문 하나에 구할 수 있다.

그러나 이렇게 했을 때, 원본 배열의 최대 최소인지 판별할 때 필요한 minIndex와 maxIndex를 재사용하지 못한다. 새로운 minIndexInThree, maxIndexInThree 같은 정수형 변수를 새로 만들어, 나머지 3개의 최대값과 최소값을 저장해야 했을 것이다.

정수형 변수 두 개를 추가로 사용할 바엔, 한 번 배열을 정리하는 것이 메모리 관점에서 더 나은 선택이다. 사실 얼마 차이 나겠느냐만은.

4번 문제

사다리게임을 구현해보세요. 사다리는 아래 그림과 같이 N개의 수직선과 M개의 수평선으로 표시되며, 수평선은 두 개의 수직선에 점을 연결하는 형태로 이루어져 있습니다. 입/출력 예시처럼 각 시작점과 연결된 결과를 출력하는 프로그램을 작성하세요.

- input 방법 : 첫 번째 줄에는 수직선의 수 N(N<=15), 두 번째 줄에는 수평선 수 M(M<=30)를 입력 받고, 다음 줄에서는 수평선의 시작점과 끝점을 입력해야 합니다.

#include <stdio.h>
#include <stdlib.h>
 
int main(void) {
    int N, M, i, j, tmp, change1, change2, idx1, idx2;
    int *arr;
 
    scanf("%d", &N);
    if (N > 15 || N <= 0) {
        printf("Error\n");
        return 1;
    }
 
    arr = (int *) malloc(sizeof(int) * N);
    for (i=0; i<N; i++) {
        arr[i] = i + 1;
    }
 
    scanf("%d", &M);
    if (M > 30 || M <= 0) {
        printf("Error\n");
        return 1;
    }
 
    for (i=0; i<M; i++) {
        scanf("%d %d", &change1, &change2);
        
        for (j = 0; j < N; j++) {
            if (arr[j] == change1) {
                idx1 = j;
            } else if (arr[j] == change2) {
                idx2 = j;
            }
        }
 
        tmp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = tmp;
    }
 
    for (i=0; i<N; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
 
    return 0;
}

[ 실행 결과 ]

> ./main
5
4
1 3
3 4
2 5
2 3
4 5 1 2 3

메모리 동적 생성으로, 첫 번호를 저장할 배열을 생성했다. 결과 배열을 새로 만들기 보다는, 처음에 만든 배열로 각 해당하는 숫자를 가진 인덱스끼리 바꿔줬다.

처음에 좀 헤맸다. 입력받은 각 숫자 인덱스에서 서로 바꿔주기만 했었는데 뭔가 잘못됨을 깨달았다. 그 문제점은 숫자를 바꿔주는 과정에서 더 이상 인덱스와, 그 인덱스가 가진 값이 일치하지가 않는다는 점이었다. 그래서 입력 받은 각 숫자에 해당하는 인덱스를 찾아 그 둘을 바꿔줬더니 잘 작동했다.