쑥로그

알고리즘 스터디 2주차 준비 - 동적계획법 #1 본문

개인 프로젝트/72일 알고리즘 다지기 프로젝트

알고리즘 스터디 2주차 준비 - 동적계획법 #1

SOOOOOK 2019. 8. 31. 01:25

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주차는 동적계획법이다.

https://github.com/mychum1/shelf/blob/master/com.ksko.algorithm/src.main.java/basic/dynamicProgramming1.md

 

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
'개인 프로젝트/72일 알고리즘 다지기 프로젝트' Related Articles more