[99클럽 코테 스터디] 21일차 TIL DP

 

 

오늘의 문제는 LeetCode

 

118. Pascal's Triangle

 

 

문제

 

 

 

문제 설명 

정수 numRows가 주어지면 numRows 크기의 파스칼 삼각형을 반환하면 되는 문제입니다. 

여기서 파스칼 삼각형이란 n번째 수와 n+1번째 수를 더해 아래 행의 n+1번째 수가 만들어지는 것을 의미합니다. 

예를 들어 numRows가 5일 때의 반환값은 아래와 같습니다. 

[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

 

 

 

문제 풀이 시간 

권장 풀이 시간은 30분이었고, 저는 22분이 걸렸습니다.

 

 

 

문제 접근 방식

문제에서 이차원 리스트가 주어졌기 때문에 이를 활용해 풀었습니다. 전체 삼각형을 외부 리스트로, 각 행을 내부 리스트로 생각했습니다. 

외부 리스트는 파스칼 삼각형 전체를 저장할 이차원 리스트입니다. 각 행이 완성될 때마다 이 리스트에 추가합니다. 

내부 리스트는 각 행을 표현하는 리스트로, 현재 행의 값을 저장합니다. 이 때 주의할 점은 각 행의 첫 번째와 마지막 요소는 1이라는 것입니다. 따라서 행의 첫 번째와 마지막 요소를 제외한 중간 요소만 수식을 통한 계산을 해주었습니다. 

 

 

 

문제 풀이

import java.util.ArrayList; 
import java.util.List; 

class Solution {
    public List<List<Integer>> generate(int numRows) {
        
        List<List<Integer>> result = new ArrayList<>();  

        for(int i = 0; i < numRows; i++) {
            
            List<Integer> row = new ArrayList<>();
            
            for(int j = 0; j <= i; j++) {
                
                if(j == 0 || j == i) {
                    row.add(1);
                } else { 
                    row.add(result.get(i - 1).get(j - 1) + result.get(i - 1).get(j));
                }

            }                
            result.add(row); 
        
        }
        return result;
    }
}

 

 

동적계획법(DP) 알아보기 

파스칼 삼각형은 동적계획법의 응용 문제입니다. 동적 계획법이란 복잡한 문제를 작은 문제로 쪼개서 결과를 저장하고 재활용하는 기법입니다. 일반적인 재귀적 호출이 하향식 접근 방식을 사용하는 반면 동적 계획법은 상향식 접근 방식을 사용합니다. 

이 문제에선 각 요소를 계산하기 위해 이전 행의 결과를 재활용하는 식으로 동적계획법을 응용하고 있습니다. 

 

 

 

이차원 리스트 알아보기 

이차원 리스트는 리스트 안에 리스트를 포함하는 구조로 행렬이나 테이블 같은 데이터를 표현할 때 주로 사용합니다. 이번 문제에서는 각 행을 리스트로, 전체 삼각형을 리스트의 리스트로 표현해 파스칼 삼각형을 생성할 수 있었습니다. 

 

 

 

이항정리 공식 활용 

파스칼 삼각형의 각 요소는 이항 계수 공식을 이용해 구할 수 있습니다. 이 공식은 이항정리의 조합 공식인 C(n, k) = n! / (k! * (n-k)!)로 계산됩니다. 처음에는 이 공식을 사용하여 팩토리얼 메서드로 구현했지만, 이 방식은 정수의 최대 범위를 초과하는 문제가 발생하여 코드를 수정하게 되었습니다.

 

 

1차 시도 및 오류 원인 확인 

1차 시도에서는 이항정리의 공식을 사용해 파스칼 삼각형을 생성하려고 했습니다. 아래 코드를 보면, 각 요소를 계산하기 위해 팩토리얼 함수를 활용했습니다.

import java.util.ArrayList; 
import java.util.List; 

class Solution {
    public List<List<Integer>> generate(int numRows) {
        
        List<List<Integer>> result = new ArrayList<>();  

        for(int i = 0; i < numRows; i++) {
            
            List<Integer> row = new ArrayList<>();
            
            for(int j = 0; j <= i; j++) {
                
                row.add(factorial(i) / (factorial(j) * factorial(i - j)));

            }                

            result.add(row); 
        
        }
        
        return result;
    }
 
    private static int factorial (int num) {
        
        int facResult = 1;
        
        for(int i = 1; i <= num; i++) {
            facResult *= i;
        }
        return facResult; 
    }
}

 

하지만 numRows가 14 이상일 경우, 팩토리얼 계산 결과가 급격히 커져 int 자료형의 표현 범위를 넘어섰습니다. 이로 인해 오버플로우가 발생하여 잘못된 결과를 반환하게 되었습니다.

이 문제를 해결하기 위해, 팩토리얼을 사용하지 않고 이항 계수를 직접 계산하는 방식으로 코드를 수정했습니다. 이를 통해 오버플로우 문제를 피하고, 파스칼 삼각형을 올바르게 생성할 수 있었습니다.

 

 

 

 

이렇게 오늘 21일차 TIL을 작성해 보았습니다.