[구현 알고리즘] 2005. 파스칼의 삼각형 (파이썬)

안녕하세요. Harry입니다.

 

본 포스팅의 목적은, 코딩테스트를 준비함에 있어 SWEA에 제시된 문제 풀이와 스스로 얻은 정보를 정리하고자 합니다.

그러므로 단순히 문제를 푸는 것이 중요한 것이 아니라, 문제를 통해 얻어가는 것이 있어야하기 때문에 접근 방식은 이전 기초 300제를 풀었을 때랑 동일합니다.

 

[접근 방식]

- 문제에서 요구하는 역량은 무엇인지?

- 알고 있어야하는 지식은 무엇인지? 에 기반하여 풀이하고자 합니다.

 

- SWEA 문제 링크입니다. : https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&contestProbId=AV5P0-h6Ak4DFAUq&categoryId=AV5P0-h6Ak4DFAUq&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=2&pageSize=10&pageIndex=1 

SW Expert Academy

[풀이 아이디어]

- 0으로 구성된 빈 2차원 리스트(triangle) 생성

- 위 리스트에 인덱스 값을 활용하여 값 대입

- 삼각형의 가장자리 = triangle 리스트 내 각 리스트 첫값(맨 처음 인덱스) 과 마지막 값(맨 마지막 인덱스) = 1로 대입

- 나머지 값을 구하기 위해선 triangle[k-1][u-1](왼쪽 대각선 값) + triangle[k-1][u](오른쪽 대각선 값)을 더하면 된다.

[코드]

t = int(input())
for i in range(t):
    size = int(input())
    triangle = [[0]*size for j in range(size)]
    # 맨 처음과 마지막은 모두 1 처리
    # 즉, 삼각형의 가장자리는 모두 1이 된다.
    for k in range(size):
        triangle[k][0] = 1
        triangle[k][k] = 1
    # 1이 아닌 삼각형 내부의 값은 왼쪽 대각선 값 + 오른쪽 대각선 값이므로, 인덱스 값으로 접근해서 계산
    for k in range(2,size):
         for u in range(1,len(triangle[k])):
                 triangle[k][u] = triangle[k-1][u-1] + triangle[k-1][u]

    print('#'f'{i+1}')
    for k in range(len(triangle)):
        for q in triangle[k]:
            if q != 0:
                print(q,end=' ')
        print()

감사합니다.