99클럽(2기) - 코테스터디 11일차 TIL # Dynamic Programming

LeetCode - 118. Pascal's Triangle

Given an integer numRows, return the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

 

---

1. 나의 첫 번째 풀이

 동적 계획법을 풀기 위해 반복적으로 등장하는 동일한 패턴을 찾으려고 했다. 현재 행의 현재 열에 들어갈 데이터는 이전 행의 '현재 열 - 1인 인덱스'를 가지는 데이터의 값과 이전 행의 '현재 열과 동일한 인덱스'를 가지는 데이터의 값을 합친 값이라는 패턴을 발견했다. 즉, 현재 위치의 값은 바로 윗 줄의 양쪽 대각선 방향으로 인접한 두 값의 합과 동일하다.  

 

1) 모든 요소의 값이 1인 2차원 배열 만들기

 먼저 최종적으로 반환해야하는 이차원 리스트와 동일한 행렬을 구성하고 모든 값을 1로 초기화했다. 각 행의 요소 개수는 1부터 numRows까지 증가한다. 모든 값을 1로 초기화한 이유는 모든 행의 첫 번째 요소와 마지막 요소는 1이고, 이 값들을 기반으로 패턴을 적용해 첫 번째 요소와 마지막 요소를 제외한 요소들의 값을 갱신하면 된다고 생각했기 때문이다. 

 

2) 2차원 배열을 순환하며 각 행의 맨 앞, 뒤 요소를 제외하고 패턴 적용

 이전 행의 데이터를 기반으로 현재 행의 데이터를 갱신할 열의 조건으로 첫 번째와 마지막 열, 첫 번째 행과 두 번째 행을 제외했다. 그 후 현재 행의 현재 열에 들어갈 데이터에 이전 행의 '현재 열 - 1인 인덱스'를 가지는 데이터의 값과 이전 행의 '현재 열과 동일한 인덱스'를 가지는 데이터의 값을 합친 값을 할당했다. 

from typing import List
class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        answer = [[1]*i for i in range(1, numRows + 1)]
        for nums_idx, nums in enumerate(answer):
            for num_idx, num in enumerate(nums):
                if num_idx > 0 and num_idx < len(nums) - 1 and nums_idx > 1:
                    answer[nums_idx][num_idx] = answer[nums_idx - 1][num_idx - 1] + answer[nums_idx - 1][num_idx]
        
        return answer

 

 

2. 나의 두 번째 풀이

 조건을 지정하는 부분이 조악하다.. 조건이 없으면 패턴을 모든 행에 적용할 수 없다는 점을 개선시키고자 했다. 

 

1) 2차원 배열을 먼저 만드는 대신 빈 1차원 배열만 생성

 2차원 배열을 먼저 만들어버리면 모든 인덱스를 알고있어야 하기 때문에 추상화에서 멀어진다. 따라서 1차원 배열만 만들어주고 2차원 배열은 매번 생성해주는 방식으로 변경했다. 

 

2) 1차원 배열을 기반으로 패턴을 적용한 행을 추가

 각 행을 생성할 때는 현재 행의 모든 요소를 1로 초기화했으며, 현재 행의 맨 앞, 뒤 요소를 제외한 범위에 해당하는 열의 데이터에 첫 번째 풀이와 동일한 방식으로 값을 할당해줬다. 이렇게 행을 생성할 때마다 최초에 만든 1차원 리스트에 추가함으로써 2차원 리스트를 만들었다. 

from typing import List
class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        answer = []
        for row_num in range(numRows):
            row = [1 for _ in range(row_num + 1)]  # 현재 행의 모든 요소를 1로 초기화
            
            # 현재 행의 맨 앞, 뒤 요소를 제외한 값 계산
            for j in range(1, len(row) - 1):
                row[j] = answer[row_num - 1][j - 1] + answer[row_num - 1][j] # 이전 행의 j-1번째 요소와 j번째 요소를 더함
            
            answer.append(row)
        
        return answer

 

 

3. 느낀점

 첫 번째 풀이는 조건을 지정하는 부분과 2차원 배열을 먼저 만드는 방식 때문에 코드가 너무 복잡해졌다. 이를 개선하기 위해 두 번째 풀이에서는 1차원 배열을 기반으로 각 행을 생성하고, 필요한 값을 계산하여 2차원 배열을 만들어나가는 방식으로 변경했다. 결과적으로 조금 더 조건을 간결하게 만들고, 가독성을 높일 수 있었다.

 

 동적 계획법은 반복되는 패턴을 추상화해서 효율적인 해결책을 도출하는 것이 중요한 만큼 어떻게 하면 재사용하기 편한 코드를 간단하게 만들 수 있을지 고민하는 과정이 많이 필요한 것 같다. 효율적이고 재사용 가능한 코드를 작성하기 위해서는 문제를 다양한 시각에서 바라보고, 개선점을 찾아내는 과정이 필요하다. 앞으로도 문제 해결에 있어서 코드의 간결함과 가독성을 높이는 방향으로 접근하려고 노력해야겠다!