| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 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 | 31 |
Tags
- onclick
- Android Studio
- clean code
- 거쳐가는 정점
- top-down
- union-find
- compiler
- 엔테크서비스
- 기술면접
- Python
- Controller
- 최단경로
- scikit-learn
- 동적계획법
- spring boot
- dto
- Django
- 우선순위큐
- disjoint set
- BufferedReader
- Java
- 유니온 파인드
- bottom-up
- 다익스트라
- 직무면접
- 플로이드 와샬
- 코딩테스트
- 벨만 포드 알고리즘
- 음수가 포함된 최단경로
- kmeans
Archives
- Today
- Total
목록동적계획법 (1)
춤추는 개발자
[동적계획법] Top-down과 Bottom-up
Top-down과 Bottom-up의 공통적인 특징 - 다음 상태를 구하기 위해, 이전 상태를 저장하고 재사용합니다. (Memoization) - 무엇을 어떻게 저장할지 정하는 것이 중요합니다. 만약, 2차원 배열이라고 한다면, x축과 y축, 배열에 저장되는 값 이렇게 3가지를 어떤 대상으로 정의할 것인지 파악해야 합니다. - 이를 위해 정확한 문제 해석과 반복문에서 배열의 인덱스에 어떤 값을 입력해야 하는지 정해야 합니다. 적용 순서 1. 상태 정의: DP배열의 index가 의미하는 것과 문제의 초기상태 정의 2. 점화식 구하기: 다음 상태를 나타내기 위한 표현식 3. 시간복잡도 계산 www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 1..
Developer's_til/자료구조 & 알고리즘
2021. 3. 31. 00:16