Java-알고리즘 ( Recursive, Dynamic Programming )

재귀

고급 정렬 알고리즘에서 재귀 용법을 사용하므로, 고급 정렬 알고리즘을 익히기 전에 재귀 용법을 먼저 익혀야 한다.

• 함수 안에서 동일한 함수를 호출하는 형태
• 여러 알고리즘 작성시 사용되므로, 익숙해져야함.

간단한 예제

// src/com.company/Main.java

package com.company;

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static Integer[] dp = new Integer[100];

    static Integer recursiveFunction(Integer targetNumber) {

        if(targetNumber < 0) {
            return 0;
        }
        if(targetNumber == 0 || targetNumber == 1) {
            return 1;
        }
        // 만약 dp에 해당 targetNumber에 해당하는 값이 있다면
        if(dp[targetNumber] != null) {
            return dp[targetNumber];
        }

        Integer value = recursiveFunction(targetNumber - 1) + recursiveFunction(targetNumber - 2) + recursiveFunction(targetNumber - 3);
        dp[targetNumber] = value;
        return value;
    }

    public static void main(String[] args) {

        System.out.println(Main.recursiveFunction(5));




    }
}

연습해보기3

- 정수 4를 1, 2, 3의 조합으로 나타내는 방법은 다음과 같이 총 7가지가 있음 - 정수 n이 입력으로 주어졌을 때, n을 1, 2, 3의 합으로 나타낼 수 있는 방법의 수를 구하시오

1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1

힌트: 정수 n을 만들 수 있는 경우의 수를 리턴하는 함수를 f(n) 이라고 하면,
f(n)은 f(n-1) + f(n-2) + f(n-3) 과 동일하다는 패턴 찾기
출처: ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Taejon 2001

이와 같이 간단항 예제를 풀어보았다.

 

동적 계획법

• 동적계획법 (DP라고 많이 부름)
  • 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서, 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘
  • 상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과값을 이용해서 상위 문제를 풀어가는 형식
  • Memorization 기법을 사용함
    
    • Memorization(메모리제이션) 이란: 프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계싼하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술
• 분할 정복
  • 문제를 나눌 수 없을때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘
  • 하양식 접근법으로, 상위의 해답을 구하기 위해, 아래로 내려가면서 하위의 해답을 구하는 방식
    • 일반적으로 재귀함수로 구현
  • 문제를 잘게 쪼갤 떄, 부분 문제는 서로 중복되지 않음
    • 병합정렬, 퀵 정렬

public class Dynamic {
    public int dynamicFunc(int data) {
        Integer[] cache = new Integer[data + 1];
        cache[0] = 0;
        cache[1] = 1;
        for (int index = 2; index < data + 1; index++) {
            cache[index] = cache[index - 1] + cache[index - 2];
        }
        return cache[data];
    }   
}