[호붕싸 모각코 1주차] Leetcode 62. Unique Paths, 72. Edit Distance

작성자	김윤희
소 감	오랜만에 모각코를 진행하니 조금 소홀히 했던 코딩테스트 문제를 풀어볼 수 있었다. 항상 느끼지만 이 부분은 모각코의 최대 장점인 듯 하다. 모여서 하다보니 혼자하는 것보다 집중도 잘됐고, 오래돼서 가물가물했던 코딩 지식도 바로바로 친구들에게 물어보며 빠르게 떠올릴 수 있었다.
일 시	2025. 3. 10. (월) 18:00 ~ 21:00
장 소	미래관 429호 자율주행스튜디오
참가자 명단	신수민, 임혜진, 배세은, 김윤희 (총 4명)
사 진

 

62. Unique Paths

문제 설명 

- m x n 격자위에 로봇이 있음

- (0,0)에서 시작해서 (m-1, n-1)로 이동하려함

- 아래 또는 오른쪽으로만 이동할 수 있음

 

즉, 두 정수 m, n이 주어졌을 때, (m-1, n-1) 위치에 도달하는 고유한 경로의 개수를 return하는 문제이다. 

 

1. 조합을 이용하는 경우 

오른쪽으로 n-1, 아래로 m-1번 이동해야한다고 하면,

총 m + n - 2 번 이동 중, n-1번을 오른쪽으로 가는 경우를 선택하는 조합의 수를 이용

import math

def uniquePaths(m: int, n: int) -> int:
    return math.comb(m + n - 2, n - 1)​

 

2. dp를 이용하는 경우 

def uniquePaths(m: int, n: int) -> int:
    dp = [[1] * n for _ in range(m)]  # (i, j)위치까지 도달하는 고유한 경로 수를 저장
                                      # 첫 행과 열은 경로가 항상 1개 뿐

    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1] # 위쪽에서 내려오는 경우 + 왼쪽에서 오는 경우

    return dp[m-1][n-1]

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        path = [1] * (n)  # 1차원 배열 사용

        for i in range(1, m):
            for j in range(1, n):
                path[j] += path[j-1] # 현재 위치 = 왼쪽 + 위쪽

        return path[n-1]

 

dp를 이용하는 경우는 1차원, 2차원 둘 다 사용하여 해결할 수 있었다. 

1차원 배열을 사용하는 경우 메모리 공간을 절약할 수 있어 효율적이었지만 점화식을 떠올리는데 쉽지 않았다. 

 

dp 문제를 응용하기 위해 72번 edit distance 문제도 이어서 풀어보았다. 

72. Edit Distance

문제설명

두 문자열 (word1, word2) 사이의 변환 비용을 최소화 하는 문제

즉, word1을 word2로 변환하는데 필요한 최소 연산 횟수 구하기

- word1: horse -> word2: ros

- horse -> rorse -> rose -> ros

- 총 3 번

 

풀이

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)

        # 앞 i개 문자를 word2의 앞 j개 문자로 변환하는 최소 연산 수 저장
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        # base case -> 빈 문자열을 다른 문자열로 변환하는 경우
        for i in range(m + 1):
            dp[i][0] = i  # word2가 빈 문자열이면 i 번 삭제
        for j in range(n + 1):
            dp[0][j] = j  # word1이 빈 문자열이면 J 번 삭제

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if word1[i - 1] == word2[j - 1]: # 문자가 같으면 그대로 사용
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = min(          # 최소 비용을 선택
                        dp[i - 1][j] + 1,    # 삭제
                        dp[i][j - 1] + 1,    # 삽입
                        dp[i - 1][j - 1] + 1 # 교체
                    )

        return dp[m][n]