줌코딩의 코딩일기

문제 2시간반 만에 풀어냈다.. 후우! 문제 링크 문제 요점 여러 개일 수도 있는 최단 경로를 어떻게 빨리 찾아낼지가 제일 중요한 문제이다. 어떻게 접근할 것인가 처음에는 그냥 최단경로를 계속해서 발견할 때마다 prev에 저장해서 다익스트라 알고리즘이 끝나면 최단경로의 prev에 있는 길을 다 차단해주려 했다. 근데 그건 시간 초과를 발생시켰다… 여러번 최단경로를 찾는...

문제 문제 링크 어떻게 접근할 것인가 벽을 부수는 문제이다. 벽을 부수면서 가장 적게 부수면서 뚫을 수 있는 방법이 발견되면 해당 위치를 큐에 넣어주었다. 코드 #include <cstdio> #include <vector> #include <queue> #define pii pair<int, int> #define X first #define Y second using namespace std; int main(){ char miro[102][102]; int d[4][2] =...

문제 문제 링크 어떻게 접근할 것인가 이 문제는 모든 친구들의 왕복 최단 거리를 알아야한다. 그래서 플로이드 와샬 알고리즘을 이용해서 문제를 풀었다. 코드 #include <cstdio> using namespace std; int n, m, x, w, v1, v2, M, d[1001][1001]; char buf[1 << 17]; inline char read() { static int idx = 1 <<...

문제 문제 링크 어떻게 접근할 것인가 전형적인 탐색 문제였다! 코드 #include <cstdio> #include <queue> using namespace std; typedef struct Point{ int x, y, w; bool operator<(const Point& o)const { return w > o.w; } }Point; char buf[1 << 17]; inline char read() { static int idx = 1 << 17;...

문제 문제 링크 어떻게 접근할 것인가 이 문제는 LCA를 변형해서 풀어야 하는 문제이다. 각 노드의 조상 2의 곱으로 저장할 뿐만 아니라 현재 노드부터 2의 곱 위치까지의 max와 min(M,m)을 저장해두어서 이용해야 한다. LCA를 완벽하게 이해했다면 풀수 있는 아주 좋은 문제인 듯 하다!! 예를 들어, 7번째 조상까지의 min과 max를 찾는다고 하면 7은...