[반복문] LeetCode 118번 문제 학습

문제를 푼 과정

1. 파스칼의 삼각형을 만들기 위해 2D 배열을 초기화했음.
2. 각 행의 크기를 행 번호에 맞게 설정하고 모두 1로 채웠음.
3. 아직 숫자 계산 로직은 없어서 완성되지 않았음.

func generateArray(numRows int) *[][]int {
	row := make([][]int, numRows)

	for i := 1; i <= numRows; i++ {
		row[i-1] = make([]int, i)
	}

	for i := 0; i < len(row); i++ {
		for j := 0; j < len(row[i]); j++ {
			row[i][j] = 1
		}
	}

	return &row
}

 

문제에 대한 설명

1. 이 문제는 파스칼의 삼각형을 주어진 행 수만큼 생성하는 문제임.
2. 각 행의 숫자는 이전 행의 인접한 값의 합으로 계산되며, 양 끝은 1임.
3. 결과는 2D 배열로 반환해야 함.

---

문제를 풀려면 어떤 알고리즘을 써야 하는지

1. 반복문을 사용해서 각 행을 순차적으로 생성하면 됨.
2. 이전 행의 값을 기반으로 다음 행을 계산하는 방식이 간단함.
3. 동적 프로그래밍처럼 이전 결과를 재활용하면 효율적임.

package main

func generate(numRows int) [][]int {
	row := make([][]int, numRows)

	for i := 1; i <= numRows; i++ {
		row[i-1] = make([]int, i)
	}

	for i := 0; i < len(row); i++ {
		for j := 0; j < len(row[i]); j++ {
			if j == 0 || j == len(row[i])-1 {
				row[i][j] = 1
			} else {
				row[i][j] = row[i-1][j-1] + row[i-1][j]
			}
		}
	}

	return row
}

func main() {
}

수정 방향

• 첫 행은 [1]로 고정.
• 두 번째 행부터 이전 행(row[i-1])을 보고 현재 행(row[i])을 계산.
• row[i][j] = row[i-1][j-1] + row[i-1][j] (단, 양 끝은 1).