4장: 설계 기법(2) - 재귀와 분할 정복법

4장: 설계 기법(2) - 재귀와 분할 정복법

재귀 호출(Recursive Call): 작업 중 자기 자신을 호출하는 것.

연습 문제
4.1 트리보나치 수열은 다음과 같이 정의 된 수열이다.
• T0 = 0
• T1 = 0
• T2 = 1
• Tn = Tn-1 + Tn-2 + Tn-3 (N = 3, 4, …)

0, 0, 1, 1, 2, 4, 7, 13, 24, 44, … 로 이어질 때 트리보나치 수열의 제 N항 값을 구하는 재귀함수를 설계하라.

            int count = 0;

            long RF_Tribo(int N)
            {
                if (N <= 1)
                {
                    return 0;
                }

                if (N == 2)
                {
                    return 1;
                }

                count++;
                return RF_Tribo(N - 3) + RF_Tribo(N - 2) + RF_Tribo(N - 1); // O(3^N)?
            }

            Console.WriteLine(RF_Tribo(N - 1));

4.2 연습문제 4.1에서 설계한 재귀 함수에 대해 메모이제이션을 사용해서 효율을 개선하라. 그리고 메모이제이션 실시 후의 복잡도를 평가하라.

Dictionary<int, long> cachedData = new Dictionary<int, long>();

            long RF_Tribo(int N)
            {
                if (N <= 1)
                {
                    return 0;
                }

                if (N == 2)
                {
                    return 1;
                }

                long result;
                if (cachedData.ContainsKey(N))
                {
                    result = cachedData[N]; // 중복 연산 제거로 O(N)에 근접
                }
                else
                {
                    result = RF_Tribo(N - 3) + RF_Tribo(N - 2) + RF_Tribo(N - 1);
                    cachedData.Add(N, result);
                }

                return result;
            }

            Console.WriteLine(RF_Tribo(N - 1));

4.5 10진수 표기로 각 자리 수가 7, 5, 3 중 하나이고 7, 5, 3이 모두 한 번은 등장하는 정수를 753수 라고 부르기로 하자. 양의 정수 K가 주어졌을 때 K이하의 753수가 몇 개 존재하는지 구하는 알고리즘을 설계하라. 단, K의 자릿수를 d라고 할 때, O(3^d) 복잡도가 허용 범위다.

            // 몇 자리 숫자인지 구한다.
            int d = (int)Math.Floor(Math.Log10(K) + 1);
            Console.WriteLine("자릿수: " + d);

            long maxValue = 0;
            if (d >= 7)
            {
                maxValue = Math.Min(K, 9999753);
            }
            else if (d >= 5 && d < 7)
            {
                maxValue = Math.Min(K, 99753);
            }
            else if (d >= 3 && d < 5)
            {
                maxValue = Math.Min(K, 753);
            }

            int count = 0;
            for (int i = 357; i < maxValue; i++) // O(1) 아무리 커도 상수 9999753 보다 큰 753 수는 없다.
            {
                string num = i.ToString();
                if (num.Contains('3') && num.Contains('5') && num.Contains('7'))
                {
                    count++;
                    Console.WriteLine(num);
                }
            }

            Console.WriteLine("\n753 수의 개수: " + count);

4.6 부분합 문제에서 재귀 함수를 사용한 복잡도 O(2^n)의 코드 4-9에 대해 메모이제이션을 사용하여 O(NW)복잡도로 개선하라.