본문 바로가기

전체 글

 (114)
알고리즘 공부 계획 지난 금요일에 시험이 끝났고, 이번 주말 동안엔 잠깐 쉬는 겸 해서 다이아(정수론+그리디)를 파밍했다. '수(Hard)' 이 녀석을 풀고 싶었지만 도저히 생각이 안 나서 다음에 다시 생각해보기로 했다. 이제 학교를 들어가면 수행 몇 개가 준비되어 있지만, 가볍게 무시해주고 전부터 공부하고 싶었던 알고리즘들을 배워볼 예정이다. 먼저 수개월을 미루고 있는 레이지 프로퍼게이션 구현을 끝내고, 개념 상으로만 알고 있던 MST, PST, HLD 구현을 해볼 것이다. 이러고 시간이 남는다면 최근에 컵이가 세그트리 비츠를 배운 것으로 추정되기 때문에, 관련 강의를 들어보고 싶다. 이쯤에서 상기시키는 올해 목표 : 정올 본선 은상 실패 / NYPC 본선 진출 실패 / 코드포스 퍼플 성공 /// ㅂㅅ...
Bottom-Up Segment Tree 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net #include using namespace std; #define fastio ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) typedef long long ll; struct Segment { vector tree; int n; Segment(int n) : tree(2*n), n(n) {} ll f(ll a,ll b) { return a+b; } void ini..
Diamond III 달성 미련 없을 정도로 풀었다. 랭작의 끝은 언제나 수학인 듯! 남은 10일 동안은 백준을 기억 속에서 지우자. 내 유일한 루비, 제비가 다이아로 강등되어서 아쉽다. 이별 선물로 다3다2를 박아줬다. 대신에 시험 끝나고 'Hey, Better Bettor'을 풀어볼 예정. 내가 하고자 하는 일이 다 잘 풀렸으면 좋겠다. 이 블로그에 오시는 모든 분들을 응원합니다.
Dinic's algorithm 최대 유량 알고리즘의 최종 버전. 구현은 충분히 외울 수 있을 정도로 직관적이다. 시간복잡도: O(V^2E) (라고 하지만 더 빠르다.) 13161번: 분단의 슬픔 첫 번째 줄에는 UCPC 구성원의 수 N(1 ≤ N ≤ 500)이 주어진다. 두 번째 줄에는 N개의 정수가 주어지는데, i번째 수가 1이면 i번 사람은 무조건 A진영에 들어가야 함을, 2라면 무조건 B진영에 들어가야 www.acmicpc.net #include using namespace std; const int V=503; const int s=501; const int t=502; const int INF=2e9; int n; int c[V][V],f[V][V]; vector ad[V]; int lev[V],work[V]; bool ch..
Fenwick Tree 펜윅 트리로 할 수 있는 것: - 점 업데이트, 구간 쿼리 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net #include using namespace std; #define fastio ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) typedef long long ll; struct Fenwick { vector tree; int n; Fenwick(int n) : tree(n+1), n(n) {} void in..

티스토리툴바