알고리즘-심화 알고리즘 (1)

동적계획법(Dynamic Programming: DP)

• 큰 문제를 부분 문제로 나눈 후 답을 찾아가는 과정에서, 계산된 결과를 기록하고 재활용하며 문제의 답을 구하는 방식
• 중간 계산 결과를 기록하기 위한 메모리가 필요
• 한 번 계산한 부분을 다시 계산하지 않아 속도가 빠름

vs.분할 정복/탐욕 알고리즘

• 분할 정복과의 차이
  -> 분할 정복은 부분 문제가 중복되지 않음
  -> DP는 부분 문제가 중복되어 재활용에 사용
• 그리디 알고리즘과의 차이
  -> 그리디 알고리즘은 순간의 최선을 구하는 방식: 특정 조건에서만 최적해
  -> DP는 모든 방법을 확인 후 최적해 구하는 방식: 항상 최적해 보장

동적 계획법 분류

• 타뷸레이션(Tabulation, tabularization)
  -> Bottom-Up 접근
  -> 작은 하위 문제부터 풀면서 올라감
  -> 모두 계산하면서 차례대로 진행: 단점.필요없는 연산을 함

• 메모이제이션(Memoization)
  -> Top-Down 접근
  -> 큰 문제에서 하위 문제를 확인해가며 진행
  -> 계산이 필요한 순간 계산하며 진행

동적 계획법 예시

• 피보나치 수열의 계산
  

동적 계획법 문제 풀이

1) 0-1 Knapsack 문제를 해결하세요!
당신은 capacity만큼의 무게를 담을 수 있는 배낭에 물건을 담고자 한다.
각 물건의 무게는 weight[i], 각 물건의 가치는 value[i]로 주어져 있을 때,
배낭에 담을 수 있는 가능한 물건들의 가치의 합 중 최대의 값을 구하시오.

def solution(capacity, weight, value):
    N = len(weight)
    C = capacity
    dp = [[0 for _ in range(C+1)] for _ in range(N+1)]

    for i in range(1, N+1):
        for w in range(1, C+1):
            if w >= weight[i-1]:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i-1]] + value[i-1])
            else:
                dp[i][w] = dp[i-1][w]
    
    return dp[N][C]


if __name__ == '__main__':
    capacity = 20
    weight = [4, 5, 2, 3, 6, 8, 5, 5]
    value = [5, 2, 6, 7, 1, 3, 4, 6]
    sol = solution(capacity, weight, value)
    print(sol)

2) 누리는 개발 공부를 하다 보니 삽으로 땅을 파는 데에 전문가가 되었다. 누리가 파내는 땅은 블록 형태로 구분되어있고, 각 블록은 제거하는 데에 서로 다른 에너지가 소비된다. 땅에 있는 첫 번째 블록은 깊이가 0부터 시작하며, 한칸씩 내려갈 때 마다 깊이가 1씩 증가한다. 누리가 블록을 제거할 수 있는 조건은 아래와 같다.

• 깊이 0에 위치한 블록은 자유롭게 제거할 수 있다.
• 깊이 d에 위치한 i번째 블록을 제거하려면, 깊이 d-1에 위치한 i-1, i, i+1번째 블록 중 하나가 제거되어 있어야 한다.
  누리는 깊이 depth의 n번째 블록에 위치한 화석을 발굴하려고 한다. 각 깊이별 블록을 제거하는 데에 필요한 에너지는 blocks에 저장되어 있다. 화석이 위치한 블록을 제거하는 데에 필요한 최소의 에너지를 구하시오. (단, n은 0부터 시작하며, 모든 깊이에는 동일한 숫자의 블록이 있다.)

def solution(depth, n, blocks):
    D = depth + 1
    N = len(blocks[0])

    dp = [[0 for _ in range(N)] for _ in range(2)]

    for i in range(N):
        dp[0][i] = blocks[0][i]
    
    for i in range(1, D):
        for j in range(N):
            if j == 0:
                dp[i%2][j] = min(dp[(i-1)%2][j:j+2]) + blocks[i][j]
            elif j == N-1:
                dp[i%2][j] = min(dp[(i-1)%2][j-1:j+1]) + blocks[i][j]
            else:
                dp[i%2][j] = min(dp[(i-1)%2][j-1:j+2]) + blocks[i][j]
    
    return dp[depth%2][n]

if __name__ == '__main__':
    depth = 3
    n = 3
    blocks = [[5, 6, 2, 6],
             [1, 6, 4, 9],
             [5, 6, 9, 4],
             [55, 14, 21, 14]]
    sol = solution(depth, n, blocks)
    print(sol)

3) 당신은 제로국으로 급파된 암살자로, 제로국의 주요 인사들을 암살하는 임무를 맡았다.
제로국에는 총 N개의 성이 있고 이 성들은 일정한 가격으로 원형으로 배치되어 있다.
당신은 조사원들을 통해서 다음과 같은 사실을 알아내었다.

• 각 성마다 주요 인사는 한 명씩 배치되어 있다.
• 각 성의 주요 인사를 암살했을 때의 보상은 rewards[i]로 주어진다.
• 하나의 성의 주요 인사를 암살할 경우, 인접한 성은 경계태세가 되어 침입할 수 없다.
  위 조건에서 달성할 수 있는 최대의 보상을 구하시오.
  단, 원형 배치의 특성상 첫 번째 성은 마지막 성과 인접해 있다.

def solution(N, rewards):
    # 0번째를 선택할 수도 있으면, N-1번째는 없다 친다.
    dp = [0 for _ in range(N-1)]
    dp[0] = rewards[0]
    dp[1] = max(dp[0], rewards[1])
    for i in range(2, N-1):
        dp[i] = max(dp[i-1], dp[i-2] + rewards[i])
    answer = dp[N-2]

    # 0번째를 선택하지 않고, N-1번째를 선택할 수 있게 한다.
    dp = [0 for _ in range(N)]
    dp[0] = 0
    dp[1] = rewards[1]
    for i in range(2, N):
        dp[i] = max(dp[i-1], dp[i-2] + rewards[i])
    
    return max(answer, dp[N-1])


if __name__ == '__main__':
    N = 6
    rewards = [5, 10, 5, 7, 5, 9]
    sol = solution(N, rewards)
    print(sol)

4) 정수로 이루어진 배열 nums가 주어지고, 0번 인덱스에서 시작한다고 하자.
최대 현재 인덱스의 숫자 nums[i]만큼 우측으로 이동이 가능하다고 할 때, 최종적으로 마지막 위치까지 도달할 수 있는지 여부를 논리형 값으로 출력하시오.

def solution(nums):
    N = len(nums)
    max_reach = 0

    for i in range(N):
        if max_reach >= i:
            max_reach = max(max_reach, i + nums[i])
            if max_reach >= N-1:
                return True
    return False


if __name__ == '__main__':
    nums = [3, 4, 1, 1, 0, 3]
    sol = solution(nums)
    print(sol)

백트래킹(Backtracking)

• 트리의 모든 노드를 탐색하는 과정에서, 유망하지 않은 쪽은 더 이상 탐색하지 않는 방법
• 용어
  -> 유망함 (Promising): 해가 될 가능성이 있는 경우 유망하다고 함
  -> 가지치기 (Pruning): 해가 될 가능성이 없는 경우 해당 노드와 그 자식 노드를 제외 하는 것
  -> 백트래킹 (Backtracking): 유망하지 않은 쪽으로 가지 않고 부모 노드로 되돌아 오는 것

N-Queen

• 𝑁 × 𝑁 체스판에 𝑁개의 퀸이 서로 위협적이지 않게 배치하는 경우의 수 문제
  

• 𝑁개를 모두 배치하기 전에, 하나씩 배치하면서 유망하지 않은 경우의 수 배제
  

• 𝑁개를 모두 배치하는 동안 계속 유망할 경우, 답안에 추가
  

백트래킹 예시 문제 풀이

1) N-Queen 문제를 해결하세요!
NxN 크기의 체스판이 있을 때, N개의 체스 퀸을 서로에게 위협이 되지 않게 놓는 모든 방법을 출력하시오.

def solution(N):
    result = []

    def dfs(path):
        def is_promising(path, n):
            new_i, new_j = len(path), n
            for i, j in enumerate(path):
                if new_j == j:
                    return False
                if new_i - i == abs(new_j - j):
                    return False
            return True

        if len(path) == N:
            result.append(path.copy())
            return
        
        for i in range(N):
            if is_promising(path, i):
                path += [i]
                dfs(path + [i])
                del path[-1]
    
    dfs([])
    return result


if __name__ == '__main__':
    N = 4
    sol = solution(N)
    print(sol)

2) 숫자 7193 은 7193 도 소수이고, 719, 71, 7 도 각각 소수이다.
n 이 주어졌을 때, n 자리 수 중에 위와 같은 소수를 찾는 프로그램을 작성하세요.

from math import factorial

def is_prime(x):
    # Wilson's Theorem
    if x < 2:
        return False
    return factorial(x-1) % x == x - 1


def solution(n):
    result = []

    def dfs(nums):
        def is_promising(nums, k):
            return is_prime(int(''.join(map(str, nums + [k]))))

        if len(nums) == n:
            result.append(int(''.join(map(str, nums))))
            return
        
        for i in range(10):
            if is_promising(nums, i):
                nums += [i]
                dfs(nums)
                del nums[-1]
    
    dfs([])
    return result



if __name__ == '__main__':
    N = 3
    sol = solution(N)
    print(sol)

3) 당신은 네트워크 전문가로, 회사의 모든 IP 주소를 관리하고 있다.
어느날 신입으로 들어온 사원이 사색이 되어 진땀을 흘리고 있는 모습을 보게 되었다.
어깨너머로 보니 사내의 모든 IP주소에서 구두점(.)을 실수로 삭제한 것으로 보인다.
당신은 수작업으로 IP주소를 하나하나 복구하고 있는 신입 사원을 보고, 몰래 프로그램을 만들어 도와주기로 마음먹었다.
프로그램의 입력은 숫자만으로 이루어진 문자열이며(ex. "2552552551", "16819501"),
프로그램의 출력은 이 문자열에 .을 3개 끼워 넣어 가능한 모든 IP 주소를 나열한 배열이다. (ex. ["255.255.255.1"]. ["168.195.0.1", "168.19.50.1"])
IP 주소의 각 숫자는 0 이상 255 이하의 숫자로만 이루어지며, 숫자 앞에 붙는 0(leading zero)는 허용되지 않는다.
위 조건에 맞는 프로그램을 작성하시오.
단, 결과 배열은 문자열 오름차순으로 정렬하여 출력하시오.

def solution(s):
    result = []

    def dfs(path):
        if len(path) == 3:
            result.append(make_address(path))
            return
        
        for i in range(1, 4):
            if is_promising(path, i):
                path += [i]
                dfs(path)
                del path[-1]

    def is_promising(path, k):
        tokens = []
        if len(path) == 0:
            tokens.append(s[:k])
        elif len(path) == 1:
            start = path[0]
            tokens.append(s[start:start+k])
        else:
            start = sum(path)
            tokens.append(s[start:start+k])
            tokens.append(s[start+k:])

        for token in tokens:
            if len(token) == 0:
                return False
            if len(token) > 1 and token[0] == '0':
                return False
            if int(token) > 255:
                return False
        return True

    def make_address(path):
        tokens = []
        tokens.append(s[:path[0]])
        tokens.append(s[path[0]:path[0]+path[1]])
        tokens.append(s[path[0]+path[1]:path[0]+path[1]+path[2]])
        tokens.append(s[path[0]+path[1]+path[2]:])
        return '.'.join(tokens)
    
    dfs([])
    return result

이 글은 제로베이스 데이터 취업 스쿨의 강의 자료 일부를 발췌하여 작성되었습니다