PS 1000문제 도전기 - 23일차 [백준]

오늘 공부한 내용 & 푼 주요 문제

12015 - 가장 긴 증가하는 부분 수열 2(골드 2)

https://www.acmicpc.net/problem/12015

12738 - 가장 긴 증가하는 부분 수열 3(골드 2)

https://www.acmicpc.net/problem/12738

14002 - 가장 긴 증가하는 부분 수열 4(골드 4)

https://www.acmicpc.net/problem/14002

14003 - 가장 긴 증가하는 부분 수열 5(플레 5)

https://www.acmicpc.net/problem/14003

LIS의 대표적인 문제. n이작을때는 DP를 이용해 풀면 시간복잡도가 O(n^2)이기 때문에 시간초과가 난다. 따라서 이분탐색을 사용해서 풀어야 한다. 이에 대한 내용은 따로 정리해서 올려보겠다.

 

2565 - 전깃줄(골드 5)

https://www.acmicpc.net/problem/2565

2568 - 전깃줄2(플레 5)

https://www.acmicpc.net/problem/2568

LIS를 활용해서 푸는 문제. 사실 전깃줄2를 풀기 위해서 위 내용을 공부했다. 덕분에 레이팅 날먹 할 수 있었다.

 

오늘 푼 잔여 문제

1문제 풀었다.

현황

레이팅: 1338 -> 1373(+35)

푼 문제 수: 569 -> 576(+7)