7/19 Coding Test

✅ 문제풀이 - DP

🎈 사칙연산 (level 4)

사칙연산에 있어 더하기는 결합법칙이 성립하지만, 빼기의 경우 결합법칙이 성립하지 않는다.
괄호에 의존하는 뺄셈 연산에 있어 연산 결과가 괄호 위치에 따라 상당히 다양하게 나올텐데 연산 결과 중 최대값을 리턴하는 문제

• 입력값 : arr 리스트 (문자열 형태의 숫자와, + 또는 -가 주어지고 연산자와 숫자가 번갈아가며 입력)
• 출력값 : 최대값 리턴

def solution(arr):
    nums = [int(x) for x in arr[::2]]    
    operators = [x for x in arr[1::2]]
    
    n = len(nums)
    dp_max = [[0]*n for _ in range(n)]
    dp_min = [[0]*n for _ in range(n)]
	return answer

< 풀이 과정 >
뺄셈을 포함한 사칙연산에서 최댓값을 만들기 위해 가장 중요한 것은 최댓값 - 최솟값을 처리해주기 위해 DP를 최댓값을 저장하는 리스트 하나, 최솟값을 저장하는 리스트 하나 총 2개로 구분하여 저장해줄 필요가 있다.
-> ### ✨ 다시 풀어봐야 할 문제! (상당히 까다로움)

🎈 등굣길 (level 3)

집에서 학교까지 가는 길이 mxn 격자 크기로 주어지고 집은 가장 왼쪽 위, 학교는 가장 오른쪽 아래에 있다고 하자.
오른쪽과 아래칸으로만 이동하며 폭우로 물에 잠긴 지역을 제외하고 집에서 학교까지 갈수있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 리턴하는 문제.

• 입력값으로 m, n, puddles(잠긴 지역의 위치)
• 출력값 : 집에서 학교까지 최단 경로 개수 % 1,000,000,007

• 물에 잠긴 지역의 수 즉 puddles 내 원소 수는 [0,10] 이고 m, n의 범위는 [1, 100] 이다.

def solution(m, n, puddles):
    dp = [[0] * (m+1) for _ in range(n+1)]
    dp[1][1] = 1
    for i in range(1, n+1):
        for j in range(1, m+1):
            if i == 1 and j == 1:
                continue
            if [j, i] in puddles:
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[n][m] % 1000000007

< 풀이 과정 >

전형적인 DP 문제.
dp는 빈 리스트를 만들어준 후 값을 채워나가는 것이 핵심인데, 이 문제처럼 dp로 만들어야 되는 구조가 주어진 문제는 사실상 쉬운 편이다.

방법은 다음과 같다.

• 현위치 (1,1)을 반영해주기 위해 dp로 (m+1) x (n+1) 크기의 리스트를 생성해주고 현 위치를 1로 저장한다. (현위치 -> 현위치 이동 횟수 1이기에)
• 이후 2중 for문으로 오른쪽, 아래로 내려가면서 값을 채워준다.
• 이때, 만일 j,i 위치가 물에 잠긴 곳이라면 해당 위치까지의 경로는 0으로 치고 아닌 경우 해당 위치의 값을 왼쪽과 위쪽의 합으로 나타낸다.
• 최종적으로 문제에서 해당 값으로 나누라는 지시가 있었기에 이를 반영하여 리턴.