- 내일배움캠프 31일차 목차
[오늘 한일]
- 알고리즘 문제풀이
- 심화강의 수강
- 알고리즘 강의수강
- 소통법 특강 수강
- ERD, DB 특강 수강
[오늘 배운점]
파이썬
<선발대 과제를 풀며 배운점>
파스칼의 삼각형을 재귀함수로 구현하는 과제였다.
- 알고리즘 세우기
과제를 풀기전에 제대로된 해법을 고민해야했다.
재귀 함수를 이용하기 위해서는 동일하게 반복되는 동작을 잡아야 하는데,
그러기 위해선 전체 풀이동작을 잘 구상해봐야 했다.
이번에도 노트에 그려보면서 구상했다.
(아래에 이어짐)
- 재귀함수는 역순으로 동작한다.
재귀함수는 탈출조건에 이르기까지 계속 안쪽으로 파고드는 형태가 된다.
탈출조건을 만나면, 가장 안쪽이 먼저 종료되고,
안쪽부터 바깥쪽순으로 함수가 종료된다.
어제 예시 중에 피보나치 수열이 이걸 활용한 예이다.
(강의중에 이해가 덜 되었는데 오늘 복습해서 확실히 이해했다.)
- (다시 알고리즘 세우기)
과제에서 n이 목표 층인건 고정이고,
가장 안쪽이 1층이며 [1]인 것도 고정이다.
그럼 어떤 로직이 반복되어야 계속 같은 동작으로 코드를 작성할수 있을까.
한시간 정도를 혼자 고민했고 그 결과 적절한 동작을 찾을수 있었다.
아래층은 윗층요소들의 왼쪽하나 오른쪽 하나를 더하며 작성된다.
왼쪽 정렬을 하면 이렇다.
1
11
121
1331
그럼 윗층을 두줄로 만들어 한칸을 빗기게 하여 포개면,
바로 원하는 모양의 아래층을 만들수 있다!
그 아래층도, 그 아래층도, 계속 바로 위층의 포개진 모양이다.
한칸을 빗기어 포개지는게 바로 삼각형으로 봤을때의 왼쪽하나 오른쪽하나를 더하는게 되기 때문이다.
- 리스트를 포개는 노하우
리스트를 한칸 미루는건 쉬웠고, 리스트끼리 더하는 방법만 고민해봤다.
인터넷으로 잠깐 찾아봤는데 한방에 해주는 연산같은건 따로 없었다.
제일 적절한건 리스트 컴프리헨션이였다.
[left_one[x] +right_one[x] for x in range(len(left_one))]
이렇게 작성하면 두 리스트의 각 요소를 합친 새 리스트를 반환한다.
(다만, 두 리스트의 길이가 같아야 한다는 요건이 있다.)
여기까지를 이용해서 이렇게 코드를 작성할수 있었다.
def recursion(n):
if n <= 1:
return [1]
pre_list = recursion(n-1)
left_one = pre_list+[0]
right_one = [0]+pre_list
return [left_one[x]+right_one[x] for x in range(len(left_one))]
print(recursion(8))
<꼬리 재귀>
어제 배운 재귀함수의 분류중에 리턴값이 있는 재귀함수가 있다.
그런데 재귀함수 내에 재귀함수 호출이 리턴 부분에서 이뤄진다면,
팀원분께 배우게 됬는데, 이런걸 꼬리재귀라고 한다.
(꼬리재귀는 파이썬이 동작하며 반복문으로 컴파일한다고 한다.)
<ord, chr>
ord(문자)는 문자를 아스키코드로 바꿔준다. a는 97이된다.
chr(숫자)는 숫자를 아스키코드에 해당하는 문자로 바꿔준다. 97은 a가 된다.
alphabet_array = [0]*26을 선언하고
(이렇게 곱하기를 하면 리스트를 숫자만큼 계속 이어붙인다.)
ord(a)-97을 하여 해당하는 알파벳 리스트의 인덱스를 지칭하게끔 하는 노하우도 있다.