코딩: 말하기 듣기 쓰기-9

다이나믹 프로그래밍

살다살다 개발자가 되기로 마음먹고 알고리즘을 배우기 시작해서 여기까지 이르렀다. 마짐가 단원인 다이나믹 프로그래밍. 이건 책에서나 그리고 블로그에서도 많은 정의가 나오기에 정확한 정의보다는 내가 이해한 것을 바탕으로 쉽게 말하겠다. 그냥, 최단 거리를 계산하는데, 중복적으로 그 전에 한번 건든 것은 건들지 않기위해서 머리를 쓴것이다 (메모이제이션: 한번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법 by 동빈). 이것은 주로 점화식을 기반으로 푸는 것 같다. 왜냐하면, 보통 문제들을 보니까, 스테이지별로 나누기가 가능하다. 스테이지별로 한단계, 한단계 진행되는데, 단계별로 관계를 식으로 잘 정리해서 점화식을 디테일하게 코딩하는 것이 관건이다. 여기서 두가지 방식이 있는데, Top-Down 과 Bottom-Up 이 있는데, 전자는 재귀방식으로 푸는 것이고, 후자는 반복문 방법이다. DP 테이블을 자주 사용하는데, 이것은 그냥 쉽게말해서 문제를 보고 리스트나 행렬이 만들어지는데, 그것을 0이나 무한숫자로 채워서 만든 테이블이다. 이것안에 있는 수를 주로 바꾸거나 한다. 이런식으로한다.

정수삼각형

이 문제는...일단 쉬워보인다. DP말고 그냥 for문 두개로 돌려서 풀면 끝나긴한다. 하지만, DP를 연습핳기위해서, 최대한 DP적으로 생각을 해보았다. 하지만, 실패. for문 두개를 이용해서 푸는 것은 동일했으나, DP적으로 생각하는 것은 아직 불가능했다.

정수삼각형 프로그래머스 문제.
https://programmers.co.kr/learn/courses/30/lessons/43105

import sys

input = sys.stdin.readline
n = int(input())
dp = []
'''
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
'''

for _ in range(n):
    dp.append(list(map(int, input().split())))

for i in range(1, n):
    for j in range(i + 1):
        if j == 0:
            up_left = 0
        else:
            up_left = dp[i - 1][j - 1]
        if j == i:
            up = 0
        else:
            up = dp[i - 1][j]
        dp[i][j] = dp[i][j] + max(up_left, up)
print(max(dp[n - 1]))

by 데이터분석가 후이

이분의 문제해설이 이해하기 쉬워서 가져왔다. 위에 코드에 대한 설명이 너무 좋다. 아무튼 두가지 경우로 나누어야한다.

파란색: 바깥으로 왼쪽끝/오른쪽끝 둘중 하나 라인타서 더해주는 경우
분홍색: 중심에서 왼쪽/오른쪽 숫자중 큰것 더해주는 경우

위에 코드를 바탕으로 이중 for문을 돌릴경우 이렇게 된다:
[[7], [10, 15], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]
[[7], [10, 15], [18, 16, 15], [2, 7, 4, 4], [4, 5, 2, 6, 5]]
[[7], [10, 15], [18, 16, 15], [20, 25, 20, 19], [4, 5, 2, 6, 5]]
[[7], [10, 15], [18, 16, 15], [20, 25, 20, 19], [24, 30, 27, 26, 24]]

여기서 잘보면, 누적된 값을 확인할 수 있는데, 이중에서 제일 큰 누적값을 선택하면 된다. max()를 이용해서 확인 가능하다. 여기서!! 30!!! 그래서 30이 답이다.

DP...점화식을 만드는게 관건. 그말인 즉슨, 어떻게 답으로 출력되는가를 입력값부터의 흐름을 파악하는게 제일 중요한게 아닌가...이걸 느끼게 된 계기가 되었다.

입국심사

https://programmers.co.kr/learn/courses/30/lessons/43238

이 문제는 우리팀에서 이진탐색을 공부할때, 찾아서 풀었던 문제이기도하다. 문제로 남아서, 다시 보았던 문제를 꼴도보기싫고 머리가 다시 아프기싫어서 넘기려고했으나. 진정한 개발자가 되기위해서는 당연히 풀어야지. 인생 쉽지않아. 아무튼 다시 풀어보았다. 신기한게, 분명 보았던건데, 까먹었다. 이래서 복습 많이하는게 중요한갑다. 아무튼 이진탐색으로 풀어야하는 문제였다. 이진탐색은 이분탐색이라고도하고 어디서는 이진검색이라고도하고 뭔가 말이 많다. 아무튼 중요한 것은 이것을 어떻게 접근할 것인지에 대한 것인데... 무조건 큰수와 작은수를 알아내어야 한다. 그래야 범위가 어느정도이고, 이 범위에서 최댓값과 최솟값을 알아야 중간값을 알아내서 이진검색을 실시할수있다. 이런문제는 제일먼저 보자마자 최댓값을 생각하는 연습을 해야한다는 것을 알았다. 이것은 팀원들과 이야기를 해보았는데, 내가 범위를 설정한것은 단순히 제일 심사가 오래 걸릴경우, 즉 최댓값과 그냥 문제에 있는 예시문제의 최솟값을 맞추어서 했다. 하지만 우리 팀원중 한명은 코딩을 하기전에 최대한 범위를 답 근처에 있도록 모든 수를 고려해서 설정을 했다. 그래서 왜 그렇게까지 했냐고하니까 그래야 시간복잡도를 줄일수있다는 뭐 어쩌구저쩌구를 하긴했는데. 뭐 이러나저러나 뭐 맞기만하면되긴하지만, 나쁘지 않은 것 같다. 중간값은 중간값동안 심사한 사람의 수. 그리고 만약에 심사한 사람의 수가 심사받아야할 사람의 수보다 같거나 많을 경우에 주어진 시간을 줄이고 (right = mid - 1), 심사받아야 하는 사람의 수보다 작을 경우에는 시간이 부족한것이니까 주어진 시간을 늘려준다 (left = mid + 1) 이런식으로.

def solution(n, times):
    answer = 0
    # right는 가장 비효율적으로 심사했을 때 걸리는 시간
    # 가장 긴 심사시간이 소요되는 심사관에게 n 명 모두 심사받는 경우이다.
    left = min(times)
    right = max(times) * n
    while left <= right:
        mid = (left + right) // 2
        checked = 0
        for time in times:
            # people 은 모든 심사관들이 mid분 동안 심사한 사람의 수
            checked += mid // time
            # 모든 심사관을 거치지 않아도 mid분 동안 n명 이상의 심사를 할 수 있다면 반복문을 나간다.
            if checked >= n:
                break

        # 심사한 사람의 수가 심사 받아야할 사람의 수(n)보다 많거나 같은 경우
        if checked >= n:
            answer = mid
            right = mid - 1
        # 심사한 사람의 수가 심사 받아야할 사람의 수(n)보다 적은 경우
        elif checked < n:
            left = mid + 1

    return answer

left 와 right를 좁혀가면서 답을 점점 숨죽여서 찾아가는것. 참 재밌는 것같다. 점점 숨통을 조여서 확 답을 낚아채는것.