CHAAANY ARCHIVE
4개의 기록을 주제별로 둘러보세요.
백준 12015를 풀던 2022년 5월에는 이진 탐색에 심리적인 거부감이 있었다. 반나절 정도 접근을 고민한 뒤 list를 이용한 풀이를 찾아봤고, 그대로 끝내지 않고 array 방식으로 다시 구현했다. 당시 제출에서는 list 풀이가 756ms, array 풀이가 592ms였지만 한 번의 채점 결과를 일반적인 성능 benchmark로 보지는 않는다.이 문제에서 가져갈 핵심은 각 길이의 증가 부분 수열이 가질 수 있는 가장 작은 마지막 값을 tails에 유지하는 것이다.tails의 의미tails[i]를 길이가 i + 1인 strictly increasing subsequence 중 현재까지 찾은 최소 마지막 값이라고 정의한다.새 값 value가 들어오면 다음 두 경우다.value가 현재 모든 tail보다..
백준 2565번 ‘전깃줄’은 서로 교차하지 않도록 최소 몇 개의 전깃줄을 제거해야 하는지 묻는다. A 전봇대 위치를 기준으로 정렬하면, 교차하지 않고 남길 수 있는 전깃줄은 B 위치가 strictly increasing하는 부분 수열이 된다.백준 2565번 전깃줄교차 조건을 LIS로 바꾸기A 위치가 작은 전깃줄을 먼저 놓았다고 하자. 두 전깃줄이 교차하지 않으려면 뒤 전깃줄의 B 위치도 더 커야 한다.A1 B2 → 교차함따라서 A로 정렬한 뒤 B sequence의 LIS(Longest Increasing Subsequence)를 구하면 최대한 많이 남길 수 있는 전깃줄 수가 나온다.최소 제거 수 = 전체 전깃줄 수 - LIS 길이Java 코드문제의 N ≤ 100에서는 이해하기 쉬운 O(N²) DP로 ..
백준 11054번 ‘가장 긴 바이토닉 부분 수열’은 어떤 peak까지 strictly increasing하고, 그 뒤 strictly decreasing하는 부분 수열의 최대 길이를 구한다. 각 index를 peak로 가정해 왼쪽에서 끝나는 LIS와 오른쪽으로 시작하는 감소 수열 길이를 더하면 된다.백준 11054번 가장 긴 바이토닉 부분 수열두 DP 배열의 의미increasing[i]: values[i]에서 끝나는 가장 긴 증가 부분 수열decreasing[i]: values[i]에서 시작하는 가장 긴 감소 부분 수열두 값 모두 자기 자신을 포함하므로 1로 시작한다.increasing[i]= max(increasing[j] + 1), j i and values[j] index i를 peak로 합칠 때..
백준 11053번 ‘가장 긴 증가하는 부분 수열’은 원래 순서를 유지하면서 값이 strictly increasing하는 부분 수열의 최대 길이를 구한다. N ≤ 1,000이므로 각 원소 앞의 모든 후보를 확인하는 O(N²) DP로 충분하다.백준 11053번 가장 긴 증가하는 부분 수열dp[i]는 i에서 끝나야 한다상태를 “i번째까지 본 전체 LIS”로 잡으면 다음 값과 어떻게 연결할지 정보가 부족하다. 대신 다음처럼 제한한다.dp[i] = values[i]를 마지막 원소로 반드시 포함하는 LIS 길이앞 index j 중 values[j] 인 원소 뒤에만 현재 값을 붙일 수 있다.dp[i] = max(dp[j] + 1) where j 붙일 이전 원소가 없어도 자기 자신 하나로 길이 1의 부분..