[SW Expert Academy][Computational Thinking] 재귀 / 동적 프로그래밍

링크

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPCwCKAAPw5UW6&subjectId=AV1lG8vKAAoCFAb_

문제 1

$F(n)=F(n-1)+F(n-2), F(1)=F(2)=1$

수도코드

function Fibonacci(n):
	if n==1 or n==2:
    	return 1
    else:
    	return Fibonacci(n-1)+Fibonacci(n-2)

정확성 증명

$F(1)=1$ 이고 $F(2)=1$이고 $n>=3$인 경우에서 해당 함수를 재귀로 일지한다.

시간 복잡도 계산

피보나치 수열을 계산하는데 걸리는 시간 즉, $F(n)$을 계산하는데 걸리는 시간은 $F(n-1)$이 걸리는 시간과 $F(n-2)$이 걸리는 시간의 합에 그 결과를 더하는 연산 ($+$)을 하는데 $O(1)$의 시간이 걸린다. 그렇기 때문에 $T(n)=T(n-1)+T(n-2)+O(1)$의 식으로 나타낼 수 있다.
$T(n-2)$가 $T(n-1)$보다 피보나치 수열에 의해 전 단계이므로 더 작거나 같기 때문에
$T(n)\leq2T(n-1)+1$로 $T(n)=T(n-1)+T(n-2)+1$의 식을 단순화 시켜도 부등호가 성립한다.
$T(n)\leq2T(n-1)+1$ 식을 반복하여
$T(n-1)\leq2T(n-2)+1$
$T(n-2)\leq2T(n-3)+1$이런 식으로 반복하고 이 식들을 대입하여 적용하면
$T(n)\leq2^kT(n-k)+2^{k-1}+...+2^0$이 된다.
여기서 $k=n-1$일 때나 $k=n-2$일 때, $T(1)$이 되거나 $T(2)$이 되므로 기하 급수의 형태를 우변이 띄게 된다. 이러한 형태를 기하 급수의 합을 계산하면 $2^n$이 되므로
$T(n)\leq2^n$의 형태를 띄게 된다. 결과적으로 $T(n)=O(2^n)$이 된다.

문제 2

수도코드

수도 코드는 재귀를 이용해 정렬하는 과정과 각 정렬된 배열을 합치는 과정으로 나뉜다.
정렬하는 전체 과정은 배열의 길이가 1보다 작으면 정렬할 필요가 없으므로 배열 글대로 리턴하고 그렇지 않으면 왼쪽과 오른쪽으로 나누어서 정렬한 결과를 합친다.

function mergeSort(arr):
	if length of arr<=1:
    	return arr
    middle=length of arr/2
    left=mergeSort(arr[0:middle])
    right=mergeSort(arr[middele:length of arr])
    
    return merge(left,right)

합치는 과정은 각 왼쪽, 오른쪽 배열이 입력으로 주어지면 각 배열의 첫번째부터 비교하면 작은 순으로 넣는 오름차순 배열이며 각 배열은 정렬되어 있으므로 한쪽 배열이 다 소진되면 남은 배열은 순차적으로 결과값에 넣어주면 된다.

fuction merge(left,right):
	result=[]
    while left is not empty and right is not empty:
        if left[0]<=right[0]:
            append left[0] to result
            left = left[1:]
        else:
            append right[0] to result
            right = right[1:]
    while left is not empty:
    	append left[0] to result
        left = left[1:]
    while right is not empty:
    	append right[0] to result
        right = right[1:]
    return result

정확성 증명

• 길이가 0이나 1이면 이미 정렬되어 있어 그대로 반환한다.
• mergeSort를 통해 배열을 두분으로 나누고 각 배열을 합치면서 각 작은 원소를 넣어가며 배열을 비워가며 정렬한다. 마지막에 남은 배열을 채워넣는 식으로 정렬한다.
• 이 과정을 반복하면 항상 정렬된 상태를 유지한다. 그렇기 때문에 재귀로 mergeSort 또한 항상 정렬된 상태를 유지한다.

시간 복잡도 계산

전체 시간 복잡도를 $T(n)$이라고 한다면 배열을 분할한 후 정렬하는 시간은 $T(\frac{n}{2})$이다. 이런 배열이 각 왼쪽, 오른쪽으로 분할되어 2개이기 때문에 $2T(\frac{n}{2})$라고 할 수 있다. 여기서 각 분할이 합쳐지면서 각 n개의 원소를 비교하면서 걸리는 시간이 n개라고 할 때, 연산 시간을 상수로 두어 c라고 할 수 있다. 결과적으로 $T(n)=2T(\frac{n}{2})+cn$이라는 계산 결과가 나온다.
첫 번째 단계에서
$T(n)=2T(\frac{n}{2})+cn$
두 번째 단계에서
$T(\frac{n}{2})=2T(\frac{n}{4})+c\frac{n}{2}$
이므로 첫 번째 단계에 대입하면
$T(n)=4T(\frac{n}{4})+2cn$
세 번째 단계에서
$T(\frac{n}{4})=2T(\frac{n}{8})+c\frac{n}{4}$
이므로 두 번째 단계에서 얻어진 식에 대입하면
$T(n)=8T(\frac{n}{8})+3cn$
결과적으로 각 단계를 k단계에 의해 일반화하면
$T(n)=2^kT(\frac{n}{2^k})+kcn$이다.
배열의 길이가 1일 때, 바로 반환하므로 $T(1)=1$이고 이를 적용하기 위해 $\frac{n}{2^k}=1$이라고 한다면 $k=\log_{2}{n}$이므로 이를 대입하면
$T(n)=2^{\log_{2}{n}}T(1)+(\log_{2}{n})cn=nT(1)+cn\log_{2}{n}=n+cn\log_{2}{n}$이므로 $n\log_{2}{n}$의 변화 폭이 더 크기 때문에 최종적인 시간복잡도는 $T(n)=O(n\log{n})$이다.

문제 3

수학적 귀납법에 의해, 배열의 크기가 2인 경우, a가 b보다 크면 서로 바꿔서 오름차순으로 정렬한다.
배열의 크기가 2보다 큰 경우는 배열의 크기가 n인 경우, 배열을 세부분으로 나누어서 첫 번째와 세번째 부분은 동일한 부분 배열을 정렬하고 두 번쨰 부분은 나머지 배열을 정렬한다. 그렇기 때문에 세 부분 모두 정렬되어 전체 배열을 항상 정렬된다.

문제 4

각 단계에서 n이 배열 길이라고 할 때, 길이가 2일 때는 한번의 스왑 연산이 일어나기 때문에 $O(n)$이고 한번의 단계에서 n의 길이를 $\frac{2}{3}$배로 줄어들고 이 연산이 3번 일어나기 때문에 시간복잡도 식을 먼저 구하면 $T(n)=3T(\frac{2n}{3})+O(1)$이라고 할 수 있다.
이 때 배열의 깊이를 먼저 구하면 배열이 각 단계에서 2/3배의 연산으로 인해 줄어듬으로 이를 일반화하면, 재귀 호출의 깊이 $d$는 배열 크기가 1이 될때까지의 단계 수 이므로 전체 길이 $n$에 $(\frac{2}{3})^d$를 곱한게 1보다 같거나 작아질 때의 식을 풀면 된다.
$(\frac{2}{3})^dn\leq{1}$
$d\log{\frac{2}{3}}\leq\log{\frac{1}{n}}$
$d\leq\log_{\frac{3}{2}}{n}$
$d=\log_{\frac{3}{2}}{n}$
각 깊이, 즉 단계마다 최대 3번의 재귀 호출(함수)가 발생하고 각 호출마다 최대 한번의 스왑함수가 발생한다.
그렇기 때문에 각 단계당 3번의 스왑함수가 발생하며 이것이 또 3번의 재귀 함수의 의해 늘어나므로 k단계라고 할 때 연산의 횟수는 $1+3+3^2+3^3+...+3^{d-1}$이라고 할 수 있다.
$d=\log_{\frac{3}{2}}{n}$이므로 이를 사용해서 기하급수의 합으로 수열을 풀면
$\sum_{i=0}^{d-1}3^i$$=\frac{3^d-1}{3-1}=$$\frac{3^{\log_{\frac{3}{2}}{n}}-1}{2}$이고 여기서 $3^{\log_{\frac{3}{2}}{n}}=n^{log_{3/2}{3}}$이므로 약 $n^{1.709}$이다. 따라서 전체 식으로 봐도 n의 제곱항이 가장 크므로 시간복잡도는 약 $O(1.709)$이며 대략 $O(nlogn)$과 비슷하다.

문제 5

배열이 정수가 증가하는 순으로 저장되어 있고 인덱스의 값과 배열에 해당 인덱스에 저장된 값과 같은 것을 찾는 것이기 때문에 이진탐색으로 쉽게 찾을 수 있으며 자연수와 정수와 상관없이 동일한 과정으로 구할 수 있다. 그 이유는 인덱스이 값이 음수로 떨어지는 경우가 아니고 저장된 값이 정수인지 자연수인지만 다르기 때문에 항상 인덱스의 값이 0 밑으로 떨어지지 않기 떄문이다.

수도코드

function binarySearch(A,low,high):
	if low>high:
    	return -1
    mid = (low+high)/2
    if A[mid]==mid:
    	return mid
    else if A[mid] > mid:
    	return binarySearch(A, low, mid-1)
    else:
    	return binarySearch(A, mid+1, high)

정확성 증명

이미 저장값이 오름차순으로 저장되어 있고 이진 탐색에 의해 각 단계에서 탐색 범위를 반으로 줄여가면서 재귀함수에 의해 동일하게 작동되기 때문에 이 방식은 올바르게 작동한다.

시간복잡도 계산

이진 탐색의 시간복잡도는 매 단계에서 탐색 범위를 반씩 줄여나가기 때문에 $O(\log_{2}{n})$의 시간복잡도를 가진다.

문제 6

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

class TreeNode {
    int value;
    List<TreeNode> children;

    public TreeNode(int value) {
        this.value = value;
        this.children = new ArrayList<>();
    }

    public void addChild(TreeNode child) {
        this.children.add(child);
    }
}

public class TreePrinter {

    public static void printTree(TreeNode node, String prefix) {
        System.out.print(prefix + "[" + String.format("%03d", node.value) + "]");

        if (node.children.size() > 0) {
            for (int i = 0; i < node.children.size(); i++) {
                TreeNode child = node.children.get(i);
                if (i == 0) {
                    System.out.print("--+--");
                    printTree(child, "");
                } else if (i == node.children.size() - 1) {
                    System.out.println();
                    printTree(child, prefix + "   L");
                } else {
                    System.out.println();
                    printTree(child, prefix + "   +");
                }
            }
        } else {
            System.out.println();
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(30);
        TreeNode child1 = new TreeNode(54);
        TreeNode child2 = new TreeNode(2);
        TreeNode child3 = new TreeNode(45);
        root.addChild(child1);
        root.addChild(child2);
        root.addChild(child3);
        child1.addChild(new TreeNode(1));
        child3.addChild(new TreeNode(123));

        printTree(root, "");
    }
}

문제 7

pourWater()함수에서는 각 배열에서 물을 담는 과정을 간단히 표현하고 있다. 한 쪽의 물이 더 많은 경우, 적은 쪽이 두배의 물이 되게 해야하므로 작은쪽의 크기만큼 빼고 그 크기만큼 작은쪽은 커지게 되어 두배가 된다. 이 함수를 사용하여 입력받은 세개의 수를 계속해서 고려하는데, 한 경우마다 각 물이 담긴 것을 따라보기 위해 큐를 두어 반복되게 한다. 한 케이스가 실행되면서 for문의 중첩으로 모든 경우를 테스트해보고 각 경우를 pourWater함수를 실행하면 된다. 이 때, 이 경우가 이미 한번 경험해본 경우, 다시 확인해볼 필요가 없기 때문에 모든 기록을 관리하는 set를 두어 다시 접근하지 않도록 한다. 그렇기에 새로운 케이스가 나올 경우, 각 경우를 큐와 세트에 넣어서 모든 케이스를 실행되게 해본다. 이 과정중 세개 중 하나가 0이되면 가능하므로 종료하고 큐가 모두 비었을 때, 즉 더 이상 새로운 케이스가 없을 경우에 0을 하나도 못만드는 경우 불가능으로 종료한다.

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    static class Tuple{
        int[] arr;
        public Tuple(int a,int b,int c){
            this.arr=new int[]{a,b,c};
        }
        public Tuple(int[] arr){
            this.arr=arr.clone();
        }
        @Override
        public boolean equals(Object obj){
            if(this==obj)return true;
            if(obj==null || getClass()!=obj.getClass()) return false;
            Tuple tuple=(Tuple)obj;
            return tuple.arr[0]==arr[0]&&tuple.arr[1]==arr[1]&&tuple.arr[2]==arr[2];
        }
        @Override
        public int hashCode(){
            return arr[0]*1000000+arr[1]*1000+arr[2];
        }
    }
    
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int num1=sc.nextInt();
        int num2=sc.nextInt();
        int num3=sc.nextInt();

        if(makeZeroL(num1,num2,num3)){
            System.out.println("가능");
        }else{
            System.out.println("불가능");
        }
    }
    public static boolean makeZeroL(int num1,int num2, int num3){
        Queue<Tuple> q=new LinkedList<>();
        Set<Tuple> visited=new HashSet<>();

        Tuple s_tuple=new Tuple(num1,num2,num3);
        q.add(s_tuple);
        visited.add(s_tuple);

        while(!q.isEmpty()){
            Tuple cur=q.poll();

            if(cur.arr[0]==0||cur.arr[1]==0||cur.arr[2]==0){
                return true;
            }

            for(int i=0;i<3;i++){
                for(int j=0;j<3;j++){
                    if(i!=j&&cur.arr[i]>0&&cur.arr[j]>0){
                        Tuple next=new Tuple(cur.arr);
                        pourWater(next.arr,i,j);
                        if(!visited.contains(next)){
                            q.add(next);
                            // System.out.printf("%d %d %d\n",next.buckets[0],next.buckets[1],next.buckets[2]);
                            visited.add(next);
                        }
                    }
                }
            }
        }
        return false;
    }
    public static void pourWater(int[] arr,int i,int j){
        if(arr[i]<arr[j]){
            arr[j]-=arr[i];
            arr[i]*=2;
        }else{
            arr[i]-=arr[j];
            arr[j]*=2;
        }
    }
}

문제 8

수도코드

기존의 재귀함수와는 다르게 memo 배열을 두어서 값이 나올때, 해당 값을 저장하여 재귀의 과정을 줄인다.

function 피보나치(n)
   if n<=0
      return "유효하지 않은 입력입니다."
   // 계산된 값을 저장할 배열을 생성
   memo = 크기 (n+1)인 배열을 -1로 초기화
   
   // 헬퍼 함수 정의
   function 피보나치_헬퍼(n)
      // 기조 조건
      if n==1 or n==2
         return 1
      
      // 이미 계산된 값이 있는지 확인
      if memo[n]!=-1
         return memo[n]
      
      // 값이 계산되지 않았다면 계산 후 저장
      memo[n]=피보나치_헬퍼(n-1) + 피보나치_헬퍼(n-2)
      
      return memo[n]
   // 헬퍼 함수 호출
   return 피보나치_헬퍼(n)

정확성 증명

• $F(1)$과 $F(2)가 1 반환
• 이미 계산된 피보나치 연산 부분을 배열에 저장하고 불러옴으로써 대체
• 나머지는 재귀적 구조가 메모리제이션에 의해 대체된다.

시간 복잡도

해당 n까지의 피보나치 수열의 계산이(즉, 함수가) 하나의 숫자를 처리하는데 한번씩만 실행되므로 n까지의 피보나치의 수열을 계산하는데 n번의 계산이 걸린다. 즉 시간복잡도는 $O(n)으로 개선된다.

문제 9

8번의 재귀를 사용하는 방법과 다르게 DP(Dynamic Programming)은 배열을 사용하는 점을 활용해 재귀를 사용하지 않고 반복문을 대신 사용한다. 이미 배열에 계산결과가 들어가기 때문에 같은 함수를 호출할 필요가 없기 때문이다.

수도코드

function 피보나치_DP(n)
	if n<=0
    	return "유효하지 않은 입력입니다"
    if n==1 or n==2
    	return 1
    // 크기 n+1의 배열을 생성하고 첫 두 값을 설정
    dp=크기 (n+1)인 배열
    dp[1]=1
    dp[2]=1
    
    // 작은 값부터 순서대로 계산
    for i from 3 to n
    	dp[i]=dp[i-1]+dp[i-2]
    
    return dp[n]

정확성 증명

$F(1)$과 $F(2)$의 결과가 1이고 각 $dp[i]$는 $dp[i-1]+dp[i-2]$로 계산되기 때문에 정확히 식 $F(i)$와 같다. 그렇기에 반복문이 끝나면 $dp[n]$의 계산이 되므로 $F(n)$이 증명된다.

시간 복잡도

기존의 재귀가 없이 배열에 저장해놓았다가 불러오기 때문에 $O(1)$의 연산이므로 반복문이 n번 수행되면서 시간복잡도는 구하고자하는 n크기만큼 수행되어 $O(n)$이 된다.

• 세 개의 방식, 재귀, 메모리제이션, DP의 방식중에서 DP의 방식이 가장 빠르다. 재귀의 방식은 시간복잡도가 $O(2^n)$이고 나머지는 $O(n)$이기 때문이다. 두개의 시간복잡도가 같지만 기본적으로 함수의 호출은 스택을 쌓는 방식으로 이루어지기 때문에 재귀에 의해 호출 스택이 깊어지면 시간이 길어질 수 있기 때문에 반복문을 통해 배열을 사용하는 DP의 방식이 더 효율적이다.

문제 10(행렬 자체를 모르겠음... so feat.GPT)

수도코드

function 행렬_곱_최소비용(p)
    // p는 크기 n+1의 배열로, 행렬의 크기를 나타냄

    n = p.length - 1
    m = 2차원 배열 크기 (n x n)로 초기화, 무한대로 채움
    s = 2차원 배열 크기 (n x n)로 초기화, 0으로 채움

    for i = 1 to n
        m[i][i] = 0 // 한 행렬을 곱하는 비용은 0

    for l = 2 to n // l은 행렬 체인의 길이
        for i = 1 to n-l+1
            j = i + l - 1
            m[i][j] = 무한대
            for k = i to j-1
                q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]
                if q < m[i][j]
                    m[i][j] = q
                    s[i][j] = k

    return m, s

정확성 증명

1.기조 조건 : $m[i][i]$는 한 행렬만을 곱할 때 비용이 0임을 나타내므로, 기저 조건이 올바르게 설정되었습니다.
2.재귀 관계: 주어진 $m[i][j]$는 최소 비용으로 'A_i'에서 'A_j'까지의 행렬을 곱하는 비용입니다. 이를 위해 모든 가능한 분할점 k에 대해 최소 비용을 찾습니다. 이때, 비용 q는 다음과 같이 계산됩니다.
$q=m[i][k]+m[k+1][j]+p[i-1]\times{p[k}\times{p[j]}$
여기서 $m[i][k]$와 $m[k+1][j]$는 이미 최적의 값으로 저장되어 있습니다.
3. 반복 구조: 행렬 체인의 길이 l을 2부터 n까지 증가시키면서 최적의 분할점을 찾습니다. 이는 동적 프로그래밍의 원리로, 작은 부분 문제부터 해결하여 점차 큰 문제로 확장해 나갑니다.

시간복잡도

삼중 for문에의해 시간복잡도는 $O(n^3)$입니다.

문제 11

수도코드

처음 배열의 원소로 시작 점을 잡고 현재 요소를 포함한 최대 합인 max_ending_here와 부분열의 최대 합인 max_so_far를 초기화 시켜준다. 그리고 남은 원소인 인덱스 1부터 n-1까지 for문으로 순차적으로 진행하면서 현재 요소를 포함하는 경우를 고려해가고 그 경우를 또 최대합과 비교해준다. 이렇게 나누는 이유는 부분열이 현재의 원소를 포함하지 않을 수도 있기 때문에 따로 기록해두어야 한다.

function 최대_연속_부분합(arr)
	n=arr.length
    max_so_far=arr[0]
    max_ending_here=arr[0]
    
    for i from 1 to n-1
    	// 현재 요소를 포함한 최대 합을 갱신
    	max_ending_here = max(arr[i],max_ending_here+arr[i]
        // 지금까지의 최대 합을 갱신
        max_so_far=max(max_so_far,max_ending_here)
    return max_so_far

이를 $Kadane's Algorithm$이라고 한다는 점을 처음알았다...

정확성 증명

초기 상태에서 max_so_far과 max_ending_here을 첫 번째 원소로 초기화 시켜 둔다. 이는 최대값을 구하는 경우이기 때문에 이렇게 둘 수 있다. 각 원소를 순회하면서 두개의 변수를 업데이트하고 현재의 경우를 기점으로 현재의 원소를 포함하는 부분합 중 최대값을 구한 후, 이를 전체의 경우와 비교해서 정답을 기록해 둔다. 즉, 이전까지의 최대합을 max_ending_here로 계산해두고 이 계산을 다시 다음 원소를 포함하는 경우 사용하는 식으로 다이나믹 프로그래밍 식으로 사용된다.

시간 복잡도

for문을 통해 전의 계산을 사용하기 때문에 각 원소 당 한번의 연산을 수행한다고 할 수 있기 때문에 배열의 원소의 갯수가 n개일 때, 시간복잡도는 O(n)이라고 할 수 있다.

문제 12

수도코드

대표적인 다이나믹 알고리즘 중 하나인 LIS(Longest Increasing Subsequence) 알고리즘 중 하나이다. 전체 수열에서 몇개의 원소를 선택하였을 때, 그 순이 배열의 나열 순으로 가져다 놓았을 때 오름차순이나 내림차순으로 정렬되어 있는 원소의 최대 길이를 구하는 문제이다.
한 배열이 있을 때, 순차적으로 배열을 순회한다면 특정 원소일 때의 최대 길이, 즉 특정원소가 포함되는 최대 길이는 현재의 원소보다 작은 전의 원소들 중의 dp값(다른 원소를 포함하는 최대 길이)중 가장 큰 값보다 +1을 한 길이인 것이다. 그렇기에 전의 모든 원소를 순회하며 그 원소의 값이 현재의 원소보다 작다면 다음 원소로 현재의 원소가 올 수 있기 때문에 그 원소의 dp값에 +1을 하여 max값을 통해 dp를 갱신해준다. 최종적으로 꼭 현재의 원소의 dp가 최대 길이라는 보장이 없기 때문에 모든 dp중의 최대값을 구해주어야 한다.

function 가장_긴_증가하는_부분수열(arr)
	n=arr.length
    if n==0
    	return 0
    dp=array of size n, initialized with 1
    
    for i from 1 to n-1
    	for j from 0 to i-1
        	if arr[i]>arr[j]
            	dp[i]=max(dp[i],dp[j]+1)
                
    return max(dp)

정확성 증명

모든 dp의 배열을 1로 초기화하므로써 각 원소의 초기의 최대 길이는 1이므로 이것이 성립한다. 각 원소까지의 최대 길이는 그 전의 최대 길이들의 저장된 값을 사용하여 계산하므로 최적화할 수 있다.

시간 복잡도

이중 for문을 사용하고 재귀를 사용하지 않기 때문에 시간복잡도는 $O(n^2)$라고 할 수 있다.