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
- 사이드 프로젝트
- 안드로이드
- 14891_톱니바퀴
- datastore
- 알고리즘
- 캣푸드 기록장
- 백준
- 안드로이드 애니메이션
- 사이드프로젝트
- 잡담글
- DynammincProgramming
- velog
- ARCore
- 애니메이션
- motionlayout
- viewpager
- 파이썬
- AndroidStudion4.1
- Android
- 스택/큐
- singleclick
- viewBinding
- Delgate Pattern
- 짤팁
- Android#Kotlin#사진
- VectorDrawable
- Desigin Pattern
- SpringAnimation
- Python
- kotlin
Archives
- Today
- Total
목록DynammincProgramming (1)
밍맹의 생각날 때 적는 블로그
[백준/Python] 1463_1로 만들기 (Dynamic Programming)
[문제 링크] 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 사용자에게 입력받은 수를 다음과 같은 조건으로 1로 만드는 최소 경우의 수를 찾으면 된다. 1을 뺀다 2로 나누어진다면 2로 나눈다. 3으로 나누어진다면 3으로 나눈다. 10을 예시로 들면 10 -> 9 -> 3 -> 1로 총 3번이면 1로 만들 수 있다. 이 문제는 다이내믹 프로그래밍(DP)으로 풀 수 있다. 다이내믹 프로그래밍이란 큰 문제를 작은 문제로 단순화시켜 해결하는 알고리즘이다. 10에서 1을 뺐을 경우 9가 된다. 여기서 우리가 만약 9가 1이 되는 최소 횟수를 알고 있다면?? (9가 1이 되는 최소 횟수) + 1 (10에서 1을 빼 9로 갈 때 횟..
알고리즘(Python)
2020. 6. 12. 15:32