안녕하세요. 블로그 운영자 김도훈입니다. "알고리즘 과외 합니다"여는 말"알고리즘 과외? 그런 것도 있어?"보통 알고리즘 과외 얘기를 꺼내면 반응은 이렇습니다.사람들에게 알고리즘 과외가 생소한 것은 사실입니다. 어쩌면, 알고리즘 공부가 현재처럼 대중적으로 자리잡은 것은 오래되지 않았기에 생소한 것이 오히려 당연할 수도 있습니다.알고리즘 문제를 푸는 과정은 꽤 길고 복잡합니다. 또한 숙련된 사람이라도 주기적으로 난관을 부딪힐 수 밖에 없는 분야입니다. 따라서 난관에 부딪혔을 때 가능한 한 빠르게 헤쳐나오고, 다음 단계를 향해 나아가도록 도와주는 멘토가 있다면 성장의 속도는 확연히 높아질 수 밖에 없습니다.만약 본인의 성장이 더뎌지고 있거나, 꾸준히 이끌어주는 멘토가 있었으면 좋겠다는 마음이 있다면 과외가 ..
KOI는 Korean Olympiad in Informatics의 약자로, 한국 정보 올림피아드를 말합니다. 이 대회는 1차 대회와 2차 대회로 이루어져 있고, 1차 대회는 이산 수학을 바탕으로 하는 수학 문제들로 이루어진 1교시와 알고리즘 문제들로 이루어진 2교시로 나누어 진행됩니다. 자세한 정보는 koi.or.kr에서 확인하실 수 있습니다. koi.or.kr에 2교시 문제들의 풀이는 공개되어 있지만 1교시 문제들의 풀이는 제공하지 않아서 풀이를 작성했습니다. 팀원 찾기: 엄밀한 증명 고민 중... 1교시 풀이 문제의 지문은 링크에서 확인하실 수 있습니다. 또한, biko.kr에서 문제를 채점받을 수 있습니다. 다음은 각 문제에 대해 개인적으로 부여한 난이도와 실제 배점입니다. 1. 그래프의 지름 2...
문제 링크 이 문제를 풀기 전에 BOI의 굉장한 학생을 먼저 풀어보시는 것을 추천드립니다. 풀이 더보기 다익스트라로 $A$로부터의 거리, $B$로부터의 거리, $C$로부터의 거리를 구한 뒤, $A$로부터의 거리의 오름차순으로 $B$로부터의 거리를 좌표압축한 인덱스에 $C$로부터의 거리를 업데이트해주면 된다. #include using namespace std; using ii = pair; using ll = long long; void o_o(){ cerr c >> m; rep(i,1,m) { int x, y, z; cin >> x >> y >> z; adj[x].emplace_back(y,z); adj[y].emplace_back(x,z); } vector v(n); vector bs; ll da[N..
문제 링크 Subtask: $M = 2, 3 ≤ N ≤ 10\,000$ (14점) 더보기 어차피 부분행렬 속 각 열 속의 등수가 전부 같은 것이 조건이므로, 행렬의 각 열의 순서는 바뀌어도 상관이 없다. 따라서 각 열을 첫번째 행의 크기 순서대로 정렬하는 것이 가능한데, 이러면 LIS 문제로 환원되어 쉽게 풀 수 있다. $O(n^2)$으로도 가능한데, $O(n\log n)$으로 풀어 Subtask #3와 함께 긁었다. Subtask: $M = 3, 3 ≤ N ≤ 10\,000$ (9점) 더보기 $O(n\log n)$의 LIS는 적용할 수 없다. 따라서 $O(n^2)$ LIS를 사용하여 풀 수 있다. 코드 Subtask: $M = 2, 3 ≤ N ≤ 2\cdot 10^5$ (15점) 더보기 세그트리를 이용..
문제 링크재밌는 트리 DP 문제였다.편의상 각 사원 $i$의 실력을 $V_i$, 부모를 $P_i$라고 하자.Subtask: $V_i > 0$ (17점)더보기그냥 최대한 많이 포함하면 이득이다.그런데, 한 팀의 팀장을 전체 트리의 루트로 잡아버리면 다른 팀이 만들어질 수 없다.또한, 루트의 $k$대 독자 후손 노드도 잡아버리면 다른 팀이 만들어질 수 없다. 따라서 1번 노드에서부터 DFS를 돌리다가 처음으로 자식 노드가 2개 이상이 된다면 가장 큰 2개만 골라주면 된다.필자의 코드이다.Subtask: $N\le 5\ 000,\ P_i=i-1$ (12점)더보기직선형 그래프에서 문제를 풀면 된다.Kadane 알고리즘과 꽤 비슷하다.각 노드 $i$마다 $\sum_{i\le k\le j}V_k$가 최대가 되게 하..
