WIL

1/22 WIL

달리는 꿈나무 2023. 1. 22. 20:48

1.  알고리즘 관련 공부

이번 주는 공부했던 알고리즘 지식을 정리하려 한다.

 

 

피보나치 수열을 통한 동적 계획법의 개념

 

동적 계획법 (Dynamic Programming)

  • DP, 다이내믹 프로그래밍이라 불린다.
  • 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 큰 문제를 해결하는 것이다.
  • 특정 알고리즘이라기 보다는 하나의 문제 해결 패러다임이다.
  • 일반적인 재귀 방식을 사용하면 동일한 작은 문제들의 값이 여러번 반복되어 시간복잡도가 늘어난다.
  • 이를 해결하기 위해 작은 문제의 값들을 저장하여 중복 계산을 제거하는 DP가 사용된다.
  • DP를 사용하기 위해서는 메모이제이션, 작은 문제들의 값을 저장하는 리스트가 필요하다.
  • 수학적 귀납법, 점화식을 생각해서 풀어야한다.
  • 수학적 귀납법 => n = 1일 때, n = 2일 때, n = 3 일 때....... , n = 주어진 조건 일 때 == Bottom-Up
  • 점화식, 즉 반복되는 공식을 도출해야한다. ex) 피보나치 수열 f(n) = f(n-2) + f(n-1) , n은 인덱스
  • DP를 사용하기 위해서는 두 가지 조건이 필요하다.
    • 1. 동일한 작은 문제들이 반복되는가?
      • 문제들의 값이 계속 반복적으로 계산이 된다.
      • 같은 값들이 부분 문제들에서 나온다면 이미 계산한 결과 값을 사용하면 되는 것이다.
    • 2. 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 찾을 수 있는가?
      • 메모이제이션에서 저장된 최적 결과 값을 다음 문제에서 사용이 가능한가?
      • 예를 들어 A에서 B를 거쳐 C를 갈 때 최단 거리를 구한다고 가정하자.
      • A에서 바로 C로 가는 루트를 구하기 보다 먼저 A에서 B로 가는 최단 루트를 찾는다.
      • 여기서 A에서 B로 가는 최단 루트가 부분 최적 결과 값이 된다.
      • 앞으로 해야할 것은 A에서 B로 가는 최단 루트 값을 저장하고(메모 하고)
      • B에서 C로 가는 최단 루트를 찾은 다음 저장한 값을 사용하여 결과를 도출하면 된다.
      • 즉, 전 인덱스들의 부분 최적 결과 값 + 이후 인덱스의 계산 결과 => 더 큰 문제 해결이 된다.
  • Top-Down, Bottom-Up 두 가지 방향으로 나뉜다.
    • Top-Down
      • Top-Down 방식은 일반적인 재귀 함수에서 Cutting Edge(중복 제거) 코드를 추가하여 최적화 하는 것이다.
      • 가장 큰 문제를 쪼개는 것 부터 시작하는 것이다. -> 분할 정복과 유사
      • 여기서 중복 제거 코드를 넣기 위해 메모이제이션을 사용하여 중복이 되는지 체크하고 중복이라면 메모에서 꺼내 사용한다.
    • Bottom-Up
      • for문(반복문)을 통해 인덱스가 1일 때부터 시작! 점화식을 이용하여 인덱스마다의 결과값을 메모이제이션하여 다음 인덱스 값에 사용
      • memo 리스트 (메모이제이션)를 이용하여 점화식을 제작해서 아래에서 위로 올라가는 것이다.
      • Bottom-Up방식을 진정한 DP라고 보는 시각이 많다.
  • 중요한 것은 가장 작은 문제의 상태를 알아야한다. 인덱스가 0 혹은 1 혹은 2일 때 주어지는 가장 작은 결과값
    • 피보나치 수열의 경우 f(0)과 f(1)의 상태이다. 이 둘은 계산할 것도 없이 1이다. 이를 메모하여 n = 2의 상황을 도출한다.

 

 

예제) 네트워크 선 자르기(Top-Down : 재귀, 메모이제이션)

 

현수는 네트워크 선을 1m, 2m의 길이를 갖는 선으로 자르려고 합니다. 예를 들어 4m의 네트워크 선이 주어진다면

1) 1m+1m+1m+1m

2) 2m+1m+1m
3) 1m+2m+1m
4) 1m+1m+2m

5) 2m+2m

 

의 5가지 방법을 생각할 수 있습니다. (2)와 (3)과 (4)의 경우 왼쪽을 기준으로 자르는 위치가 다르면 다른 경우로 생각한다.
그렇다면 네트워크 선의 길이가 Nm라면 몇 가지의 자르는 방법을 생각할 수 있나요?

 

▣ 입력설명
첫째 줄은 네트워크 선의 총 길이인 자연수 N(3≤N≤45)이 주어집니다.

 

▣ 출력설명
첫 번째 줄에 부분증가수열의 최대 길이를 출력한다.

 

▣  입력예제 1

7

 

▣  출력예제 1

21

 

 

해설)

가장 기초적인 다이나믹 프로그래밍 문제이다. Bottom-Up 방식으로 진행한다면 주어진 예제에서 1일 때부터 시작이다.

수열의 각 부분은 순서를 지켜야한다. 그리고 길이는 1 또는 2이므로 가장 작은 값은 1과 2라는 것을 알 수 있다.

Bottom-Up은 시작 지점부터 for문을 돌린다. 여기서 포인트는 메모 리스트도 만드는 것이다. 

메모리스트의 값은 0으로 범위는 N+1로 해주자 인덱스 1부터 값을 넣어줄 것이다.

n=1은 값이 1이므로 메모리스트[1]에 1을 넣자, n=2은 값이 1+1, 2 즉, 2가지므로 메모리스트[2] = 2이다.

n=3은 n=2일 때와 1이 남는 경우, n=1과 2가 남는 경우로 나눌 수 있다.

즉 앞에서 전에 존재하는 최대 값인 f(2)와 f(1)을 더하는 것이다.

이는 곧 n=3 일 때 -> f(2) +f(1)이 된다는 것이다. 결과값은 3이 된다. 이후 메모리스트[3] = 3 메모

n=4일 때 는 n=3일 때와 남은 길이가 1일 때, n=2일 때와 남은 길이가 2일 때로 쪼갤 수 있다.

f(3)과 f(2)를 가져와 더한다 -> 5

이런 식으로 마지막 길이가 1 또는 2 이렇게 두 가지로 나뉠 때 전에 계산한 결과들을 가져오면 되는 것이다.

아래 코드 해설은 Top-Down 방식도 적었으니 비교를 해보자.

# 동적계획법 => Dynamic Programming

# 어떤 문제가 존재하는데 단번에 풀기 어려우면 
# 작은 단위로 직관적으로 줄여서 해결한다.
# 가장 작은 단위에서 값을 구하면 그것을 메모(Memoization)해서 저장한다.
# 이것을 단위를 조금씩 크게해 전 단위에서 구한 값을 이용해서 값을 구하고
# 그것을 저장한다.

# 고등학교 때 배운 수열, 점화식을 생각하자
# 이산수학에서 배웠던 귀납적 추론을 생각하자

# 이 문제를 보자 => 1번은 1, 2번은 2, 3번은 4
# 규칙을 찾아야한다. 등차수열일지 등비수열일지
# 점화식을 떠올리자 f(n) = 2f(n-1)

# 이렇게 n = 1일 때, n = 2일 때 ... n = n + 1 일 때 까지 올라가는 것을 바텀 업(Bottom - Up) 기법이라고 한다.


# dy라는 리스트를 만들고 n(길이)이 = 1 일 때 방법의 수를 기록
# 그 다음 n = 2 일 때 방법의 수와 n = 1일 때 방법의 수를 합쳐서 기록
# 1(n = 1) + 1
# 3 부터 점화식을 알아낸다.

# 길이 3에서 맨 마지막의 길이가 1일 때 전에 구해 놓은 2가 경우의 수가 된다.
# 2(n = 2)
# 그 다음 길이 3에서 마지막의 길이가 2일 때 남은 1이 경우의 수 n = 1일 때 경우의 수가 된다. 
# 1(n = 1)
# => 2 + 1 = 3

# 길이 4에서 맨 마지막의 길이가 1일 때 
# n = 3의 경우의 수가 되므로 3을 가져온다.
# 길이 4에서 맨 마지막의 길이가 2일 때 
# n = 2의 경우의 수가 되므로 2를 가져온다.
# => 3 + 2 = 5

# 길이 5에서 맨 마지막의 길이가 1일 때
# n = 4의 경우의 수가 되므로 5를 가져온다.
# 길이 5에서 맨 마지막의 길이가 2일 때 
# n = 3의 경우의 수가 되므로 3을 가져온다.
# => 5 + 3 = 8

# 길이 6에서 맨 마지막의 길이가 1일 때
# n = 5의 경우의 수가 되므로 8을 가져온다.
# 길이 6에서 맨 마지막의 길이가 2일 때
# n = 4의 경우의 수가 되므로 5를 가져온다.
# => 8 + 5 = 13


# Top - down 기법
# 재귀함수로 구현
# DFS(7)의 경우 DFS(6) + DFS(5)가 되고
# DFS(6)의 경우 DFS(5) + DFS(4)가 되듯이
# 쭉 내려가는 것이다. (전위 순회)
# DFS(2) + DFS(1) 이 될 때까지 내려가면
# 계산을 시작한다.
# 아래에서 올라올 때 기록할 곳을 만들어서
# 메모한다.
# memo = [0]*(n+1)
# 올라갈 때 겹치는 연산이 발생하면
# 메모한 값을 가져온다.
# memo[2]값이 존재하면
# DFS(3)을 돌릴 떄 memo[2]를 가져오면 된다.
# 즉, return memo[n]
# cut edge 
# 메모를 해놓고 불필요한 연산을 제거한다.


# 바텀 업 기법
n = int(input())

# 메모할 공간 , 메모이제이션
memo = [0] * (n+1)
# 1번부터 사용하려고 n+1개
# 직관적으로 알 수 있는 것은 초기화를 해주는 것이 좋다.
memo[1] = 1
memo[2] = 2
    
for i in range(3,n+1): 
    #       점화식
    memo[i] = memo[i-1] + memo[i-2]

print(memo[n])



def DFS(len):
    if len == 1 or len == 2:
        return len
    
        # edge cut, 메모이제이션을 통한 다이나믹 프로그래밍
    if memo[len] != 0:
        return memo[len]

    else:
        # 메모이제이션
        memo[len] = DFS(len-1) + DFS(len-2)
        return memo[len]

if __name__ == '__main__':

    # 탑 다운 기법

    n = int(input())
    memo = [0] * (n+1)
    print(DFS(n))

 

 

 

 

 

 

최장 부분 증가 수열 원리

 

 

최장 부분 증가 수열(Least Increasing Subsequence)

  • 원소가 n개인 배열의 일부 원소를 골라내어 만든 부분 수열 중에 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 한다.
  • 일반적으로 최장 증가 부분 수열의 길이가 얼마인지 푸는 간편한 방법은 DP를 이용하는 것이다.
    • 메모 리스트를 생성한다. 모든 값은 0으로, 길이는 n+1로
    • 맨 처음 존재하는 수열의 값의 최장 증가 수열의 값은 항상 1이다. 메모 리스트 1번 인덱스에 넣어주자
    • 이후 for i in range(2, n+1) => 수열 끝까지 돌면서 체크
    • 이후 이중 for(j)문을 사용한다. 이 for문은 현재 인덱스인 i에서 역방향으로 수들을 체크한다.
    • 주어진 수열이 arr라고 할 때 arr[j]가 arr[i] > arr[j]이면서(현재 인덱스에 존재하는 arr의 값보다는 작아야 증가 수열이 된다.)
    • 역방향에 있는 수들 중 그 memo값이 가장 크다면(부분 수열의 갯수가 가장 크다면) 최장 증가 부분 수열에 적합하다.
    • 역방향에 존재하는 j인덱스의 memo리스트 값, 즉 부분 문제의 최적 값을 가져와서 1을 더해(i 인덱스의 숫자가 추가된 것)  i인덱스의 memo에 넣는다.
    • memo의 값들 중 가장 큰 수를 찾아서(부분 수열의 갯수가 가장 많다면) 정답에 넣는다.
  • 보통 이 문제는 수열을 쥐어주어 만들 수 있는 수열의 최대 갯수를 구하는 문제거나 겹치지 않게 선을 연결하여 만들 수 있는 최대 갯수를 물어본다.

 

 

예제) 최장 부분 증가 수열

 

N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하라. 예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3 이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내어 길 이가 5인 최대 부분 증가수열을 만들 수 있다.

 

▣ 입력설명
첫째 줄은 입력되는 데이터의 수 N(2≤N≤1,000, 자연수)를 의미하고, 둘째 줄은 N개의 입력데이터들이 주어진다.

▣ 출력설명
첫 번째 줄에 부분증가수열의 최대 길이를 출력한다.

 

▣ 입력예제 1
8

5 3 7 8 6 2 9 4

 

▣ 출력예제 1

4

 

해설)

최장 부분 증가 수열은 정확한 공식이 존재한다. 이중 for문을 통해 현재 인덱스의 arr값 보다 작은 arr값을 가지는 j 인덱스들을 찾으면서

그 인덱스의 memo 값들 중 가장 큰 값을 가지는(최장) j 인덱스를 찾아서 현재 인덱스의 memo에 +1을 하고 넣어준다.

이 memo리스트가 다 채워졌을 때 가장 큰 값을 찾으면 최장 부분 증가 수열의 최대 길이를 찾을 수 있다.

 

# 인덱스를 돌면서 현재 인덱스의 수가 부분 중가 수열의 마지막 항이라고 생각하자
# 부분 증가 수열 => dp 점화식 문제

# memo를 만들어 각 자리가 마지막 항이 되는 수열의 최대 길이를 준다.
# 다음 memo에 전에 수열을 만들 수 있는 값들 중 가장 큰 값에 + 1

# 즉 전 항들이 가능한 값들 중 가장 큰 값을 정해서 + 1 하는 것이다.

# 그 다음 memo 값들 중에 가장 큰 값이 최대 길이가 된다.


if __name__ == "__main__":
    n = int(input())
    # 1번 부터 인덱스에 맞춰서 할게용
    arr = list(map(int, input().split()))
    arr.insert(0, 0)

    memo = [0] * (n+1)
    memo[0] = 0
    # 1번 인덱스는 1로 초기화
    memo[1] = 1

    res = 0

    # for 문을 두 번 돈다.
    for i in range(2,n+1):
        max = 0
        # i 바로 앞에서 부터 돌아야하니까 i-1이 되어야한다.
        # 즉 i번째면 i 앞쪽 부터 1번까지 돌면서 arr[i]보다 작은 값을 찾는다.
        for j in range(i-1, 0 , -1):
            # 부분 증가 수열의 조건을 만족할 때
            if arr[j] < arr[i]:
                if memo[j] > max:
                    max = memo[j]    
            memo[i] = max + 1
        # memo 값 중에 가장 큰 값을 찾자 => 최대 길이
        if memo[i] > res:
            res = memo[i]
    
    print(res)

        

    # 최대 부분 증가수열은 또 하나의 리스트가 필요하다.