[99클럽 코테 스터디] 22일차 TIL - Pascal's Triangle II

오늘의 학습 키워드

</> 동적계획법

공부한 내용 본인의 언어로 정리하기

import java.util.*;
class Solution {
public List<Integer> getRow(int rowIndex) {
    List<Integer> row = new ArrayList<>();

    row.add(1);

    for(int i = 1; i <= rowIndex; i++){
        for(int j = i - 1; j > 0; j--){
            row.set(j, row.get(j-1) + row.get(j));
        }
        row.add(1);
    }
    return row;
    }
}

오늘의 회고

오늘은 어제랑 비슷한 종류의 문제가 나왔다. 차이점은 이중 리스트가 리스트로 변경 됬다는것, 그리고 마지막 행의 값만 구하면 된다는것

그래서 일단 List로 결과를 보여줄 객체를 만들고 시작했다.

List<Integer> row = new ArrayList<>();

그리고 시작과 마지막은 1로 고정되어있으므로 추가해 주었다.

row.add(1);

row.add(1);

중간값을 가져와야하는데 예시를 보면 rowIndex보다 +1번째 행을 구해야 하므로

for(int i = 1; i <= rowIndex; i++)

로 만들어 주었다.

그리고 이중 for문을 이용해 이전 행의 인접한 2개의 값을 더해주는데

for(int j = i - 1; j > 0; j--)

로 만들어 준 이유는
i-1을 하지 않으면 역순으로 진행하는 순서에서 인덱스 값이 초과해버리기 때문에 오류가 난다.
그래서 역순으로

row.get(j, row.set(j-1) + row.set(j));

로 인접한 두개의 값을 더해서 row의 j번째 값으로 가져다주었다.

이렇게 되면 오류가 나는데 그 이유는 시작이 1이었지만 마지막 row.add(1)때문에 최상위에도 1이 하나가 더 들어가 에러가 나는것이므로, i for문 안에 마지막 1을 추가하는 식으로 넣어주어야한다.
그래서 완성된 것이

for(int i = 1; i <= rowIndex; i++){
        for(int j = i - 1; j > 0; j--){
            row.set(j, row.get(j-1) + row.get(j));
        }
        row.add(1);
    }

이렇다.

AI 코드리뷰

현재 코드의 장점

1. 공간 효율성: 전체 삼각형을 저장하지 않고 요청된 행만 생성하므로 메모리 사용이 효율적입니다.
2. 간결성: 코드가 비교적 짧고 이해하기 쉽습니다.
3. In-place 연산: 새로운 리스트를 만들지 않고 기존 리스트를 업데이트하여 공간을 절약합니다.

현재 코드의 단점

1. 가독성: 중첩된 루프와 복잡한 인덱싱으로 인해 코드의 의도를 파악하기 어려울 수 있습니다.
2. 타입 안전성: 제네릭을 사용하지 않아 타입 안전성이 떨어집니다.
3. 입력 검증: 음수 입력에 대한 처리가 없어 예외가 발생할 수 있습니다.

시간 복잡도

• 이 알고리즘의 시간복잡도는 O(rowIndex^2)입니다.
• 외부 루프는 rowIndex번 실행되고, 내부 루프는 각 반복마다 최대 i번 실행됩니다.
• 1 + 2 + 3 + ... + rowIndex 번의 연산이 수행되므로,
  이는 (rowIndex * (rowIndex + 1)) / 2에 해당합니다.
• 따라서 전체 시간복잡도는 O(rowIndex^2)입니다.

개선 제안

1. 제네릭 사용: List를 사용하여 타입 안전성을 높입니다.
2. 입력 검증 추가: 음수 입력에 대한 처리를 추가합니다.
3. 변수명 개선: 'i', 'j' 대신 더 의미 있는 변수명을 사용하여 가독성을 높입니다.
4. 주석 추가: 알고리즘의 작동 방식을 설명하는 주석을 추가합니다.

개선된 코드 제안

오늘은 AI의 코드 제안 대신 클럽장님이 말한 이항 계수의 방법을 이용한 코드를 작성한다.

import java.util.*;  
class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> row = new ArrayList<>();
        long coef = 1;
        for (int i = 0; i <= rowIndex; i++){
            row.add((int) coef);
            coef = coef * (rowIndex - i) / (i + 1);
        }
        return row;
    }
}

개선된 버전의 장점:

1. 공간 효율성: 전체 삼각형을 저장하지 않고 요청된 행만 생성하여 메모리 사용을 최소화합니다.
2. 수학적 최적화: 이항 계수 공식을 사용하여 각 원소를 직접 계산함으로써 연산 횟수를 줄입니다.
3. 간결성: 코드가 간결하고 이해하기 쉽습니다.
4. long 타입 사용: 중간 계산에서 long 타입을 사용하여 큰 수의 오버플로우를 방지합니다.

개선된 버전의 단점:

1. 정밀도 손실: int로의 캐스팅으로 인해 매우 큰 rowIndex에 대해 정밀도 손실이 발생할 수 있습니다.
2. 예외 처리 부재: 음수 입력에 대한 예외 처리가 없습니다.
3. 가독성: 수학적 로직이 명시적으로 설명되어 있지 않아 코드의 의도를 파악하기 어려울 수 있습니다.

시간 복잡도:

• O(n), 여기서 n은 rowIndex입니다.
• 루프가 rowIndex + 1번 실행되며, 각 반복에서의 연산은 상수 시간이 소요됩니다.

이 구현은 효율적이지만, 코드의 의도를 명확히 하는 주석을 추가하고 입력 유효성 검사를 포함하면 더 개선될 수 있습니다. 또한, 매우 큰 rowIndex에 대해서는 BigInteger를 사용하여 정밀도 문제를 해결할 수 있습니다.

---

내일 공부할 것 :

1. 조합론 (Combinatorics)

   • 이항 계수 (Binomial Coefficients)의 성질과 응용
   • 파스칼의 항등식 (Pascal's Identity)
     

2. 수학적 최적화

   • 모듈러 연산 (Modular Arithmetic)을 이용한 큰 수 처리

3. 알고리즘 설계 패턴

   • 분할 정복 (Divide and Conquer) 접근법

문제

https://leetcode.com/problems/pascals-triangle-ii/