Problem Solving Diary #19
요즘 애드혹 감각이 좀 줄어든 것 같아서 백준에서 플래-다이아 애드혹 문제들을 랜덤하게 10개 뽑아 풀어 보았다. 괜찮은 문제도 있었던 반면 풀기 싫은 문제도 많이 있었다. 1. ? 정말 풀기 싫은 문제가 뽑혀서 안 풀고 넘어갔다. 무슨 문제였는지는 공개하지 않는다. 2. Монотонная подпоследовательность 길이가 $n$인 순열 중 LIS나 LDS의 길이 최댓값이 $k$인 것을 찾는 문제이다. Erdos-Szekeres Theorem에 의하면 길이가 $(r-1)(s-1)+1$ 이상인 수열은 길이 $r$의 증가부분수열이나 길이 $s$의 감소부분수열이 있다. $r=s=k+1$을 넣으면, $k^2+1$ 이상의 길이를 가진 수열은 길이 $k+1$ 이상의 IS/DS가 있다. 따라서 $n >..
코딩/문제풀이
2024. 4. 15. 19:39