일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 백준
- 스프링 번역
- 컴퓨터공학기초
- MariaDB
- 2375
- bitbucket
- event_scheduler
- RESTful
- search api
- 11053
- 빗버킷
- Programming
- DP
- 젠킨스
- WebFlux
- 자바
- 페이징
- 도커
- jenkins
- 검색 API
- 다이나믹프로그래밍
- 알고리즘다지기프로젝트
- while
- 알고리즘
- Reactive stream
- Today
- Total
쑥로그
알고리즘 스터디 2주차 준비 - 동적계획법 #1 본문
1주차 분할정복 문제로 울타리 자르기 문제를 풀었다.
https://algospot.com/judge/problem/read/FENCE
algospot.com :: FENCE
울타리 잘라내기 문제 정보 문제 너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체하기로 했습니다. 이 때 버리는 울타리의 일부를 직사각형으로 잘라내 재활용하고 싶습니다. 그림 (b)는 (a)의 울타리에서 잘라낼 수 있는 많은 직사각형 중 가장 넓은 직사각형을 보여줍니다. 울타리를 구성하는 각 판자의 높이가 주어질 때, 잘라낼 수 있는 직사각형의 최대
algospot.com
아이디어가 잘 떠오르지 않아서 고생했다. 원래같으면 for문 열심히 돌려서
문제를 풀었을 것이다. 시간복잡도는 O(n^2)가 나왔을 것이다.
이걸 분할정복으로 풀라니 base case가 구체적으로 잘 떠오르지 않았다.
면적을 구하는 것일텐데 어떻게 구해서 합치지? 라는 생각에 애먹었던 문제.
포인트는 height를 계속 갱신해가면서 인덱스 두개를 이용해 사각형을 확장시켜나가는 것이다.
https://github.com/mychum1/shelf/blob/master/com.ksko.algorithm/src.main.java/basic/Fence.java
mychum1/shelf
shelf for docs stuied. Contribute to mychum1/shelf development by creating an account on GitHub.
github.com
2주차는 동적계획법이다.
mychum1/shelf
shelf for docs stuied. Contribute to mychum1/shelf development by creating an account on GitHub.
github.com
커리큘럼 -
1. 메모이제이션 설명 + 난이도 하. 외발뛰기 문제
2. 전통적 방법 + 난이도 하. 타일링방법의 수
3. 경우의 수 + 난이도 중. 삼각형 위의 최대 경로 개수 세기
'개인 프로젝트 > 72일 알고리즘 다지기 프로젝트' 카테고리의 다른 글
[자바] 백준 14501 문제 풀이 - 퇴사 (0) | 2019.09.17 |
---|---|
[자바] 백준 11053 가장 긴 증가하는 수열 (0) | 2019.09.14 |
[자바] 백준 1912 - 연속합 풀이 (0) | 2019.09.10 |
72일 알고리즘 스터디 커리큘럼 (0) | 2019.08.25 |
알고리즘 스터디 1주차 준비 - 분할정복 (0) | 2019.08.22 |