알고리즘 공부방

https://contests.ioi-jp.org/open-2018/index.htmlhttps://oj.uz/problems/source/351 역시 JOIOC는 어렵다. 문제 하나하나가 다 좋은 문제이고, 많이 생각할 수 있게 해주는 문제들인 것 같다.4일동안 1, 4번을 풀었고, 2번은 부분점수, 3번은 풀지 못하였다.Heavy Light Decomposition을 응용한 DP 최적화, Sqrt Decomposition 등 아직 내가 익숙하지 않은 개념들이 많이 이용되어서 더 어렵게 느껴진 것 같다. 나중에 이런 개념들을 잘 익힌 후에 꼭 다시 풀어봐야 할 문제들이다. 4. xylophone 순열이 하나 있고, 물어볼 수 있는 쿼리는 오직 어떤 구간 내의 최대값-최솟값만 물어볼 수 있을 때 2N 번..

https://www.ioi-jp.org/joi/2017/2018-ho/index.htmlhttps://oj.uz/problems/source/307 1, 2번까지는 무난하게 풀 수 있었고, 3, 4번을 푸는데 내 힘으로 풀지 못하고 여러 블로그들과 공식 풀이를 보며 풀어 이틀이 걸렸다. 5번 문제는 공식 풀이 슬라이드를 봐도 도무지 이해가 안가 나중에 다시 풀어봐야 할 것 같다. 이번 셋을 풀면서 느낀 점은 DP의 중요성과, 그래프 문제들은 역시 관찰과 연습만이 답인 것 같다. 또한, 역시 JOI 문제들은 문제의 질과 수준 모두 매우 좋은 것 같다. 1. stove 만약 K번 킬 수 있다면 각 난로를 켜야하는 시간에만 켜놓으면 된다. 그럼, 그 이하라면 어떻게 해야 할까?전체 구간을 기준으로 난로를 켜..

문제 https://www.acmicpc.net/problem/1648 N*M 크기의 격자판을 2*1 모양의 타일로 채우는 경우의 수를 출력하는 문제이다. 풀이 일단 당연히 비트마스크 dp 문제이다. 더욱 자세한 풀이는 https://www.slideshare.net/Baekjoon/baekjoon-online-judge-1648 을 참고하자. 이와 같이 각 칸에 번호를 붙이자. solve(pos, mask) = pos 번째 위치 전까지의 번호는 모두 채워져 있고, 비트마스크가 mask 일때 경우의 수를 의미한다. 비트마스크의 표현 범위는 만약 pos 가 15라면 15~20을 표현한다. 21번부터는 표현할 필요가 없음을 알 수 있다. 왜냐하면 21번을 포함하는 타일이 1~14중 하나를 동시에 포함할 수가..

우선, $O(N^2)$ DP 풀이부터 살펴 보자. $dp[i]$ = $0$ ~ $i$ 구간에서 $i$를 끝으로 하는 lis의 최대 길이 $dp[i]$ = $0$ ~ $i-1$ 의 $j$ 에 대하여 $arr[i]>arr[j]$를 만족하고, $dp[j]+1$의 최대값을 만족한다. 여기서는 구현할 때 처음에 NEGINF, 끝에 INF 를 추가해서 구현하였고, 동시에 전 단계로의 선택 과정을 담아 복원까지 했다. #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; const int MAXN = 1000; const int INF = numeric_limits::max(); const int NEGINF = ..