TIL) 8주차 3일

하면 할 수록 어려운 알고리즘..

 

그래도 혼자 하는게 아니라 

 

팀원들과 다같이 해서 다양한 답이 나온다

 

오늘도 화이팅!

---

코딩테스트 - 파스칼 함수 구하기

---

나는 처음에 접근을 빈 리스트를 초기화 해주고 그안에 인덱스 0 부터 값을 넣어주면 되겠다 라고 생각했다. 그래서 짠 코드가 아래 코드이다.

def pascal(n):
    p=[]
    p[0] = 1
    	.
        .
        .
    retunr p

이런식으로 생각을 했었는데 IndexError가 떴다. 아예 잘못 생각 하고 있던것이다... 파이썬에선 리스트에 값을 추가 해주려면 append() 또는 extend() 또는 += 를 사용 해주어야 한다. 

 

다음으로 생각해낸것이 아래코드이다.

def pascal(n):
  if n <= 2 : return [1]*n
  elif n>2 : 
    return [1] + [pascal(n-1)] + [1]

이 코드같은 경우엔,

n=3 : [1, [1, 1], 1]

n=4 : [1, [1, [1, 1], 1], 1] 

이런식으로 나온다.

 

그래서 2차원 배열로 만들어지는 가운데 리스트 부분들을 더해주면 원하는 값을 만들 수 있겠다 라는 생각을 하게 되었다. n=3 일때는 [1, 2, 1] 이 만들어 져야 하고, n=4 일땐 [1, [ 1, 2, 1], 1] → [1, 3, 3, 1] 이 만들어 지는 것이다.

 

즉, 인덱스로 생각해보면 n=3 일때는 pascal(n-1)의 0번째 인덱스와 1번째 인덱스의 합이고, n=4일때는 pascal(n-1)의 0번째 인덱스와 1번째 인덱스의 합 + pascal(n-1)의 1번째 인덱스와 2번째 인덱스의 합이다.

이걸 식으로 풀어낸다면 , pascal(n-1)[a] + pascal(n-1)[a+1] for a in range(0, n-2) 이다.

아래는 수정 후 코드이다.

def pascal(n):

  if n <= 2 : return [1]*n
  elif n>2 : 
    return [1] + [pascal(n-1)[i] + pascal(n-1)[i+1] for i in range(0, n-2)] + [1]

  

재귀함수를 제대로 이해하면 크게 어렵지 않은 문제지만 재귀함수 자체가 어려운것 같다.. 

---