2020. 4. 9. 16:21ㆍPS/Problem Solving
Code SASA가 다시 열린 기념으로 선배들이 만든 문제를 풀었다.
그러던 도중 예전에 풀었던 문제를 발견했다.
https://code.sasa.hs.kr/problem.php?id=1297
SASA OJ
영화를 좋아하는 세종이는 쉬는날인 오늘 영화관에 가서 하루종일 영화를 보려고 한다. 오늘 상영하는 영화의 개수를 N, 각각의 영화의 상영 시작 시간을 S, 상영 종료 시간을 E라고 할 때, 오늘 세종이가 볼 수 있는 영화의 최대 수를 출력하여라. (단, 오늘 24시 이전에 시작하여 다음날에 끝나는 영화도 오늘 상영하는 영화에 포함하며, 상영시간이 24시간 이상인 영화는 없다.)
code.sasa.hs.kr
(전형적으로 보이는) 영화 스케줄링 문제이다. 어떻게 풀었나 싶어 봤더니 웬걸 N=100 인데도 불구하고 지수시간 알고리즘으로 백트래킹을 돌리고 있었다. 코드가 통과는 했지만, 기분이 영 찝찝하다. 그래서 Interval Scheduling에 대한 공부를 했다.
상황에 맞는 완벽한 블로그 포스팅이 있었다. https://suuntree.tistory.com/103
그리디
<설명> 1. 그리디로 항상 최적해를 구할 수 있다면, 그리디는 dp보다 훨씬 빠르다. (그리디로 풀리면 보통 dp로도 풀린다) 2. 시공간 제약으로 인해 최적해를 찾는 것이 극히 제한되는 경우, 근사해를 찾아준다. p..
suuntree.tistory.com
내가 필요했던 것은 1. 활동 선택 문제 (activity - selection problem) 에 대한 내용이었다.
결론적으로는 끝나는 시간이 앞에 오는 순으로 정렬한 다음, 차례대로 가능할 경우 선택해주면 된다.
느낌
귀류법으로 자신의 풀이를 증명한 것이 인상적이다.
그리디 기법을 사용할 때는 항상 증명이 필요하다는 것을 배웠다.
그리디에 대한 설명 글을 올린 적이 한번 있었는데, 정말 파도 파도 재밌는 문제 종류가 그리디인 것 같다.
아래 문제들은 대부분 재밌다.
https://codeup.kr/problemsetsol.php?psid=1
비고
참고한 블로그
https://potensj.tistory.com/45
https://suuntree.tistory.com/103
'PS > Problem Solving' 카테고리의 다른 글
| [Code SASA] 정독실에서 tic-tac-toe (0) | 2020.05.23 |
|---|---|
| [Code SASA] 숫자 카드 게임 (0) | 2020.05.15 |
| Codeup/코드업 3180 간단한 문제 풀기 위해 공부 했던 것들 (1) | 2020.03.26 |
| 내가 보려고 만든 소인수분해 방법 정리글 (0) | 2020.02.26 |
| CodeUp에서 기억나는 문제 (0) | 2020.02.20 |