ps
백준 1199번 - 오일러 회로
https://www.acmicpc.net/problem/1199 1199번: 오일러 회로 첫 줄에는 정점의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 그리고 다음 N개의 줄에 대해 인접행렬의 정보가 주어진다. i+1번째 줄에는 i번 정점에 대한 인접행렬이 주어진다. 두 정점 사이에 간선이 여러 www.acmicpc.net # Approach) 오일러 회로를 구성하는 알고리즘, Hierholzer's Algorithm에 대해 배우는 문제이다. # Logic) Hierholzer's Algorithm을 그대로 적용하자. TLE를 피하기 위하여 본 포스트에서는 인접행렬대신 인접리스트를 이용하여 구현할것이다. 1. 간선의 정보를 저장해준다. 각각의 간선의 정보를 간선의 리스트 edges에 넣어준후, 각 정..
백준 7579번 - 앱
https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net # Approach) 제한 된 두가지의 자원(메모리, 비용)중 하나를 최소화하며 다른 하나를 최대화 해야한다. 고로 Knapsack 알고리즘을 떠올리자. dp배열을 어떻게 잡을지가 이 문제의 포인트이다. $dp[N][M]$ 으로 메모리를 채워가는경우 $O(n) = N \times M = 10^2 \times 10^7 = 10^9$으로 터질 가능성이 있다. 따라서 $ dp[N][sum(c)]$, $sum(..
백준 19565번 - 수열 만들기
https://www.acmicpc.net/problem/19565 19565번: 수열 만들기 문제 지문에 쓰여 있는 조건을 만족하는 가장 긴 수열을 $A$라 하자. 첫째 줄에는 $A$의 길이를 출력한다. 둘째 줄에는 $A$의 원소들을 출력한다. 이러한 수열이 여러 개일 경우 아무거나 출력한다. www.acmicpc.net # Approach) $For$ $1 \leq i < j \leq |A| $, $A_{i} \neq A_{j}$ $\lor A_{i+1} \neq A_{j+1}$ $\iff$ $ \lnot \left(A_{i} = A_{j} \land A_{i+1} = A_{j+1}\right)$ $\iff$ $\lnot \left(\left\{ A_{i}, A_{i+1} \right\} = \lef..
백준 1006번 - 습격자 초라기
https://www.acmicpc.net/problem/1006 1006번: 습격자 초라기 하나의 특수 소대로 인접한 두 영역을 커버할 수 있는 배치는 (2,10), (9,16), (4,5), (7,8), (13,14) 이다. 그리고 나머지 6개 구역은 각각 하나의 특수 소대로 커버할 수 있다. 그러므로 최소 11개 특수 소 www.acmicpc.net # Approach) 타일링문제와 상당히 흡사하다. 고로 DP를 떠올려보자. First Try(Failed) # Definition) $dp[i][j] :$ $min \ value \ when$ $inner \ circle \ is$ $filled \ to \ index \ i$, $and \ outer \ j$ $in[i] :$ $cost \ of \..
백준 및 코드포스
2021/6 - 백준 첫 시작(한달동안 기초문제들만 슬쩍봄) 2021/12 ~ 현재(2022/4/1기준) 백준 5개월, 푼 문제 420개, 플레티넘 2 20점 2021/2/8 codeforces 첫 시험 2021/4/1 기준 contest 9회 참여, 레이팅은 1484... 아직은 푸는 속도와 실수에 발목을 많이 잡히는 것 같다. virtual이 도움이 될까 싶은 마음에 안하고 있었는데 최근에 한번 쳐본 후로 생각이 바뀌어서 앞으로 virtual을 가끔씩 해보려고 한다. 2022/4/10 극심한 슬럼프 요새 문제들이 손에 잡히지 않고 글씨가 둥둥 떠다니는 느낌이다. 실수도 너무 많고, 실수를 한 문제를 디버깅하는게 너무나도 귀찮은 상태다. 대충 머리속으로 알고리즘을 생각한후 TLE가 날 것 같으면 sub..