줌코딩의 코딩일기

문제 문제 링크 문제 접근 이 문제는 트리를 이해하고 디피를 활용하는 방법을 이해하고 있다면 풀 수 있는 문제이다. 트리는 사이클이 존재하지 않음으로 하나의 점에서 부터 시작해서 이전 값을 이용해서 풀어나가는 dp를 사용할 수 있다. 이 문제를 디피로 푸는 방법이 떠오르지 않는다면 백준 1520번 내리막길을 한번 풀어보길 바란다. 디피 방법 dfs를...

문제 문제 링크 문제 접근 이 문제는 모든 노드가 연결되는 최소 엣지를 찾는 MST를 구하는 문제이다. 여기서 문제는 가장 짧은 거리를 구해야한다는 것이다. 이를 위해서 priority queue를 이용해서 미리 거리를 다 구해놓고 하나씩 연결해가면서 싸이클이 발생하는지 확인하는 과정을 진행하였다. 코드 #include <cstdio> #include <queue> #include <cmath> #define pii pair<int, int>...

문제 문제 링크 문제 접근 딱 트리에 디피 쓰면 될 문제로 보인다. 근데 문제는…. 디피를 쓰기에 노드개수 최대 10만개, 색깔개수 10만개?? 그럼 dp[100001][100001]인데 말이 안되잖아.. 이때 등판한 구원투수 구사과님 ㅠㅠ 색깔의 수 정하기 증명(갓구사과님) 그렇다면 색깔은 log_2(100000)개 최대 16개의 색깔을 가지게 된다. 이를 디피를 이용해서 풀어내면 된다. How dp 현재...

문제 문제 링크 문제 접근 이 문제는 문제를 어떻게 접근할지 잘 생각해봐야 한다. Union Find를 이용해서 오히려 Union 되있는것을 하나씩 부서가면서(Collapse) 진행하면 되지 않을까 생각했지만 그 또한 시간 초과를 발생시킨다. 여기서 발상의 전환을 유발하는 내용이 문제 설명에 존재한다. 다음 (N-1)+Q개의 줄 중에서 N-1개는 (1)의 형태로, Q개는 (2)의 형태로 주어진다. (1)...

문제 문제 링크 문제 접근 이 문제는 큐를 이용해서 해결할 수 있다. 차선을 큐라고 생각하고 하나씩 제거하고 추가하기를 반복한다. 이때 만약 새로운 원소의 무게를 감당할 수 없을 때는 들어올 수 있을 때까지 0을 넣어준다. 이를 반복하면서 cnt를 확인한다. 코드 #include <cstdio> #include <queue> using namespace std; int n, w, l,...