백준 1003 : 피보나치 함수 - C# 풀이

문제 사진.

 

하루 1문 코딩 테스트를 하면서 더더욱 느끼는 거지만 약간 느낌이 수학문제 푸는 느낌이다.

현재는 밤에 이 짓을 하고 있는데, 차라리 아침에 한번 확인하고 하루동안 계속 생각해 보는 게 나을 것 같다.

이 문제를 푼 대다수가 "시간 초과"로 인한 실패를 경험했다고 인터넷에 나온다.

내가 원래 제시했었던 방법과 그에 맞춰 찾은 해결법을 남겨두도록 하겠다.

---

1. 원래 풀이

using System;

namespace unicoti { 
    class Program {
        static int oneCount = 0;
        static int zeroCount = 0;
        
        static void Main(string[] args) {
            string input = Console.ReadLine();
            int repeat = int.Parse(input);
        
            for(int i = 0; i < repeat; i++) {
                int a = int.Parse(Console.ReadLine());
                fibonacci(a);
            
                Console.WriteLine(zeroCount.ToString()+" "+oneCount.ToString());
                oneCount = 0; zeroCount = 0;
            }
        }
    
        static void fibonacci(int n) {
            if(n == 0) {
                zeroCount++;
            } else if(n == 1) {
                oneCount++;
            } else {
                fibonacci(n-1);
                fibonacci(n-2);
            }
        }
    }  
}

 

솔직히 좀 과도하게 긴 감이 있지만, 코드 자체는 쉽다.

먼저, 0과 1이 몇 번 나올지 카운트할 변수를 만들어주었고, 밑에 피보나치 함수를 만들어서

0과 1이 나올 때마다 카운트를 올리고, 재귀함수로 만들어주었다. 이렇게 하면 어떤 함수가 실행되던

한 개의 변수로 값이 모아질 것이라 생각해서 이렇게 진행했다.

이제 주어진 값대로 몇 번 실행할지를 정해 for문으로 반복하고, 마지막에는 값을 출력해 주어 끝냈다.

 

이 방식은 분명 간단하고 맞는 방법이지만, 작은 숫자부터 매우 큰 숫자까지 모두 확인하는 코딩 테스트의 특성상

재귀함수 방식은 매우 큰 숫자에서 오버플로우를 일으키기 충분하다. 따라서 많은 유저들이 시간 초과를 경험한다.

---

2. 해결방안.

using System;
using System.Collections.Generic;

namespace unicoti {
    class Program {
        static int oneCount = 0;
        static int zeroCount = 0;
        static Dictionary<int, (int zeroCount, int oneCount)> memo = new Dictionary<int, (int zeroCount, int oneCount)>();
        
        static void Main(string[] args) {
            string input = Console.ReadLine();
            int repeat = int.Parse(input);
        
            for (int i = 0; i < repeat; i++) {
                int a = int.Parse(Console.ReadLine());
                var result = fibonacci(a);
                Console.WriteLine(result.zeroCount + " " + result.oneCount);
                oneCount = 0; zeroCount = 0;
            }
        }
    
        static (int zeroCount, int oneCount) fibonacci(int n) {
            if (memo.ContainsKey(n)) {
                return memo[n];
            }

            if (n == 0) {
                zeroCount = 1;
                oneCount = 0;
            } else if (n == 1) {
                zeroCount = 0;
                oneCount = 1;
            } else {
                var fib1 = fibonacci(n - 1);
                var fib2 = fibonacci(n - 2);
                zeroCount = fib1.zeroCount + fib2.zeroCount;
                oneCount = fib1.oneCount + fib2.oneCount;
            }

            memo[n] = (zeroCount, oneCount);
            return memo[n];
        }
    }
}

 

좀 많이 길긴 하다.. 솔직히 그렇게 효율적인 풀이는 아닌 것 같지만 나 자신의 개인적인 발전을 위해

남기는 글이기에 굳이 신경 쓰지는 않겠다. 결론적으로, 내가 선택한 방법은 로직은 똑같이 가져가되

최적화를 시키는 것이다. 많은 자료를 찾아본 결과 "메모이제이션"이라는 기법을 많이들 쓰는 걸 볼 수 있었다.

이에 대한 글은 따로 남기도록 하겠다.

요약하자면 1번과 같은 로직으로 풀었지만 최적화를 더하여 시간 초과 현상을 해결했다.

---

오늘의 느낀점)

코딩 테스트를 매일 밤에 풀고 있는데, 아침에 문제를 보고 하루동안 생각하는 게 낫겠다고 느꼈으며,

로직의 완성뿐 아니라 최적화 기술도 새로 알게 되어 공부할 거리가 생겨서 좋았다. 원래는 난이도 별로

문제가 정리되어 있는데 나는 순서대로 풀고 싶어서 이러고 있는데, 객기 부리지 말걸 그랬다.

 

C#의 기본 구조를 글로 한번 정리했음에도 아직까지는 헷갈리는 부분이 남아있는 듯하다.

유니티를 너무 많이 해서 처음 보는 순수 언어의 구조는 아직 헷갈린다. 그래도 계속해서 하루에 1문제씩

풀어주고 있는 나 자신이 고맙기도 하다. 메모이제이션을 완벽히 이해하여 또다시 글로 남기길 응원한다.

---

이상으로 도움이 되었길 바라며,

 

끝.