분할정복을 이용한 다이나믹 프로그래밍 최적화 목적과 조건 목적 $O(KN^2)$ 의 알고리즘을 $O(KNlogN)$으로 시간복잡도를 줄이기 위함 조건 1. DP 점화식 $dp[i][j] = min_{k<i}(dp[i-1][k] + C[k][j])$ 2. C의 조건 $C[i][j]$ 는 Monge array이거나 최적해의 단조성이 ...

코드포스 다시 열심히! 블로그도 열심히! 개요 본케도 블루에 올려놨지만 맨날 민트로 다시 떨어진다. 항상 잘보면 1700언저리 못보면 1500 정도 나와서 딱 민트 상위 블루 하위가 지금 나의 퍼포먼스라고 생각하면 될 듯하다. 하지만 나는 더 잘하고 싶다. 지금까지 귀찮아서 버추얼과 업솔빙을 소홀히 했는데 지금이라도 열심히 해보려한다. 목표는 정규라...

rust 공부시작! 개요 C, C++, python을 할줄 알지만 뭔가 다른 사람들과의 차별점을 두고 싶어서 하나만 더 배워보고 싶었다. rust는 백준 사이트에서 보면 굉장히 빠르다. 또한 보안에도 좋다고 들었다. 그런것도 있지만 희소성도 있는 것 같아서 공부를 해보려고 한다. 여기서는 출력, 입력, 자료형 등 기본적인 문법을 정리해보겠다....

코드포스 블루 달성 후기 드디어 달성!! 1년 가까이 코드포스를 한 것 같다. 중간에 코드포스를 쉰 적도 있었지만 백준을 풀면서도 꼭 블루로 올리고 싶다고 생각을 했었다. 내가 올린 과정과 방법, 그리고 앞으로 어떻게 공부하는 것이 좋은지 글로 남기려고 한다. 내가 고생한 만큼까지 고생하지 않도록 내 글을 읽는 누군가가 도움이 되었으면 한다. ...

여름캠프 및 SUAPC 후기 개요 뭔가 엄청나게 오랜만의 포스팅이다. 이 글의 주인공은 이번 방학동안 참여한 알고리즘 캠프이다. 나는 지난 3학기동안 꾸준히 신촌엽합의 캠프를 들었고 suapc는 2학기동안 참여했다. 하지만 후기를 쓰는 것은 처음이다. 항상 이 캠프가 끝나면 학기가 시작되니 귀찮음을 이겨내지 못했던 것이다. 이번엔 꽤나 만족...

2023-05-25-Edu Codeforce round 149 (Div.2) 개요 디비전 2는 솔직히 4문제는 풀어야 본전이다. 나도 옛날엔 인정하지 않았지만 A == 브론즈, B== 실버하위, C == 실버 상위, D == 골드 수준의 문제들이 출제 되기 때문이다. (물론 편차가 있긴하지만) 예전에는 내가 C, D를 자주 못풀었기 때문에 D가...

2023-05-13-Edu Codeforce round 148 (Div.2) 개요 에듀라운드가 어려운건지…. 에듀라운드는 블루퍼포 이상을 맞아본적이 없는 것 같다. 솔직히 그렇게 큰 차이는 없는데 왜 그러는지는 도저히 모르겠다. 이번 셋은 C까지 매우쉽고 D부터는 좀 어려웠다.. D는 감은 잡았는데 뭔가 구현이 막막해서 못풀었다. (이런 문...

HLD(Heavy Light Decomposition) 💡 트리에서 임의의 두 정점을 잇는 경로에 대한 쿼리가 궁금할 때. 구현과정 구현과정은 jinhan님의 블로그 를 참고하여 구현했다. 가중치가 있는 그래프라면 adj에 가중치 없는 그래프를 만들고, cost[정점]에 해당 정점으로 갈 때 드는 비용을 저장한다. 그리고 input[...

행렬 거듭 제곱 💡 DP 점화식이 선형 방정식인 경우 $ a_n = \sum_{k=1}^{m}{c_k*a_{n-k}} $ 위와 같은 형태의 점화식일 때 $O(m^3log(n))$ 에 n번째 항을 구할 수 있다. 분할정복을 이용한 행렬 거듭제곱 $O(log(n))$ 예를 들어 피보나치 수를 생각해보자 [\begin{bmatrix} F_2...

2023-05-02-It takes two 개요 최근엔 몸이 바빠져서 그런지 게임을 많이 못했다. 바빠진 이유는 역시 학교를 가면서, 알바도 하면서, 연애도 하기 때문일 것이다. 그래도 게임만 하던 작년보단 더 생산적인 것 같기도하다. It takes two는 내가 스토리가 예쁜 게임을 좋아하다보니 수민이와 꼭 같이 하고 싶은 게임이였다. ...