[정글] 알고리즘 특강 (2)

Divide & Conquer

• 분할정복 방식의 대표적인 예 : merge sort
  • 둘로 나눔 (나눈 문제들은 원래 문제와 같은 입려값을 가져야 함)
  • 각각 정렬
  • 합침
• 최댓값 찾기를 분할 정복 방식으로 구현해보자
  • 배열 A를 두 부분 배열 A1, A2로 나눔
    -> 나눌 때 부분 배열 각각이 다시 최대값 찾는 단계로 재귀호출될 것이라고 생각하기
  • 그리고 원래 문제를 다시 생각해봄
    -> A1의 최댓값, A2의 최댓값 둘 중 더 큰 값이 A의 최댓값이다.
  • 슈도코드 :

max(a[0...n-1])
if n=1 return a[0]
mid <- n/2
m1 <- max(A[0...mid])
m2 <- max(A[mid+1...n-1]_
if m1 > m2
	then return m1
    else return m2
    
//참고 : 재귀호출의 시간 복잡도 : T(n) = 2T(n/2) + O(1) 
// 재귀호출에서 사용되는 시간 (T로 표현. 인스턴스 사이즈가 n/2로 줄어듦 (리턴되기 전까지 n/2))
// + 재귀호출이 아닌 곳에서 사용되는 시간

• 이진탐색 또한 분할정복이다.
  • 중간값을 k와 비교한 후 배열의 절반에 대해서만 탐색을 계속 함
  • 즉 남은 n/2 크기의 부분 배열에 대한 subproblem을 풀면 문제 해결
    • 탐색 관점에서 생각하면 한 번 비교하고 탐색 범위를 절반으로 줄이고 있음
    • 원하는 답을 찾기 위해 탐색 범위를 줄여나가는 것이 골자
  • 이진탐색의 경우는 두 부분 모두 recursion태울 필요 x
  • 정렬된 상태이기 때문에 찾는 값이 없는 부분이 어딘지 알고 있음
    -> 이 부분은 재귀호출로 계속 찾을 필요 없음
• 두 자리 정수 x, y의 곱셈을 분할 정복으로 풀어보기
  • x와 y의 자리수를 반으로 나누기 
    • x = a*10^n/2 + b 
    • y = c*10^n/2 + d
  • x*y 식을 전개하면 a*c, a*d, b*c, b*d값(recursion으로 계산)을 알면 x*y값을 구할 수 있다는 것을 알 수 있다.
  • 시간복잡도? 
    • recursion part : n/2사이즈의 instance들을 4번 호출
    • not recursion part : 10의 거듭제곱을 얼마나 곱하는지, 더하기 연산을 얼마나 하는지 등을 계산해보면 됨
    • T(n) = 4T(n/2) + O(n) 즉 O(n^2)
  • 곱셈 O(n^2)보다 더 빠르게 안 되는 걸까?
    • bc+ad=ac+bd-(a-b)(c-d) 공식을 활용하면 recursive call을 4번에서 3번으로 줄일 수 있음
    • T(n) = 3T(n/2) + O(n) 즉 O(n^log2^3) = O(n^1.584..)

Backtracking

• n-queen 문제
  
  • goal : sequence of queen position을 찾는 것
  • contraints : queen은 각 row 당 하나씩만 놓을 수 있음, 서로 공격할 수 없게 놓아야 함
  • decision : 각 row에서 queen을 어디 놓을지 결정하기

• 한 줄에 퀸을 하나만 놓는다
• 다음 줄로 간다
• 아무 데도 놓을 수 없으면 이전 단계로 백트래킹한다
• 놓을 수 있으면 다음 줄에 놓으러 간다
• 모든 줄에 놓았으면 정답을 찾은 것
• -> 모든 경로를 깊이 우선 탐색하고있다는 것을 알 수 있음

placequeens(Q[1..n], r):
	if r=n+1
    	print Q[1..n]
    else
    	for j <- 1 to n
        	legal <- True
            for i <- 1 to r-1
            	if(Q[i]=j) or (Q[i]=j+r-i) or (Q[i]=j-r+i)
                	legal <- False
            if legal
            	Q[r]<-j
                placequeens(Q[1..n], r+1) //recursion

• 최선의 결정(decisioin)을 반복하여 점진적으로 답을 만들어 나간다.
• Tries to construct a solution incrementally by a sequence of correct or best "decisions"
• 그 길이 옳은지 아닌지 알 수 있는 방법? 가보지 않고서는 아직 알 수 없다.
• 따라서 best decision은 모든 선택지를 모두 고려하여 임시적으로 가본 후에 backtracking하는 것

 

• 최장 증가 부분 수열 문제 (LIS) 백트래킹으로 풀기
  • increasing subsequence 중 길이가 가장 긴 것이 무엇인지 찾는 문제
  • (1) 어떤 결정(decide)의 연속(sequence)을 통해 LIS를 만들어내기 -> 어떤 결정인가?
  • 임의의 subsequence는 각 원소를 포함시킬지 말지 결정함으로써 만들어짐
  • 그런 선택을 함으로써 정답에 가까워지냐 아니냐를 판단해서 백트래킹하든지 계속 탐색하든지 선택하면 됨
    • 예) 3141592653  5897532384626
    • 1456까지는 선택했다. 그 다음부터 선택할지 말지 계속 정해보자
    • 5는 6보다 크므로 선택하지 않는다.
    • 8은 6보다 크므로 선택 가능. 그리고 subsequence도 1 증가한다. 그런데 8을 넣는 것이 '최선'일까?
    • 8을 무시하는 것이 최선일 수도 있다.
    • 따라서 8을 포함시키는 경우, 포함시키지 않는 경우를 분기시켜 둘 다 시행해보고 더 불리한 것을 무시(백트래킹)하는 방법을 사용하자.
    • 따라서 백트래킹 알고리즘은 8을 포함시킨 후 / 포함시키지 않은 후 나머지 결정을 recursion태우기 -> 두 가지로 분기됨
    • 둘 중에 더 긴 increasing subsequence가 나오는 것으로 결정
  • (2) j번째 원소 A[j]를 포함시킬까 말까를 결정하기 위해 임시로 포함시키거나 포함시키지 않은 결과를 recursion태우기
  • (3) 이런 방법이 동작하려면 지난 결정들에 대한 어떤 정보를 기억해야 하는가? 
    • 마지막 원소만 기억하면 됨. 마지막 원소보다 더 큰 숫자이기만 하면 되므로
    • 따라서 recursive call을 할 때 마지막 원소를 넘겨주기

lisbigger(prev, a[1..n]): #prev값보다 커야 함
	if n=0
    	return 0
    else if a[1]<=prev
    	return lisbigger(prev, a[2..n])
    else
    	skip <- lisbigger(prev, a[2..n])
        take <- lisbigger(a[1], a[2..n])+1
        return max{skip, take}

 

• 최장 증가 부분 수열을 백트래킹으로 풀면 모든 가능한 증가하는 부분 수열을 탐색해야 한다.
• 즉 각 원소가 선택되는 경우, 선택되지 않는 경우를 고려하며 모든 경우를 탐색해야 한다.
• 이 경우 시간 복잡도는 O(2^n)이다.
• LIS를 효율적으로 해결하려면 dp로 중복 계산을 줄여야 한다.

# top-down(memoization)
def lisbigger(prev_index, curr_index, arr, memo):
    if curr_index == len(arr):
        return 0
    
    if (prev_index, curr_index) in memo:
        return memo[(prev_index, curr_index)]
    
    # 현재 원소를 선택하지 않는 것이 최선일 수도 있음 -> 확인하기 위해 재귀 보내기
    skip = lisbigger(prev_index, curr_index + 1, arr, memo)
    
    # 현재 원소를 선택하는 것이 최선일 수도 있음 -> 확인하기 위해 재귀 보내기
    take = 0
    if prev_index == -1 or arr[curr_index] > arr[prev_index]:
        take = 1 + lisbigger(curr_index, curr_index + 1, arr, memo)

    # 같은 문제를 여러 번 중복해서 구하고 있을 때 그 값을 dp에 저장해두기
    memo[(prev_index, curr_index)] = max(skip, take)
    return memo[(prev_index, curr_index)]

arr = [10, 22, 9, 33, 21, 50, 41, 60]
memo = {}
print(lisbigger(-1, 0, arr, memo))  # 출력: 5 (10, 22, 33, 50, 60)

# bottom-up
def lis_dp(arr):
    n = len(arr)
    dp = [1] * n  # 최소 LIS 길이는 1

    for i in range(n):
        for j in range(i):
            if arr[j] < arr[i]:  # 증가하는 경우
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

arr = [10, 22, 9, 33, 21, 50, 41, 60]
print(lis_dp(arr))  # 출력: 5

Dynamic Programming

• 피보나치 수열을 dp로 풀기
  • 피보나치 수열을 재귀로 구현하면 매우 느리다.
    -> 시간 복잡도가 지수함수임. recursion tree를 그려보면 호출 횟수가 기하급수적으로 늘어나는 것을 확인할 수 있음
  • dp는 테이블 채우기가 아니고.. recursion 알고리즘에서 중복 연산이 나올 때 그 부분을 재사용해서 효율적으로 만들어주는 방법임
  • k번째 답을 구하기 위해서는 k-1, k-2번째 등의 답이 필요하기 때문에 k번째 답을 k-1, k-2번째 답으로 표현할 수 있음
    -> 점화식
  • 그리고 k-1, k-2번째 답을 구하기 위해서는 재귀, 백트래킹을 이용하는 것
  • DP is recursion without repitition
  • DP를 사용해 문제를 해결하는 일반적인 과정
    • 문제를 해결하는 recursive한 패턴 혹은 점화식을 찾아내야 함
    • 계산할 값이 무엇인지 결정하기(어떻게 계산해야 하는지 생각 x) 그것에 대한 점화식 구하기
    • basecase부터 차곡차곡 table에 쌓아가는 방식으로 해결
• LCS (Longest Common Subsequence, 최장 공통 부분 수열)
  • a와 b는 배열 형식으로 주어졌다고 가정
  • l(i, j)는 a(1..i), b(1..j)사이의 lcs 길이로 정의하기
  • 두 배열을 탐색하다가 다른 문자가 나오면
    • a[k]의 값을 무시하고 a[k+1]부터 b[k]의 값과 매치되는지 계속 탐색하거나
    • b[k]의 값을 무시하고 b[k+1]부터 a[k]의 값과 매치되는지 계속 탐색해야 함
    • -> 두 분기 중 매칭 수가 더 많은 부분이 이김
  • base case : i 또는 j가 0일 때 (배열 a 또는 b가 공집합인 경우)
  • l(i, j)의 재귀적인 구조를 찾기

# 점화식
if a[i] == b[j]
	l(i, j) = l(i-1, j-1) + 1
if a[i] != b[j]
	l(i, j) = max(l(i-1, j), l(i, j-1))

 

• recursion: 알고리즘에서 가장 중요한 개념
• divide and conquer : 크게 자르는 recusion
• backtracking : 하나씩 떼어내는 recursion
• dp : 반복 계산을 없앤 recursion

재귀가 모든 알고리즘의 기초가 되는 개념이라는 사실을 알게 되었다.

그리고 재귀 알고리즘을 짤 때 점화식만 잘 찾으면 구체적으로 모든 케이스에서 코드가 어떻게 작동되는지 완벽히 이해하지 않아도 된다는 말을 듣고 재귀의 원리에 대해 조금 더 이해할 수 있게 되었다.

두 번째 특강 시간에는 분할 정복과 dp를 적용하기 위해서 문제를 어떤 방식으로 접근해야 하는지 자세하게 배울 수 있었다.

 

스스로 자료를 찾아서 공부하기만 했다면 모든 알고리즘을 관통하는 개념이 재귀인지 알 수 없었을 것 같다. 또한 유형을 파악하기 어려운 문제를 마주했을 때 먼저 문제를 작게 분할해본 후 재귀적으로 해결할 수 있는지부터 고려하고 가능하면 반복되는 문제가 있을 경우 dp, 아닐 경우 백트래킹으로 접근하는 방식을 배웠는데 이러한 접근은 앞으로 어려운 문제가 나올 때마다 적용할 수 있을 것 같다.