나만의 백준 랜덤디펜스 기록. 자세한 설명과 규칙은 이 글에서.

2024년 6월 1일 (P5)

1. 문제 : Phonomenal Reviews
2. 알고리즘 : DFS, 트리
3. 성공 여부 : 성공 (50분)
4. 풀이 링크 : 작성 예정
5. 복기 : 쌀국수 가게들과 그 사이에 있는 레스토랑으로 이루어진 트리를 다시 만들고, 그 트리의 지름의 경로는 한 번만 방문 및 나머지 경로는 두 번씩 방문하면 됨을 알아채면 되는 문제다.
   처음엔 트리 DP로 접근했는데, 어느 순간 어디서 잘못됨을 감지했다. 아마 트리의 지름이 되는 쌀국수 가게를 찾는데서 잘못한 것 같다. 그래서 풀이 방향을 살짝 틀어서 AC를 받았다. 재미있는 문제였다.

2024년 6월 2일 (P4)

1. 문제 : 고장난 프린터
2. 알고리즘 : 머지 소트 트리, 세그먼트 트리, 정렬
3. 성공 여부 : 성공 (57분)
4. 풀이 링크 : 작성 예정
5. 복기 : $x_i$에 대해, $[0, min(N, \frac{M}{x_i}) - 1]$ 구간에서 $x_i$보다 작거나 같은 원소의 개수를 구하면 되는 문제다. 사실 문제 자체는 머지 소트 트리만 알면 어렵진 않은데, 일단 파이썬으로는 뚫리지 않는 문제 같고 C++로도 오버플로우 부분을 조심해야 한다. (난 파이썬으로 짰다가 도저히 안뚫려서 C++로 옮겨 적는다고 시간을 많이 낭비했다😥 Python is too heavy)

2024년 6월 3일 (P3)

1. 문제 : 나무 징검다리
2. 알고리즘 : ?
3. 성공 여부 : 실패
4. 풀이 링크 : 작성 예정
5. 복기 : $dp(i, j, k)$를 $i$번째 순서에 $j$번째 장난감을 놓을 때 $k=0$이면 감소, $k=1$이면 증가라고 한다면 가능하면 $1$, 불가능하면 $0$인 식으로 정의해서 $O(n^3)$으로 풀려고 했는데 실패했다. 장난감이 중복되는 것을 어떻게 처리해야 할지 모르겠다.
   어렵다 어려워...😑

2024년 6월 4일 (P4)

1. 문제 : Magical Girl Sayaka-chan
2. 알고리즘 : ?
3. 성공 여부 : 실패
4. 풀이 링크 : 작성 예정
5. 복기 : 다음은 내가 생각한 풀이다.
   주어지는 모든 $K_i$에 대해서는 반드시 합계에 포함되고, 원하는대로 나열을 할 수 있다. 그러므로 $K_i$를 나열했을 때 인덱스가 증가하다가 감소 또는 감소하다가 증가인 경우가 최적이 된다. 그래야 그 사이사이에 포함되는 구간이 최소가 된다. 그래서 주어지는 $K$를 정렬, 구간합을 빠르게 구하기 위해 $S$의 누적합을 미리 구해놓는다. 그리고 정렬된 $K$에 대해 순서대로 반발력을 구하면 되지 않을까 했는데 WA를 받았다. 틀린 이유는 각 음표쌍의 반발력을 구할 때 내림을 하기 때문이다. 그래서 이는 dp로 처리해야 할 것 같은데, 이 부분이 생각이 나지 않아 실패했다.
   dp만 나오면 실패하는 것 같다😥

2024년 6월 5일 (P5)

1. 문제 : 회전 미로 탐색
2. 알고리즘 : ?
3. 성공 여부 : 실패
4. 풀이 링크 : 작성 예정
5. 복기 : $4 \times 4$ 크기의 구역이 $k^2$개 있는 것을 $2k \times 2k$ 크기의 구역이 $4$개 있는 것으로 착각해서 구현해버렸다. 잘못됨을 감지했을 때가 50분 가까이 흐른 상태였고 그렇게 실패했다.
   별다른 알고리즘은 없고 그냥 빡구현 문제다. 다음에 시간이 많이 넉넉할 때 풀어봐야겠다.

2024년 6월 6일 (G1)

1. 문제 : 두 번째 트리의 지름
2. 알고리즘 : DFS, 트리
3. 성공 여부 : 성공 (11분)
4. 풀이 링크 : 작성 예정
5. 복기 : 트리의 지름을 이루는 두 정점을 $u$와 $v$라 한다면, 두 번째 트리의 지름은 반드시 $u$나 $v$가 끝점이 됨을 알아채야 하는 문제다. 직관적으로 바로 알 수 있고 또한 찍어 맞추기도 쉬운 문제이긴 하다만, 엄밀하게 증명하라고 하면 좀 어려운 문제 같다.

2024년 6월 7일 (P5)

1. 문제 : Railway
2. 알고리즘 : 최소 공통 조상, 트리, 희소 배열
3. 성공 여부 : 성공 (18분)
4. 풀이 링크 : 작성 예정
5. 복기 : $r$을 루트로 한 트리에서 $u$와 $v$의 거리는 $d[u] + d[v] - d[lca(u,v)] \times 2$를 만족한다. 이를 이용해서 쿼리를 온라인으로 처리하면 되는 문제다.
   메모리 제한이 $32$ MB라서 좀 당황할 수 있지만, 공간복잡도를 $O(N \log N)$으로 잡으면 충분하다는 것을 알 수 있다.

2024년 6월 8일 (P4)

1. 문제 : Haircut
2. 알고리즘 : 세그먼트 트리
3. 성공 여부 : 성공 (20분)
4. 풀이 링크 : 작성 예정
5. 복기 : Inversion Counting 웰논 문제다. 근데 난 어디선가 많이 본 문제 같은데 하면서 머지 소트 트리 + 누적 합으로 풀었다...🙄 $[0, i-1]$ 구간에서 $A_i$보다 큰 수를 찾아 누적 합 배열 $P_{A_i}$에 개수를 저장하고 누적 합을 계산하면 된다.
   웰논 문제이긴 하지만, 다른 방법으로 풀어냈다는 점만으로도 뿌듯하고 성장했다는 것을 느낀다.

2024년 6월 9일 (P3)

1. 문제 : 토르의 여행
2. 알고리즘 : ?
3. 성공 여부 : 실패
4. 풀이 링크 : 작성 예정
5. 복기 : 풀이를 봐도 매우 어려운 문제다. 대충 요약하면, 각 정점마다 서브트리의 각 정점까지의 경로의 합을 모두 전처리한다. 그리고 각 쿼리마다, 정점 $A$에서 거리가 $D$인 개수 + (정점 $A$의 부모 $P$의 반대 자식 $B$에서 거리가 $D - E_A - E_P$인 개수 + $E_P == E_A$) + $\cdots$가 정답이 된다고 한다.
   이걸 어떻게 cp로 하지...? 너무 어렵다😥

2024년 6월 10일 (P4)

1. 문제 : 로봇 레이스
2. 알고리즘 : ?
3. 성공 여부 : 실패
4. 풀이 링크 : 작성 예정
5. 복기 : 명령의 마지막부터 도착 칸에서 한 칸씩 움직여 본다. 그러면서 민식이와 영식이의 시작 위치까지의 거리를 재는 그런 풀이를 짰는데 실패했다.
   알고리즘 태그를 보니 dp다. 어떻게 점화식을 세워야 할지 도통 감이 오지 않는다.

2024년 6월 11일 (P5)

1. 문제 : 248 게임
2. 알고리즘 : DP
3. 성공 여부 : 실패
4. 풀이 링크 : 작성 예정
5. 복기 : $dp(i, j) = max_{k=i}^{j-1} \left( dp(i, k) + 1 \text{ if } dp(i,k)=dp(k+1,j) \right)$ 점화식을 세워서 $O(N^3)$에 풀어내면 된다. 난 바보같이 분리 집합 + 그리디로 접근해서 시간 다 날려먹고 실패했다. dp 문제는 접근하기가 너무 어렵다 ㅠ

2024년 6월 12일 (G1)

1. 문제 : 동아리방 청소!
2. 알고리즘 : DP
3. 성공 여부 : 성공 (47분)
4. 풀이 링크 : 작성 예정
5. 복기 : 운이 좋게 어제 풀었던 문제와 비슷한 유형인 구간 dp 문제가 걸렸다.
   $dp(i, r)$을 $i$번째 청소를 했을 때 $[1, r]$ 구간의 최적값이라고 정의한다면, $dp(i, r) = min_{l=1}^{r-1}\left(dp(i - 1, l) + A(l + 1, r)\right)$ 점화식을 세울 수 있다. 물론 $A(l,r)$은 $l$번째 날부터 $r$번째 날까지의 누적이다. 이는 전처리하면 된다.
   dp 문제를 이렇게 뚝딱 풀어내니깐 기분이 좋다.

2024년 6월 13일 (P5)

1. 문제 : 광기의 PS
2. 알고리즘 : 그리디, 정렬
3. 성공 여부 : 성공 (24분)
4. 풀이 링크 : 작성 예정
5. 복기 : 4월 랜덤디펜스에 걸렸던 문제인 Energy Stones과 비슷한 유형이다.
   $i$번, $j$번 문제를 비교했을 때, $i$번 문제를 먼저 풀게 됐을 때의 식과 $j$번 문제를 먼저 풀게 됐을 때의 식을 비교해서 $i$번 문제를 먼저 푸는 조건을 부등식으로 나타내면 결국 $T_i \ge T_j$로 정리된다.
   이런 그리디 문제 재밌고 맛있다.😋

2024년 6월 14일 (P4)

1. 문제 : 감시 초소
2. 알고리즘 : ?
3. 성공 여부 : 실패
4. 풀이 링크 : 작성 예정
5. 복기 : $P$가 최대 $100\,000$인 점을 보았을 때, 각 구역이 감시할 수 있는 구역은 많지가 않다. 그래서 투 포인터를 이용해서 $dp(r) = min(dp(r), dp(l-1)+c_m)$ 점화식을 세웠는데 답이 아니었다. 각 구역이 감시할 수 있는 최대 구역을 감시하지 않는 최적값도 있기 때문이다. 이를 어떻게 처리해야 할지 감이 오지 않아 실패했다.🙄

2024년 6월 15일 (P5)

1. 문제 : Lounge Lizards
2. 알고리즘 : LIS, 기하학, 정렬
3. 성공 여부 : 성공 (53분)
4. 풀이 링크 : 작성 예정
5. 복기 : TV를 기준점으로 도마뱀들을 각도로 기준으로 정렬하고, 같은 각도의 도마뱀들을 모아서 LIS의 길이를 구해주면 된다. 생각보다 풀이는 간단하다.
   각도 정렬할 때 파이썬 기준으로 $atan2(X_i - T_X, Y_i - T_Y)$을 기준으로 잡았다. 그래서 오차를 얼마로 잡아야 할까 고민하면서 일단 $10^{-9}$로 잡았는데 AC를 받았다. 오차를 고려한 저격 TC가 없는 것 같다. 아무튼 성공했으니 기분이 좋다!

2024년 6월 16일 (P4)

1. 문제 : Landscaping
2. 알고리즘 : ?
3. 성공 여부 : 실패
4. 풀이 링크 : 작성 예정
5. 복기 : MCMF로 접근했는데 실패했다. 모델링 잘한 것 같은데 왜 안되는지 이유를 전혀 모르겠다;;; 나중에 각 잡고 다시 풀어봐야겠다.

2024년 6월 17일 (P5)

1. 문제 : How I Wonder What You Are!
2. 알고리즘 : 기하학
3. 성공 여부 : 성공 (29분)
4. 풀이 링크 : 작성 예정
5. 복기 : 두 벡터 사이의 각도(라디안)을 구하는 공식인 $acos(\frac {a \cdot b} {|a| \times |b|})$을 알고 있으면 풀 수 있는 문제다. 이 공식이 어려운 기하학 문제를 풀 때 유용하게 계속 쓰여서 외워두는 것이 좋다.

2024년 6월 18일 (P4)

1. 문제 : Yawned-Zoned
2. 알고리즘 : 매개 변수 탐색, 분리 집합, 이분 탐색
3. 성공 여부 : 실패
4. 풀이 링크 : 작성 예정
5. 복기 : $x$를 하품을 하는 학생의 수의 최댓값, $f(x)$를 하품을 하는 학생의 수의 최댓값이 $x$ 이하일 때의 필요한 칸막이의 수라고 정의해서 이분 탐색으로 찾으면 되는 문제이다.
   문제 자체가 신기해서 실패하고 바로 업솔빙했는데, 풀이 찾아보니깐 스택이나 큐로 롤백을 구현하는 분들이 많은데 사실 롤백은 필요없다. $j-1$번째와 $j$번째 열 사이에 칸막이를 둔다면 $j$번째 열의 학생만 다시 위아래로 유파해주고 다시 시작하면 된다.

2024년 6월 19일 (P5)

1. 문제 : 건배
2. 알고리즘 : DP
3. 성공 여부 : 실패
4. 풀이 링크 : 작성 예정
5. 복기 : $dp(l,r) = max\left(dp(l+1,r-1) + (1 \text{ if } A_l = A_r \text{ else } 0), max_{k=1}^{k<r}\left(dp(l,k)+dp(k+1,r)\right)\right)$ 점화식으로 $O(N^3)$에 풀어내면 된다.
   난 멍청하게 $max_{k=1}^{k<r}$ 이 부분을 $max_{k=1}^{k<r-1}$으로 범위를 잡아서 시간 지날 때까지 틀린 이유를 못찾고 끝났다.😑
   여담으로 $N$이 최대 $1\,000$인데 $O(N^3)$으로 의도했거나 뚫리는 이런 문제는 진짜 정말 별로다.

2024년 6월 20일 (G1)

1. 문제 : Musical Chairs
2. 알고리즘 : DP
3. 성공 여부 : 성공 (21분)
4. 풀이 링크 : 작성 예정
5. 복기 : 요세푸스 순열의 마지막 원소만 구하는 문제다. 스몰 케이스를 직접 손으로 계산하고 점화식 끼워 맞추다 보니 AC를 받았다 허허😅 사실 왜 통과했는지 모르겠다.

2024년 6월 21일 (P5)

1. 문제 : 타일 채우기 2
2. 알고리즘 : DP, 수학
3. 성공 여부 : 성공 (50분)
4. 풀이 링크 : 작성 예정
5. 복기 : 점화식을 정리하면 결국 행렬 DP를 사용할 수 있는 선형 점화식이 나온다. 근데 $N$이 대놓고 행렬 dp + 빠른 거듭제곱을 사용해야 하는 범위라서, 풀이를 쉽게 알아챌 수 있는 문제 같다.

• 2024년 6월 22일 ~ 2024년 6월 26일은 이사 일정으로 쉬어갑니다.

2024년 6월 27일 (P4)

1. 문제 : Races
2. 알고리즘 : ?
3. 성공 여부 : 실패
4. 풀이 링크 : 작성 예정
5. 복기 : Point가 가장 많은 하나의 경로를 찾아서 Point의 개수의 반이 정답이 되는 것 같다. 그래서 트리 DP로 접근해서 (현재 정점에서의 두 자식으로의 경로) or (루트에서 현재 정점의 한 자식으로의 경로)를 계산했는데 WA를 받았다. 뭐가 문제인지 전혀 모르겠다.😥 요 근래 이사한다고 컨디션이 정상이 아니다 후...

• 2024년 6월 28일은 이사 일정으로 쉬어갑니다.

2024년 6월 29일 (P5)

1. 문제 : Festival
2. 알고리즘 : DP, 비트마스킹, 정렬
3. 성공 여부 : 성공 (53분)
4. 풀이 링크 : 작성 예정
5. 복기 : 비트필드를 이용한 dp 문제다. $O(N \times 2^M)$으로 dp 테이블을 채워가면 된다.
   처음엔 비트 dp라는 것을 바로 눈치채지 못하고 유량이랑 그리디로 접근했다. 그러다가 $N$과 $M$이 상당히 작으며, 모든 $i(0\le i < N)$가 선택되어야 한다는 것에서 풀이를 알아냈다.

2024년 6월 30일 (P4)

1. 문제 : 반복 패턴
2. 알고리즘 : KMP
3. 성공 여부 : 실패
4. 풀이 링크 : 작성 예정
5. 복기 : 실패 함수를 이용하는 문제다. 난 실패 함수 $pi$의 마지막 원소나 모든 원소를 이용했는데 그게 아니었다. $f(f(f( \dots$ 와 같이 prefix, suffix를 동시에 만족하는 문자열의 길이를 전부 찾아야 하는 것이다.
   그래도 좀 자신있어 하는 알고리즘인 KMP를 사용하는 문제에서 틀리다니 아깝고 바보같다😥