글 읽기 - 메모이제이션을 사용했는데 어디가 잘못됬는지 모르겠습니다.

dimss 5년 전 0

시간초과가 나와서 질문드립니다.

질문 게시판에 검색도 해보고 글을 다 읽어 봤지만 어디가 잘못됬는지 모르겠습니다.

제가 작성한 부분의 소스가 어디서 잘못되어서 시간초과가 뜰까요.

import java.util.Scanner;

public class Main {

    private static int zeroCount = 0;
    private static int oneCount = 0;
    private static int[] numbers = new int[41];

    public static void main (String args[]) {
        Scanner s = new Scanner(System.in);

        int count = s.nextInt();

        for (int i = 0; i < count; i ++) {
            int temp = s.nextInt();
            numbers[temp] = fibonacci(temp);
            System.out.println(zeroCount + " " + oneCount);
            zeroCount = 0;
            oneCount = 0;
        }
    }

    public static int fibonacci(int n) {
        if (n == 0) {
            zeroCount ++;
            return 0;
        } else if (n == 1) {
            oneCount ++;
            return 1;
        } else {
            if (numbers[n-1] != 0 && numbers[n-2] != 0) {
                return numbers[n-1] + numbers[n-2];
            } else {
                return fibonacci(n - 1 ) + fibonacci( n - 2);
            }
        }
    }
}

seico75 5년 전 1

메모하는 부분이 없네요.

그리고 메모는 0/1 의 수를 메모해야하지 않을까요?

djm03178 5년 전 1

메모장에 펜을 그은 적이 없으니 아무것도 메모가 항상 안 되어 있는 게 당연합니다.

dimss 5년 전 0

@seico75
기본 피보나치도 안되서 왜 안되는지 확인하고 하려고요 ㅠ

numbers[temp] = fibonacci(temp); 저는 이게 메모라고 생각하고 있는데 잘못생각한걸까요?

djm03178 5년 전 1

펜을 아예 그은 적이 없는 건 아니군요. 하지만 이건 메모이제이션이라기보다는 결과를 그냥 저장해둔 것에 가깝습니다. 메모이제이션이라고 하려면, 그 중간 과정에서 나온 값들도 모두 기록해둬야 합니다.

예를 들어 fibonacci(40)을 구하려면 fibonacci(0)부터 fibonacci(39)까지를 모두 호출하게 되는데, 그 때마다 각각의 결과를 구할 수 있는데 이들을 바로바로 저장해두면 좋지 않을까요?

dimss 5년 전 0

@djm03178

답변감사드립니다!

seico75 5년 전 1

기본 피보나치에 중점을 두어서

조금더 자세히 설명을 드리면...31~35줄은.. 아래와 같이 바뀌어야 할 껏 같네요..

말씀하신 것 처럼 main에서 memo를 하면 전체 프로그램 수행에서 한번만 memo 가 됩니다.

우리의 목적은 중간 저장 결과를 모!두! 저장해야하니까 아래와 같이 재귀 함수 내에서 계산된 것을 모두 저장해야 합니다.

돌려보지 않고 음주 코딩이어서 감안하고 봐주세여.

#if 1
//가져다 쓸 수 있으면 쓰고
if (numbers[n] != 0)    return number[n];
// 아니면 돌리고....
else {
    number[n] = fibonacci(n - 1 ) + fibonacci( n - 2);  // 그러나 저장은 하고...
    return number[n];
}
#else // 좀더 깔끔하게 하려면....
int& ret = numbers[n];

if ( ret == 0)    // 아직 메모가 안되었으면 재귀 돌려 저장하고.... 되었으면 그냥 저장한 값 쓰고
{
    ret = fibonacci(n - 1 ) + fibonacci( n - 2);
}
return ret;
#endif

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

메모이제이션을 사용했는데 어디가 잘못됬는지 모르겠습니다.

dimss 5년 전 0

seico75 5년 전 1

djm03178 5년 전 1

dimss 5년 전 0

djm03178 5년 전 1

dimss 5년 전 0

seico75 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말