BOJ 11055 (가장 큰 증가하는 부분 수열)
O(N^2) 부분 수열은 어느 정도 마스터했다고 생각했는데 또 다시 막힌 문제. 그만 막히고 싶다.
← 블로그
BOJ 풀이.
BOJ?
Baekjoon Online Judge의 약자.
Related Contents
기록 8
최근 업데이트 순BOJ 1699 (제곱수의 합)
오랜만에 tag: DP로 검색해서 풀어본 문제. DP 문제는 실버까지는 굉장히 재미있다. 골드부터는 관찰이 좀 어려워져서 풀이가 힘들지만.. (23년 8월 기준) PS의 빈출 영역이기 때문에 꾸준히 연습해야 한다.
BOJ 2252 (줄 세우기)
풀이를 보면 매우 당연하지만, 그래프에 대한 개념이 확실히 되어 있지 않다면 아이디어 발상이 어려울 수 있다. 어떤 순서를 강제하는 것을 edge 연결로 볼 수 있고, 이런 조건을 만족하게끔 해둔 다음에 방문하지 않은 노드부터 차례대로 dfs로 방문해 나가면, 제일 끝에 도달하는 녀석이
BOJ 9252 (LCS 2)
LCS는 Longest Common Subsequence의 약자로 이 문제 제목에도 대놓고 쓰였다. 처음 접했을 때 생각하기 어려운 DP이고, 개같이 멸망. 아래 URL의 풀이를 거의 그대로 참고했다.
BOJ 17404 (RGB거리 2)
기존 RGB거리 문제의 강화판. 그래도 최근 DP 짬밥이 있어서 그런지 처음에 막혔어도 힌트 안보고 최종 풀이에 성공했다. 풀이 방식에는 여러가지가 있어 보이는데, 나는 DP 차원을 확장하는 것으로 해결했다.
BOJ 6549 (직사각형 최대 넓이 구하기)
예전에 스택으로 풀 수 있다는 이야기만 듣고 덮어놨었던 문제. 다이아몬드 가공 문제에서 최대 면적을 빠르게 구해야할 필요가 있어서 다시 꺼내 풀어보았다.
BOJ 11727 (2xn 타일링)
간단한 DP 연습 문제. 아래 점화식을 N = 3, 4, 5 반복해보면 관찰할 수 있다.
BOJ 11057 (오르막 수)
간단한 DP 연습 문제. 오르막 수는 n번째 자리에 올 수 있는 수가 n - 1번째 자리에 올 수 있는 수로 정해진다.