AP 프로그래밍

[관계기반설계] [메모이제이션] CodeUp 문제풀이

yalu 2023. 3. 13. 02:48

관계기반설계는 해를 하나의 함수로 표현하고 함수들의 관계를 이용하여 해를 구하는 방법이다.

점화식 또는 수학적 귀납법의 형태로 해를 나타낼 수 있을 때, 관계기반설계는 자주 쓰이는 테크닉이니 알아두자.

예를 들어, 피보나치 수열 f(n)을 구해야 할 때, f(n) = f(n-1) + f(n-2)이다.

따라서 다음과 같은 형태로 해를 구할 수 있다.

다음은 코드업 - 1915 : (재귀함수) 피보나치 수열 실행 시간을 보여주는 코드이다.

#include <stdio.h>
#include <time.h>

int f(int n){
if (n==0) return 0; // 0이면 0
if (n==1||n==2) return 1; // 1, 2는 1
return f(n-2)+f(n-1); // 그 외는 n-2 + n-1
}

int main(){
int a;
scanf("%d",&a); // 입력
clock_t start = clock(); // 함수 실행 시작 시간 측정
printf("%d ",f(a)); // 출력
clock_t end = clock(); // 함수 실행 종료 시간 측정
printf("run time : %lf", (double)(end - start) / CLOCKS_PER_SEC); // 함수 실행 시간 출력
}

보다시피 관계기반설계를 사용했다.

하지만 이 알고리즘의 치명적인 단점은 바로 O(n^2)의 시간복잡도를 가졌다는 것이다.

n이 작다면 상관 없지만 n이 45라면 실행시간이 무려 6초나 걸린다.

메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. - 위키백과 -

음.. 그렇다고 하니 메모이제이션을 사용해보자.

다음은 코드업 - 1916 : (재귀함수) 피보나치 수열 (Large) 실행 시간을 보여주는 코드이다.

#include <stdio.h>
#include <time.h>

int memo[50001] = {0}; // 50001 크기의  배열

long long int f(int a){
if (a == 1 || a == 2){ // 입력값이 1 또는 2인 경우 1
memo[a] = 1;
return 1;
} else if (memo[a] != 0){ // 메모리에 이미 계산된 결과가 있으면 그대로 반환
return memo[a];
} else { // 이전에 계산한 결과가 없으면 계산
return memo[a] = (f(a - 1) + f(a - 2)) % 10009; // 10009로 나눔 (문제에서 그렇게 하라고 함)
}
}

int main(){
int a;
scanf("%d", &a); // 입력
clock_t start = clock(); // 함수 실행 시작 시간 측정
printf("%lld ", f(a)); // 출력
clock_t end = clock(); // 함수 실행 종료 시간 측정
printf("run time : %lf", (double)(end - start) / CLOCKS_PER_SEC); // 실행 시간 출력
}

이 방법을 쓰니 무려 50000번째 항까지의 합을 0.000000초 만에 구할 수 있다.

이 알고리즘의 시간복잡도는 O(n)이다.

근데 이 알고리즘은 공간복잡도가 O(n)이다. 어이쿠; 번거롭네

꼬리 재귀는 재귀 함수를 호출할 때 스택을 재사용하면서

메모리를 과도하게 사용하지 않도록 최적화하는 방법이다. - 위키백과 - 

꼬리재귀를 한번 사용 해보자

 
#include <stdio.h>
#include <time.h>

long long int f(int n, int f1, int f2) {
if(n == 0) { // 0번째는 0
return f2;
} else if(n == 1) { // 1번째는 1
return f1;
}
long long int currentFibo = f1 + f2; // 현재 피보나치 수 계산
f2 = f1; // 이전 피보나치 수 업데이트
f1 = currentFibo; // 현재 피보나치 수 업데이트
return f(n - 1, f1, f2); // 재귀 호출
}

int main() {
int n;
scanf("%d", &n); // 입력
clock_t start = clock(); // 함수 실행 시간 측정 시작
printf("%lld ", f(n, 1, 0)); // 출력
clock_t end = clock(); // 함수 실행 시간 측정 종료
printf("run time : %lf", (double)(end - start) / CLOCKS_PER_SEC); // 실행 시간 출력
}

짠 시간복잡도가 O(n), 공간복잡도가 O(1)인 코드가 완성되었다.

비슷하게 CodeUp - 2832 : [상태 정의를 통한 탐색] 계단 오르기 1-1 를 해결 할 수 있다.

문제설명

OO이가 계단을 올라가려고 한다.

계단은 모두 n칸으로 구성되어 있다.

OO이는 한 번에 1칸, 2칸을 오를 수 있다.

OO이가 k개 이하의 칸을 사용하여 0번째 칸에서 출발하여 n번째 칸으로 올라가는 서로 다른 방법의 수를 구하는 프로그램을 작성하시오.

만약 n = 3, k = 3 이면

- 1 2 : 0번째, 1번째, 3번째 계단을 이용하여 목표에 도달
- 2 1 : 0번째, 2번째, 3번째 계단을 이용하여 목표에 도달

로 모두 2가지 경우가 있다.

입력

첫 번째 줄에 n과 k가 공백을 기준으로 입력된다.

[입력값의 정의역]
[1 ≤ n ≤ 40]
[1 ≤ k ≤ 20]

출력

계단을 올라가는 서로 다른 경로의 수를 출력한다.

#include <stdio.h>

int n, k;
int memo[41][21];// 배열 선언

int step(int current_n, int steptimes)
{
  if (current_n > n || steptimes > k) // 0반환
    return 0;
  if (current_n == n) // 1반환
    return 1;
  if (memo[current_n][steptimes] != -1) // 이미 계산된 값인 경우 반환
    return memo[current_n][steptimes];
  memo[current_n][steptimes] = step(current_n + 1, steptimes + 1) + step(current_n + 2, steptimes + 1); // 값을 계산하고 저장
  return memo[current_n][steptimes];
}

int main()
{
  scanf("%d %d", &n, &k); // 입력
  for (int i = 0; i <= n; i++) // 배열 초기화
    for (int j = 0; j <= k; j++)
      memo[i][j] = -1;
  printf("%d\n", step(0, 1)); // 출력
  return 0;
}

 

해설 : step(current_n, steptimes) = step(current_n + 1, steptimes + 1) + step(current_n + 2, steptimes + 1)를 이용한다.

참 쉽죠?

핵심 개념 : 관계기반설계, 메모이제이션, 꼬리재귀

 

 

 

 

 

 

 

 

 

 

 

 

 

 

순서도

오류 해결 과정

#include <stdio.h>

int n, k;
int memo[41];

int step(int current_n, int steptimes)
{
    if (current_n > n || steptimes > k)
        return 0;
    if (current_n == n)
        return 1;
    if (memo[steptimes] != -1)
        return memo[steptimes];
    memo[steptimes] = step(current_n + 1, steptimes + 1) + step(current_n + 2, steptimes + 1);
    return memo[steptimes];
}

int main()
{
    scanf("%d %d", &n, &k);
    for (int i = 0; i <= k; i++)
        memo[i] = -1;
    memo[k] = 0;
    printf("%d", step(0, 1));
    return 0;
}

에서 memo[steptimes] = step(current_n + 1, steptimes + 1) + step(current_n + 2, steptimes + 1); 점화식을 잘못 설계해서 어려움을 겪음.