codeforce round #807(div 2) 업솔빙 Codeforces Round #807 개요 하… 진짜 미칠 것 같다 이번엔 A, B를 20분 만에 풀어서 2시간동안 한 문제만 풀어도 3솔의 벽을 깨는 건데… 그걸 못했다. 2시간동안 C,D하나 풀기를…ㅠㅠ 이쯤 되면 이번 방학 목표를 코드포스 3솔로 바꿔야 할 것 같다.(원...

백준 18253번 최단경로와 쿼리 문제풀이 [18253 최단경로와 쿼리] https://www.acmicpc.net/problem/18253 . 쿼리를 한번에 계산하는 테크닉을 배워보자. 처음으로 풀게된 다이아 문제이고 참 좋은 문제라는 생각이 들어서 포스팅한다. 문제상황 파악하기. 문제상황은 간단하다 일단 Naive하게 짠다고 하면 ...

codeforce round #805(div 3), #806(div 4) 업솔빙 Codeforces Round #805, #806 개요 +97점, -10점 했다. 그래도 긍정적인 부분은 이제 코포 유형이 뭔지 감이 잡히고 있다. 코포는 코포로 공부하는게 맞는것같다. 그래도 버추얼은 귀찮아서 안하지만 ㅋㅋㅋ div 4는 ...

에듀 라운드 131 업솔빙 Educational Codeforces Round 131 개요 이쯤 되면 컨디션 문제도 아닌것같다. 내가 그린은 어케 갔었는지도 의문이다.ㅋㅋㅋㅋㅋ 코포는 시간이 생명인데 영어에서 자꾸 절어서 시간이 오래걸리고 여전히 3솔을 못한다.ㅠㅠ 이제부턴 진짜 버추얼이라도 돌아봐야겠다. A. Grass Fi...

백준 1949번 우수 마을 문제풀이 [1949 우수 마을] https://www.acmicpc.net/problem/1949 . 트리에서 dp를 수행한다. 문제상황 파악하기. 정점의 합이 최대여야한다. 고르는 정점들이 인접하면 안된다. 안 고른 정점 옆에는 최소한 한 개는 고른 정점이 있어야한다. 이것도 3번이 낚시인데 ...

백준 3665번 최종 순위 문제풀이 [3665 최종 순위] https://www.acmicpc.net/problem/3665 . 그래프를 모델링하고 BFS 위상 정렬을 한다. 문제상황 파악하기. 작년순위가 모두 주어지고 그 다음에는 올해 등수가 바뀐 팀이 주어진다. 이 때 올해 순위를 확정하여야한다. 1등 부터 자식으로 방향이 ...

Trie 자료구조 이해하기 [5670 휴대폰 자판] https://www.acmicpc.net/problem/5670 . 트라이 자료구조를 이용한다. 문제상황 파악하기. 휴대폰의 자동완성 기능을 사용했을 때 버튼 누르는 횟수를 계산하는 문제이다. 트라이 자료구조를 이용하여 버튼을 누를 때마다 카운트를 해주면 된다. Trie가 뭐길...

merge sort를 이용하여 inversion 개수세기 [1517 버블 소트] https://www.acmicpc.net/problem/1517 . inversion의 개수를 센다. 문제상황 파악하기. 버블소트는 arr[i]>arr[i+1]이면 swap하면서 진행하는 정렬 방법이다. 그리고 이는 당연하게도 O(n^2)이 걸린다....

lazy propagation없이 구간 갱신하기 [16975 수열과 쿼리 21] https://www.acmicpc.net/problem/16975 . lazy propagation없이 segment tree를 이용하여 구간 갱신을 하고 점 쿼리를 해결한다. 문제상황 파악하기. 문제는 구간에다가 k를 더한다. 우리가 알고있는 segme...

3솔의 벽이 너무 높다.. Codeforces Round #801, #802 div2 개요. 벌써 코포를 시작한지 한달 정도가 넘어간다. div2만 들어서면 2솔밖에 못한다.. 3솔의 벽이 너무 높다. 아이디어도 못떠올리는 경우가 대다수이다. “dp 같긴한데…, greedy같긴한데..”생각만하고 못풀 때도 많다. 문제점 잡기가 어렵다...