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같긴한데..”생각만하고 못풀 때도 많다. 문제점 잡기가 어렵다...

백준 11505 구간 곱 구하기 문제풀이 [11505 구간 곱 구하기] https://www.acmicpc.net/problem/11505 . segment tree를 이용하여 빠르게 구간 곱을 변경하고 출력한다. 문제상황 파악하기. [2042 구간 합 구하기] https://www.acmicpc.net/problem/2042 . 위 ...

코드포스 폭망기념 upsolving Codeforces Round #800 Editorial 개요. 코드포스를 시작하고 그래도 계속 그린 퍼포먼스는 나오길래 답만 보고 넘겼었다. 그런데 이번 코포에서 정말 단 한문제도 못풀었다… 그래서 분노의 업솔빙을 해보려고 한다. ㅠㅠ 백준 플레가 코포 뉴비에서 헤매고 있다니 정말 분하고 부끄럽다. ...

백준 1305 광고 문제풀이 [1305 광고] https://www.acmicpc.net/problem/1305 . KMP알고리즘 base의 failure function을 이용해서 문제의 답을 구한다. 문제상황 파악하기. 광고 문구가 될 수 있는 것중 가장 짧은 광고문구를 찾는 문제이다 . 광고가 될수 있는 문구 1글자, 2글자, 3글...

백준 4386 별자리 만들기 문제풀이 [4386 별자리 만들기] https://www.acmicpc.net/problem/4386 . 간선을 추려서 MST(minimum spanning tree)를 만든다. 문제상황 파악하기. 정점들의 위치가 주어지고 이동은 어디든 할 수 있다 . 이동 할때 그 거리는 점과 점사이의 거리이다. 모...

백준 4803 트리 [4803 트리] https://www.acmicpc.net/problem/4803 . 상호 배타적 집합(disjoint set)을 이용하여 트리인지 아닌지 판단한다. 문제상황 파악하기. 정점을 잇는 간선이 주어진다 . 이 그래프는 서로 떨어져있는 그래프일 수도 있고 사이클이 있을 수도 있다. 즉 떨어져 있는 그래프...

백준 2206 벽 부수고 이동하기 문제풀이 [2206 벽 부수고 이동하기] https://www.acmicpc.net/problem/2206 . BFS로 최단거리를 탐색한다. 문제상황 파악하기. 전형적인 그래프 탐색 문제처럼 보인다. 최단거리를 구해야하므로 DFS가 아닌 * BFS(너비우선 탐색) 으로 풀어야한다. 문제는 벽을 한번만 부술...

백준 2166 다각형의 면적 문제풀이 [2166 다각형의 면적] https://www.acmicpc.net/problem/2166 . 신발끈 공식을 이용하여 다각형의 면적을 구해보자 문제상황 파악하기. 점들로 구성된 다각형의 넓이를 구하는 문제로 신발끈 공식을 이용하여 구할 수 있다. 점의 최대 좌표는 100000이고 그렇다면 면적을 구할 ...