[알고리즘 문제 풀이] 파스칼의 삼각형

 

📍  문제 요약

크기가 N인 파스칼의 삼각형을 만들어야 한다.
파스칼의 삼각형이란 아래와 같은 규칙을 따른다.

1. 첫 번째 줄은 항상 숫자 1이다.
2. 두 번째 줄부터 각 숫자들은 자신의 왼쪽과 오른쪽 위의 숫자의 합으로 구성된다.

N이 4일 경우,

N을 입력 받아 크기 N인 파스칼의 삼각형을 출력하는 프로그램을 작성하시오.

 

 

🧩 로직 설계 1 >> 해답

1) 삼각형의 첫 번째 줄은 항상 1이다.

2) 두 번째 줄부터는 각 숫자가 윗줄의 두 숫자를 더한 값이다.

3) 프로그램은 한 줄씩 숫자를 채운 후, 다음 줄로 넘어가면서 같은 과정을 반복한다.

4) 가장 중요한 점은 각 줄의 첫 번째 숫자와 마지막 숫자는 항상 1이고, 나머지 숫자는 이전 줄에서 두 숫자를 더한 값이다.

 

---

🎯 단계별 소스 코드 및 구현

함수 정의

def pascal(idx, prev, arr):

 

파스칼의 삼각형을 그리는 함수

• idx 는 현재 몇 번째 줄을 그리고 있는지를 나타낸다.
• prev는 이전 줄의 값을 담고 있다. 현재 줄의 숫자들은 이전 줄의 숫자들을 더해서 만들어지기 때문에 필요하다.
• arr 은 전체 파스칼 삼각형을 담을 2차원 리스트다.

 

기저 조건 (멈추는 조건)

if idx == N:    
    return

• 파스칼의 삼각형을 언제 멈출지 결정한다.
• idx가 삼각형의 줄 수인 N에 도달하면 더 이상 그릴 필요가 없기 때문에 함수를 종료한다.

 

한 줄을 채우는 방법

for j in range(idx + 1):

• 이 부분은 현재 줄에 몇 개의 숫자를 채울지 정하는 반복문이다.
• ex) 첫 번째 줄은 하나의 숫자, 두번째 - 두 개의 숫자, 세번째 - 세 개의 숫자를 채워야 하니까 idx+1 번 반복한다.

 

첫 번째 숫자는 1

if j == 0:
    arr[idx][j] = 1

• 각 줄의 첫 번째 숫자는 항상 1이므로, 첫 번째 칸(j==0) 에는 1을 넣는다.

 

나머지 숫자는 윗줄 두 숫자의 합

else:
    arr[idx][j] = prev[j - 1] + prev[j]

 

• 첫 번째 숫자 이외의 나머지 숫자들은 바로 윗줄에 있는 두 숫자를 더해서 만들어진다.
  여기서 prev[j-1] 은 이전 줄의 왼쪽 숫자, prev[j]는 이전 줄의 오른쪽 숫자(현재 위치에서 위쪽에 있는 값) 를 의미한다.

 

그 줄을 출력

print(arr[idx][j], end=' ')

• 각 줄의 숫자를 출력한다. 

 

재귀 호출 (다음 줄을 그리기 위해 함수 다시 호출)

pascal(idx + 1, arr[idx], arr)

• 다음 줄을 그리기 위해 함수를 다시 호출한다
  이번 줄을 다 해줬으면, 다음 줄을 그릴 차례이다. idx+1 을 통해 다음 줄로 넘어가고, arr[idx]는 이번줄의 값을 prev로 넘겨줘서 다음 줄을 만들 때 사용할 수 있게 한다. 
• arr[idx]의 역할
  • arr은 전체 파스칼 삼각형을 담는 2차원 배열이고, arr[idx]는 현재 줄을 나타낸다.
  • 파스칼 삼각형에서 현재 줄의 값을 구할 때, 이전 줄의 값을 참고해서 새로운 값을 만든다. 
    그래서 현재 줄을 구한 후에는 그 줄을 다음 줄의 '이전 줄'로 넘겨주어야 한다.
  • 여기서 arr[idx]가 현재 줄의 값을 담은 리스트이고, 이 값을 다음 호출에서 prev로 사용하게 된다.

 

입력 받기 및 배열 초기화

T = int(input())
for tc in range(1, T + 1):
    N = int(input())
    arr = [[0] * N for _ in range(N)]

• 테스트케이스의 수와 파스칼 삼각형의 줄 수를 입력받는다.
• arr은 N x N 크기의 2차원 리스트로, 파스칼 삼각형을 저장할 공간을 만든다.

 

삼각형 출력

print(f'#{tc}')
pascal(0, [], arr)

• 각 테스트 케이스에 대해 파스칼 삼각형을 그리기 시작한다.
• pascal(0, [], arr) 로 첫 번째 줄부터 삼각형을 그리기 시작한다. 

 

---

💡 소스 코드

def pascal(idx, prev, arr):
    if idx == N:
        return

    # 행 채우기
    for j in range(idx + 1):
        # 첫번째 열 1로 채우기
        if j == 0:
            arr[idx][j] = 1
        else:
            arr[idx][j] = prev[j - 1] + prev[j]
        print(arr[idx][j], end=' ')
    print()

    # 다음 행 채우러 가기
    pascal(idx + 1, arr[idx], arr)


T = int(input())
for tc in range(1, T + 1):
    N = int(input())
    arr = [[0] * N for _ in range(N)]

    print(f'#{tc}')
    pascal(0, [], arr)

 

🔎 회고

• 재귀 연습의 필요성을 느