본문 바로가기

전체 글

 (175)
2021 KOI 대비 DAY-1 오랜만에 글을 쓴다. 지난 일주일 동안 열심히 노느라 PS에도, 블로그에도 조금 소홀했다. 저녁시간에 축구 또는 농구를 하고 조기 입실을 한 다음, 라면과 컵밥을 먹고 게임을 하다가 11시 조금 넘어서 올라오는 웹툰을 보면서 잠드는 행복한 일상의 반복이었다. 물론 PS를 완전 놓지는 않았다! 레이지 세그 구현체를 만들려고 보니 전부 탑다운 세그 트리를 이용하길래 탑다운 세그 트리 구현체를 먼저 만들려고 시도했지만, 마음에 드는 구현체를 만들기가 쉽지 않아 포기했을 뿐이다. (struct에 나름 최적화가 되어있으면서도 직관적으로 이해 가능한 그런 구현체가 있다면 공유 부탁드립니다 ㅠ) 정신을 차리고 보니 KOI 예선이 2주 앞으로 다가와서 정말 대비를 해야겠다고 생각하던 차에, 북곽 선생님들께서 졸업하신 ..
알고리즘 공부 계획 지난 금요일에 시험이 끝났고, 이번 주말 동안엔 잠깐 쉬는 겸 해서 다이아(정수론+그리디)를 파밍했다. '수(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..

티스토리툴바