99클럽 TIL (240830)

> [Middler] Unique Paths

https://leetcode.com/problems/unique-paths/

 

문제 풀이 과정

• DP(동적 계획법)
• 목표 : 로봇이 피니쉬 지점에 도달하는 모든 경로의 수 (로봇의 움직임은 아래,오른쪽만 가능)

접근 방법

• dp[i][j] 는 (i,j) 좌표에 도달할 수 있는 경로의 수. 로봇은 아래와 오른쪽으로만 이동할 수 있으므로 i,j 지점은 (i-1,j) 혹은 (i,j-1)지점으로 부터만 도달할 수 있다. 그래서 아래와 같은 식이 나온다.
• dp[i][j] = dp[i-1][j] + dp[i][j-1] 

 

문제 풀이

python

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # 목표 : 로봇이 피니쉬 지점으로 갈 수 있는 모든 경로의 수

        # dp를 이중리스트로 만든다.
        dp = [[1] * n for i in range(m)]
        
        # dp[i][j]에 대해 경로의 수를 채운다. dp[i][j] : d[i-1][j] + d[i][j-1]
        for i in range(m) :
            for j in range(n) :
                if i == 0 or j == 0 : continue
                dp[i][j] = dp[i-1][j] + dp[i][j-1]

	# dp[m-1][n-1]의 경로의 수를 리턴한다.
        return dp[m-1][n-1]

 

회고 및 느낀점

DP 문제유형이라고 알고 푸니까 DP로 풀었지 아니면 DP로 풀었을까? 흐음.... 아니라면 DFS로 풀었을 것 같다.

 

---

> [Beginner] min cost climbing stairs

https://leetcode.com/problems/min-cost-climbing-stairs/description/

 

문제 풀이 과정

• DP(동적 계획법)
• 목표 : 최소한의 비용으로 꼭대기 층에 오를 수 있는 비용 리턴

접근 방법

• dp[i] 는 i-1번째 층에서 올 수 있고, i-2번째 층에서 올 수 있다. (= 계단을 1칸 혹은 2칸 이동할 수 있다.) 그래서 아래의 점화식을 도출할 수 있다.
• dp[i] = min(dp[i-1]+dp[i], dp[i-2]+dp[i])
• 그리고 최소 비용 리턴 시, top(=cost의 길이) 에 도달하는 방법은 top-1, top-2 두가지이다. 그래서 두가지 중 최소값을 리턴했다.

 

문제 풀이

python

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        # 목표 : 주어지는 cost 배열을 이용해서 꼭대기 층에 오를 수 있는 최소 비용 리턴

        # [조건]
        # 1. 계단을 1칸 혹은 2칸 이동할 수 있다.
        # 2. 1층(i=0) 혹은 2층(i=1)에서 시작할 수 있다.

        # dp[i] 는 i번째 층에서 꼭대기 층에 오를 수 있는 최소 비용
        
        top = len(cost)
        dp = [0] * top
        dp[0] = cost[0]
        dp[1] = cost[1]

        for i in range(2, top) :
            dp[i] = min(dp[i-2]+cost[i], dp[i-1]+cost[i])
        
        return min(dp[top-1], dp[top-2])

 

오늘의 회고 및 느낀점

DP에 익숙해져 가고 있는 것 같다. easy 문제라서 그런가 싶지만..? 기분이 좋다.

 

---

 

> [Challenger] 등굣길

https://school.programmers.co.kr/learn/courses/30/lessons/42898#

 

🔥다시보기🔥

 

문제 풀이 과정

• DP(동적 계획법)
• 목표 : 집에서 학교까지 갈 수 있는 최단경로의 개수 % 1000000007

접근 방법

• dp[i][j] 은 물웅덩이 이외에 다른 지역을 거쳐 오는 경로의 수입니다. 위의 미들러 문제와 유사하지만 조건을 잘 작성해 웅덩이를 거치지 않도록 하면 됩니다.
• dp[i][j] = dp[i-1][j] + dp[i][j-1] (단, dp[i][j] 는 웅덩이가 아니어야 합니다.)

 

문제 풀이

python

def solution(m, n, puddles):
    # 목표 : 집에서 학교까지 가는 최단경로 개수(단, 물웅덩이가 있으면 갈 수 없음)
    dp = [ [0]*(m+1) for i in range(n+1) ]
    
    # 물웅덩이 표시
    for i,j in puddles :
        dp[j][i] = -1
        
    for i in range(1,n+1) :
        for j in range(1,m+1) :
            if i == 1 and j ==1 : 
                dp[i][j] = 1
            elif dp[i][j] == -1 :
                dp[i][j] = 0
            else :
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
                
    return dp[n][m] % 1000000007

 

오늘의 회고 및 느낀점

조건문을 잘 설정하자! 엣지케이스에 대해서도 생각을 해보고 로직을 짜자구..!