주요 전략
- 귀납추론 : 주어진 문제보다 조금 작은 문제들의 답을 안다면 그 것을 이용해서 더 큰 문제의 답을 구할 수 있다!
문제해결 순서
1. 문제 정의 : P(n) : n개의 값에 대한 해
2. 일반화 : 부분문제 정의
3. 기저조건 : P(1)=1, P(2)=2
4. 재귀식 : 거꾸로, 경우로 나눈다 - P(i) = P(i-1) + P(i-2)
5. 코딩
# 사다리 올라가기
# 1칸 또는 2칸 올라갈 수 있음, N층 까지 올라가는 경우의 수
ladder = [1, 2]
n = int(input())
for i in range(2, n):
ladder.append(ladder[i-1] + ladder[i-2])
print(ladder[n-1])
--------------------------------------------------------------------
# 비트 스트리밍
# 1이 연속하지 않는 길이 k의 비트 스트링 수
bit = [2, 3]
n = int(input())
for i in range(2, n):
bit.append(bit[i-1] + bit[i-2])
print(bit[n-1])
--------------------------------------------------------------------
# 최장 증가 부분 수열
# 5 2 8 6 3 6 9 7
# P(k) = 앞에 있는 숫자 중에서 확장 할 수 있는 수 중에 P값이 가장 큰 수
arr = [5, 2, 8, 6, 3, 6, 9, 7]
l = [1]
for i in range(1, len(arr)):
m_len = 0
m_num = 0
for j in range(0, i):
if arr[i] > arr[j]:
if m_len <= l[j]:
m_len = l[j]
if m_len == l[j] and m_num < arr[j]:
m_num = arr[j]
l.append(m_len + 1)
print(max(l))
'Study' 카테고리의 다른 글
[자격증] 데이터분석전문가 ADP 실기 24회 후기 (0) | 2022.05.11 |
---|---|
AI(Artificial Intelligence) 인공지능이란 무엇일까 (0) | 2022.04.28 |
[알고리즘] 재귀함수(Recursive Function)를 활용한 이진탐색(Binary Search) using by Python (0) | 2022.03.22 |
Let's keep the environment clean (0) | 2022.03.14 |
ADP 23회 데이터분석 전문가 실기 후기 (0) | 2021.12.20 |