Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- vue.js
- fastapi
- jpa
- LLaMa
- GPT
- kubernetes
- 생성형 AI
- Redis
- 컨설턴트
- 솔루션조사
- 오픈시프트
- OpenShift
- Docker
- 로깅
- fast api
- SpringBoot
- Python
- 머신러닝
- BFS
- Machine Learning
- 생성형
- 도커
- LeetCode
- 리트코드
- POD
- k8s
- vuejs
- 쿠버네티스
- 컨설팅
- 메세지큐
Archives
- Today
- Total
수 많은 우문은 현답을 만든다
Recursion: Davis' Staircase 본문
순수하게 짜려고하면 대략 3중 for문이 나온다.
딱히 그래프 데이터도없고 좌우로 이동하는 내용도 없으니 DFS, BFS는 아닌듯 하다.
이럴땐 수학적으로 접근해 작은 단위부터 규칙을 찾는수밖에...
다이나믹 프로그래밍(Dynamic Programming):
- 목적: 최적 부분 구조를 갖춘 문제를 해결하기 위한 기법으로, 작은 부분 문제들의 해를 저장하고 활용하여 전체 문제의 해를 효율적으로 계산하는 것이 목적입니다.
- 작동 방식: 문제를 작은 부분 문제들로 나누고, 각 부분 문제에 대한 해를 계산하여 메모이제이션(기억화)하며, 이를 조합하여 전체 문제에 대한 해를 구합니다. Bottom-up 방식과 Top-down 방식이 있습니다.
풀이
# n=1
# 1
# n=2
# 11
# 2
# n=3
# 111
# 12
# 21
# 3
def stepPerms(n):
if n <= 2:
return n
if n == 3:
return 4
return stepPerms(n-1) + stepPerms(n-2) + stepPerms(n-3)
에엣? Time limit exceeded 가 발생했다.
문제에서 주어진 stepPerms 함수는 재귀적으로 계단을 오르는 방법의 수를 찾는 방법으로 작성되어 있습니다. 그러나 이 함수는 중복 계산을 많이 수행하므로 큰 입력에 대해서는 시간 초과가 발생할 수 있습니다. 이를 해결하기 위해서는 다이나믹 프로그래밍(Dynamic Programming)의 메모이제이션(Memoization) 기법을 사용하여 중복 계산을 피해야 합니다. 아래는 메모이제이션을 적용한 코드입니다:
memo = {}
def stepPerms(n):
if n <= 2:
return n
elif n == 3:
return 4
if n not in memo:
memo[n] = stepPerms(n-1) + stepPerms(n-2) + stepPerms(n-3)
return memo[n]
완성!