오늘의 학습 키워드
</> 동적계획법
공부한 내용 본인의 언어로 정리하기
import java.util.*;
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> triangle = new ArrayList<>();
//첫줄은 항상 1
triangle.add(Arrays.asList(1));
//아래 숫자들 계산
for(int i = 1; i < numRows; i++){
//현재 행
List<Integer> row = new ArrayList<>();
//이전 행
List<Integer> prevRow = triangle.get(i - 1);
//각 행의 시작은 항상 1
row.add(1);
//중간 숫자 계산 (이전 행의 )
for(int j = 1; j < i; j++){
row.add(prevRow.get(j-1)+prevRow.get(j));
}
//각 행의 마지막은 항상 1
row.add(1);
triangle.add(row);
}
return triangle;
}
}오늘의 회고
오늘 주제가 동적 계획법이어서 동적 계획법에 대한 공부부터 시작하였다
동적 계획법 <- 해당 링크에 정리하였음
정의와 사용법에 대해서 공부는 하였지만...메모이제이션이나 Top-Down, Bottom-Up에 대해 실제로 적용해서 사용을 해야할지 감이 안잡혀서 각 행을 만드는 법부터 생각을 해보았다.
- 주어진 행의 수 만큼의 삼각형을 만든다.
- 각 줄의 첫번째와 마지막은 1이다.
- 중간에 들어갈 숫자들은 이전행의 해당 인덱스와 인접한 두 숫자들이다.
- 맨 첫줄은 항상 1, 한개이다.
그렇다면 첫번째 꼭대기를 1로 처음부터 제공해주고 두 번째 줄부터 numRows 만큼 만들면 되겠다고 생각했다.
(사실 여기까지도 엄청 고민하고 생각하고... Output은 보지도 않고 삼각형만 뚫어져라 보면서 재귀함수 생각하고 값을 더해서 아래로 내릴 생각만 하다가 깨달았다... 나는 아직 그렇게 생각까진 안든다...)
그래서 일단 triangle 이차원 리스트를 초기화 한 후에 첫번째 배열에 [1]을 추가해 주었다.
List<List<Integer>> triangle = new ArrayList<>();
triangle.add(Arrays.asList(1));일단 현재 행을 계산할 리스트가 필요했고, 이전 행에서 가져와야 하므로 이전행도 객체가 하나 필요했다.
그리고 아래로 들어갈 행들을 만들어 주었다. 그리고 첫번째와 마지막 배열에 1을 넣어주었다.
for(int i = 1; i < numRows; i++){
List<Integer> row = new ArrayList<>();
List<Integer> prevRow = new ArrayList<>();
row.add(1)
// + 중간 값
row.add(1)
}중간 값을 어떻게 하면 좋을지 굉장히 고민을 많이했다.
그리고 두번째부터 만들어야하므로 for문의 반복을 1부터 시작하고 n번째 줄을 n개의 배열의 길이를 가지고 있으므로 i만큼만 증가시켜 나갔다. 그리고 현재 행에다 이전행의 인접한 2개를 더해주었다.
for(int j = 1; j < i; i++){
row.add((prevRow(j)+prevRow(j+1));
}하지만 여기서 오류가 있었는데 최대 인덱스의 범위를 벗어나버리면서 시작이 인덱스 1번부터 시작되어 잘못된 값이 나오게 되었다. 그래서 순서를 개선하였다.
for(int j = 1; j < i; j++){
row.add(prevRow.get(j-1)+prevRow.get(j));
}완성된 행을 triangle에다 추가를 해주고 마지막 결과를 반환하였다.
triangle.add(row);
return triangle;AI 코드리뷰
현재 코드의 장점
-
기능 구현: 이 코드는 파스칼의 삼각형을 생성하는 요구사항을 잘 구현하고 있습니다. 각 행의 숫자를 올바르게 계산하고, 각 행을 올바르게 추가합니다.
-
가독성: 코드가 간결하고 이해하기 쉽습니다. 각 부분이 명확하게 나누어져 있어 읽기 편합니다.
-
동적 행 생성: 각 행을 생성하기 위해 이전 행을 참조하여 필요한 값을 계산하고, 이를 리스트에 추가하는 방식이 효율적입니다.
현재 코드의 단점
-
불변 리스트: Arrays.asList로 생성된 리스트는 크기를 변경할 수 없기 때문에, 리스트의 크기를 동적으로 조정할 수 없습니다. 그러나 이 코드에서는 행을 새로 생성하고 있으므로 문제가 되지 않습니다.
-
메모리 사용: List의 각 행을 ArrayList로 생성하고 추가하는 과정에서 메모리 사용이 증가할 수 있습니다.
시간 복잡도
- 시간 복잡도: 𝑂(𝑛^2), 여기서 𝑛은 numRows입니다.
- 각 행을 생성하는 데 필요한 시간은 그 행의 요소 수만큼입니다.
- 전체적으로는 1+2+3+…+(𝑛−1)개의 연산이 필요하며, 이는 𝑂(𝑛2)에 해당합니다.
- 공간 복잡도: 𝑂(𝑛2)
- 생성된 삼각형의 모든 요소를 저장해야 하므로, 𝑛개의 행이 각 𝑖번째 행에 𝑖+1개의 요소를 포함하므로 총 𝑂(𝑛^2)의 공간이 필요합니다.
개선된 코드 제안
import java.util.*;
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> triangle = new ArrayList<>();
if (numRows <= 0) {
return triangle;
}
triangle.add(new ArrayList<>(Collections.singletonList(1)));
// 각 줄 계산
for (int i = 1; i < numRows; i++) {
List<Integer> row = new ArrayList<>();
List<Integer> prevRow = triangle.get(triangle.size() - 1);
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가 0 이하인 경우를 처리하여 불필요한 작업을 방지합니다.
- Collections.singletonList 사용: 첫 번째 행을 초기화할 때 Collections.singletonList(1)을 사용하여 불필요한 Arrays.asList 호출을 줄입니다.
- triangle.size() - 1 사용: triangle.get(i - 1) 대신 triangle.get(triangle.size() - 1)을 사용하여 가독성을 향상시킵니다.
개선된 버전의 장점:
- 안정성: 빈 입력을 처리하여 코드의 안정성을 높입니다.
- 가독성 향상: 더 간결한 코드로 가독성을 개선합니다.
- 효율성: 추가적인 데이터 구조를 사용하지 않고 필요한 연산만 수행합니다.
개선된 버전의 단점:
- 불필요한 개선: 성능 차이가 크지 않으며, 원래 코드도 이미 효율적입니다.
시간 복잡도:
시간 복잡도: 여전히 𝑂(𝑛2)
공간 복잡도: 여전히 𝑂(𝑛2)
내일 공부할 것 :
- 알고리즘과 데이터 구조
- 동적 계획법: 개념 복습, 예제 문제 풀이
- 그래프 이론: DFS, BFS, 최단 경로 알고리즘
문제
