📌 Memoization vs Recursive

• Qustion - Momoization과 Recursive을 성능, 가독성 측면에서 비교하고 피보나치 수를 DP와 Recursive을 이용해서 구현하고 테스트하여라. f(1), f(100), f(10000)

📍 What is?

• Recursive

Recursive은 자신을 정의할 때 자신을 다시 참조하는 것을 의미한다.

fun fibo(n: Int): Int = if (n <= 2) 1 else fibo(n - 1) + fibo(n - 2);

• Memoization

  Memoization은 주어진 입력값에 대한 결과를 저장하여 같은 입력값이 주어졌을 때 다시 계산하는 것을 방지하는 개념니다. 가장 대표적인 예시가 피보나치 수열이다. 피보나치 수열에서 n번째 수를 구하는 함수를 f(n)이라고 해보자. n = 10 일 때 f(10) = f(9) + f(8) 이다. 근데 f(9) = f(8) + f(7) 이다. f(8)이 다시 계산되는 것을 확인할 수 있다. n의 값이 작을 때에는 큰 차이가 없으나 굉장히 큰 경우에는 반복 계산의 개수도 많아지고 낭비되는 시간도 많아진다. 만약 f(8)의 값을 메모리에 저장하고 이후 f(8)을 다시 계산할 때 직접 계산하는 것이 아니라 메모리에 저장된 값을 사용하면 훨씬 빠르게 계산할 수 있게 된다.
  

val memory: Array<Int> = Array(n) { 0 };

fun fibo(n: Int): Int = 
	if (n <= 2) 1 
    else if (memory[n] != 0) memory[n] 
    else (memory[n] = fibo(n - 1) + fibo(n - 2));

📍 Comparative Analysis

Memoization은 기존의 이미 계산한 결과값들은 재사용하기 때문에 동일 입력에 대한 문제는 O(1)의 시간으로 처리한다.

반면에 Recursive은 동일한 입력에 대한 계산을 계속하기 때문에 구하고자하는 값이 클수록 시간이 기하급수적으로 늘어난다.

테스트 결과에서도 f(1)은 시간적인 차이가 없었으나 f(100), f(1000)에서는 굉장히 큰 차이가 나는 것을 확인할 수 있다.

결론적으로 Memoization이 Recursive보다 시간적인 측면에서 굉장히 효율적이다.

다만, 위의 kotlin 구현을 보면 Recursive이 가독성 측면에서는 좋다는 것을 확인할 수 있다.

📍 Implement of Fibonacci

• DP

private final long[] memory = new long[Integer.MAX_VALUE];

public long fibonacci(int n) {
    return n < 2 ? n : memory[n] != 0 ? memory[n] : (memory[n] = fibonacci(n - 1) + fibonacci(n - 2));
}

• Recursive

public long fibonacci(int n) {
    return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
}

📍 Testing

• Testing Method

public void run(int n) {
    System.out.println("==================================================");
    long start = System.currentTimeMillis();
    long value = fibonacci(n);
    long end = System.currentTimeMillis();
    System.out.println("Value of fibonacci 1 = " + value + " Time = " + (end - start) + "ms");
    System.out.println("==================================================");
}

• Test Result

Memoization

시간적인 성능에 있어서는 문제가 없지만 수의 크기가 굉장히 커져서 잘못된 처리를 한 것 같다.

Recursive

재귀적으로 처리하는 방식으로 모든 하위 문제들을 계산하기 때문에 f(100)과 f(1000)은 시간적으로 오랜 시간이 걸려 측정이 어렵다.

📌 Bottom-Up & Top-Down

• Question - Buttom-Up과 Top-Down 방식을 정리(DP가 어느 부분에 해당하는지 언급) 하고 장단점을 비교하여라.

📍 What is?

• Bottom-Up

Bottom-Up 방식은 문제의 가장 작은 단위부터 시작하여 최종 문제까지 상향식으로 계산하는 방법이다. 피보나치 수열을 예로 들면 f(5)를 구할 때 f(2)=f(1) + f(0)을 우선 계산한다. (f(1)=1, f(0)=0). f(2)를 계산하고 나서는 f(3) = f(2) + f(1)을 계산하고 최종적으로 f(5) = f(4) + f(3)을 계산한다.

예시를 그림으로 나타내면 다음과 같다.

• Top-Down

Top-Down 방식은 위에서 아래로 문제를 분할하면서 계산하는 방법이다. 피보나치 수열을 예로 들면 f(5)를 구할 때 f(4)와 f(3)으로 문제를 분할합니다.

동일하게 f(n)=f(n-1)+f(n-2)으로 문제를 분할합니다. 또한 이미 계산한 f(n)에 대해서는 다시 계산하는 것이 아니라 이전에 저장한 memory에서 결과값을 호출하여 계산합니다.

아해의 그림은 fib(4)의 계산 방법이다. 화살표 방향으로 계산을 하며 노란색 블럭은 직접 계산하지 않고 memory에서 결과값을 불러온다.

📍 Compare

Top-Down

• 재귀를 사용하기 때문에 구현하기가 쉽다.
• 문제를 해결하는데 필요한 하위 문제들만을 계산한다.
• 재귀를 사용하기 때문에 stack overflow가 발생할 수 있다.

Bottom-Up

• 일반적으로 Top-Down 방식보다 효율적이다.
• 문제를 해결하기 위해서 필요한 하위 문제 이외의 문제들도 계산한다.

📌 LCS Algorithm

• Question - 설명자료의 LCS 알고리즘을 구현하여라.

📍 Implement

public class LCS {

    public int algorithm(String strA, String strB) {
        int lengthA = strA.length();
        int lengthB = strB.length();

        int[][] table = new int[lengthA + 1][lengthB + 1];

        for (int i = 1; i < lengthA + 1; i++)
            for (int j = 1; j < lengthB + 1; j++)
                if (strA.charAt(i - 1) == strB.charAt(j - 1)) table[i][j] = table[i - 1][j - 1] + 1;
                else table[i][j] = Math.max(table[i - 1][j], table[i][j - 1]);

        return table[lengthA][lengthB];
    }
}

📍 Testing

• Test Code

@Test
void algorithmTest() {
    LCS lcs = new LCS();
    List<String> strAs = List.of("ACAYKP", "ABCD", "ABCDEF", "heroicalyly", "eatmany", "ACCGATCG");
    List<String> strBs = List.of("CAPCAK", "AEBD", "GBCDFE", "scholarly", "setapple", "GACAT");
    List<Integer> lcsMaxes = List.of(4, 3, 4, 5, 3, 4);

    for (int i = 0; i < strAs.size(); i++) {
        assertEquals(lcsMaxes.get(i), lcs.algorithm(strAs.get(i), strBs.get(i)));
    }
}

• Result
  

📌 Edit Distance

• Question - Edit Distance를 구현하고 테스트하여라.

📍 Implement

public class EditDistance {

    public int algorithm(String from, String to){
        int fromLength = from.length();
        int toLength = to.length();

        int[][] table = new int[fromLength + 1][toLength + 1];

        for (int i = 1; i <= fromLength; i++) table[i][0] = i;
        for (int j = 1; j <= toLength; j++) table[0][j] = j;

        for (int i = 1; i <= fromLength; i++)
            for (int j = 1; j <= toLength; j++)
                if (from.charAt(i - 1) == to.charAt(j - 1))
                    table[i][j] = table[i - 1][j - 1];
                else
                    table[i][j] = 1 + Math.min(table[i][j - 1], Math.min(table[i - 1][j], table[i - 1][j - 1]));

        return table[fromLength][toLength];
    }
}

📍 Testing

• Test Code

@Test
void algorithmTest() {
    EditDistance editDistance = new EditDistance();
    List<String> froms = List.of("delete", "GUMBO", "abcdef", "MICROSOFT", "PYTHON", "EXPONENTIAL", "strike", "saturday", "stone", "elephant");
    List<String> tos = List.of("delegate", "GAMBOL", "azced", "NCSOFT", "PHOTO", "POLYNOMIAL", "stable", "sunday", "strong", "relevant");
    List<Integer> distances = List.of(2, 2, 3, 4, 4, 6, 3, 3, 2, 3);

    for (int i = 0; i < froms.size(); i++) {
        assertEquals(distances.get(i), editDistance.algorithm(froms.get(i), tos.get(i)));
    }
}

• Result

📌 Problem Solving

📍 Problem 01

코딩테스트 연습 - N으로 표현

📍 Problem 02

코딩테스트 연습 - 정수 삼각형

📍 Problem 03

코딩테스트 연습 - 등굣길

📍 Problem 04

코딩테스트 연습 - 도둑질