✨ 문제
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:
https://leetcode.com/problems/pascals-triangle/description/
✨ 개념
동적 프로그래밍 Dynamic Programming
- 복잡한 문제를 작은 문제로 분해하여 해결하는 알고리즘 기법.
- 동적 프로그래밍을 적용하기 위해서는 다음 2가지 조건이 필요하다.
최적 부분 구조 : 전체 문제의 최적해를 부분 문제의 최적해로부터 찾을 수 있어야함.
중복되는 부분 문제 : 부분 문제가 여러번 중복되어 반복계산 되어야함.
동적 프로그래밍의 두 가지 접근 방식
상향식 접근법 Bottom-up
- 작은 하위 문제부터 해결해 나가며 차례로 큰 문제를 해결하는 방식.
- 일반적으로 반복문을 사용하여 구현됨.
하향식 접근법 Top-down
- 큰 문제를 해결하기 위해 재귀적으로 하위 문제를 호출하는 방식
- 하위 문제의 결과를 저장하기 위해 메모이제이션을 사용함.
✨ 최종코드
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> triangle = new ArrayList<>();
if (numRows <= 0)
return triangle;
List<Integer> firstRow = new ArrayList<>();
firstRow.add(1);
triangle.add(firstRow);
for (int i = 1; i < numRows; i++) {
List<Integer> prevRow = triangle.get(i - 1);
List<Integer> row = new ArrayList<>();
// 첫번째 요소 추가
row.add(1);
for (int j = 1; j < i; j++)
row.add(prevRow.get(j - 1) + prevRow.get(j));
// 마지막 요소 추가
row.add(1);
triangle.add(row);
}
return triangle;
}
입력받은 numRows만큼을 높이로 하는 파스칼 삼각형을 구현하는 문제이다.
삼각형의 각 행을 저장할 정답 리스트 triangle을 선언하고 numRows가 0 이하일 경우 빈 리스트를 반환한다.
첫 행의 값을 저장할 리스트 firstRow를 만들고 첫번째 값은 항상 1이므로 1을 add한다. 그리고 triangle에도 firstRow를 추가해준다.
그 다음 for문으로 나머지 행들의 값을 채워주는데 prevRow에 현재 구현할 행의 한줄 위의 리스트를 불러온다. 그리고 현재 구현해야하는 행을 저장할 리스트 row도 선언한다.
모든 행의 첫번째 요소는 항상 1이므로 1을 add하고 마지막 요소를 제외한 나머지 부분의 값은 바로 위 행의 두 요소를 더한 값이므로 for문을 통해 윗행에서 인덱스가 j - 1인 값과 j인 값을 더해 row의 j를 구해준다.
for문이 끝나면 모든 행의 마지막 요소도 항상 1이므로 1을 add 해준다. 마지막으로 triangle에도 row를 추가해준다.
그리고 triangle을 리턴한다.
