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

2024년 5월 1일 (G3)

1. 문제 : Partioning Number (Large)
2. 알고리즘 : 브루트포스
3. 성공 여부 : 실패
4. 풀이 링크 : 작성 예정
5. 복기 : 5월의 시작부터 좋지 않다. 브루트포스, dp 순으로 접근하다가 실패했다. 알고리즘 태그 까보니 브루트포스다. 요즘 랜덤디펜스 계속 실패하네😥 일단 후에 다시 풀어봐야겠다.

2024년 5월 2일 (G4)

1. 문제 : 파스타
2. 알고리즘 : DP
3. 성공 여부 : 56분 (성공)
4. 풀이 링크 : 작성 예정
5. 복기 : 3차원 DP 문제. 2차원 DP로 접근하다가 시간 다 날리고 다시 차근차근 생각해서 겨우 풀어냈다. 갑자기 ps 실력이 떨어진 느낌이 나네 ㅠ 이런 간단한 문제도 실패할 뻔 하다니... 바쁜 일들이 끝나면 ps 좀 해야겠다.

2024년 5월 3일 (G3)

1. 문제 : 그래프 매칭
2. 알고리즘 : DP
3. 성공 여부 : 31분 (성공)
4. 풀이 링크 : 작성 예정
5. 복기 : $N \le 8$인 모든 TC의 답을 구해서, 억지로 규칙성을 찾아 점화식을 세워서 AC를 받았다. 나중에 풀이 작성하면서 증명도 해봐야겠다.

2024년 5월 4일 (G2)

1. 문제 : Driving Lanes
2. 알고리즘 : DP
3. 성공 여부 : 22분 (성공)
4. 풀이 링크 : 작성 예정
5. 복기 : 각 도로가 끝날 때마다 각 차선의 최솟값을 저장하면서 dp를 진행하면 된다. 너무 쉬워서 G5로 기여했다. 그래서 현재 이 문제의 난이도는 G4가 됐다.

2024년 5월 5일 (G1)

1. 문제 : This Too Shall Pass
2. 알고리즘 : 기하학, 선분 교차 판정
3. 성공 여부 : 42분 (성공)
4. 풀이 링크 : 작성 예정
5. 복기 : 처음엔 각 수비수를 중점으로 한 $d$개의 정사각형의 꼭짓점과 중점을 $O_1$과 $O_i$와의 ccw 결과를 판단하는 풀이로 시도했으나 실패. $O_1$과 $O_i$과 중점이 직선상에 있지만 $O_1$과 $O_i$을 잇는 선분이 직사각형을 지나지 않는 TC가 반례가 된다.
   그래서 각 정사각형을 이루는 선분을 모두 저장해서, 각 공격수가 정사각형 내에 있지 않고 공격수를 잇는 선분이 정사각형의 선분과 교차하지 않는지 판단하는 풀이로 AC를 받았다.
   그런데 1틀만 하면 될 것을 무려 6틀이나 했는데, case #1:처럼 #을 넣어서 틀리던지, TC 번호를 나타내는 $t$를 증가시키지 않고 continue 한다던지... 너무 멍청하게 틀려버렸다. 이런 실수 줄여야 하는데, 빨리 끝내려고 다급하게 풀다보니 이렇게 된 것 같다. 다음부터 신중하게 문제를 읽고 풀어야겠다.

2024년 5월 6일 (P5)

1. 문제 : Вышивка жемчугом
2. 알고리즘 : ?
3. 성공 여부 : 실패
4. 풀이 링크 : 작성 예정
5. 복기 : 트리라는 것을 눈치채고, 간선의 개수를 누적 합이나 세그로 접근해서 오일러 지표로 풀면 될 것 같은데 $a$와 $b$의 범위가 너무 크다. 어떻게 풀어야 할까?

2024년 5월 7일 (G1)

1. 문제 : Вышивка жемчугом
2. 알고리즘 : 수학
3. 성공 여부 : 성공 (57분)
4. 풀이 링크 : 작성 예정
5. 복기 : 주어진 범위의 수들은 소인수 개수가 많지가 않아서 모두 소인수 분해를 해놓고, 뒤 인덱스부터 제곱으로 검사하고, 약수들마다 카운트해주는 방식을 사용하면 된다.
   검사는 $A_p \times A_q$의 소인수들로 필요한 소인수들을 채워주고 남은 소인수들을 전부 채워줄 수 있는 수를 찾으면 된다.

2024년 5월 8일 (P5)

1. 문제 : Take a break!
2. 알고리즘 : ?
3. 성공 여부 : 실패
4. 풀이 링크 : 작성 예정
5. 복기 : 이어지는 일들을 한 뭉텅이로 보면, 그 뭉텅이에선 당연히 $d_i$가 큰 값부터 시작해야 함을 직관적을 알 수 있다. 그런데 일의 순서는 바뀔 수 있어서 어떻게 접근해야 할지 도통 떠오르질 않아 실패했다.
   내일부터 밀린 업솔빙 시작해야겠다.

2024년 5월 9일 (G1)

1. 문제 : 바나나나빠나나
2. 알고리즘 : DP
3. 성공 여부 : 실패
4. 풀이 링크 : BOJ 15910 - 바나나나빠나나 풀이
5. 복기 : 누가 봐도 dp긴 한데, DFA를 자세히 보지 않고 혼자 Top-Down DP 짜면서 뻘짓하다가 실패했다 ㅠ...
   그런데 DFA 그림을 dp 식으로 나타내는 발상 자체가 어려운 것 같다. 하지만 눈치채면 구현은 쉬운 그런 느낌. 문제에서 힌트를 주면 조금 더 자세히 보는 습관을 들여야겠다.

2024년 5월 10일 (G2)

1. 문제 : The Maze Makers
2. 알고리즘 : DFS, 구현, 비트마스킹
3. 성공 여부 : 성공 (24분)
4. 풀이 링크 : BOJ 10346 - The Maze Makers 풀이
5. 복기 : 거의 깡구현 문제. 문제 지문 그대로만 구현하면 돼서 크게 어렵지 않았다. 이런 문제는 언제나 땡큐지😋

2024년 5월 11일 (G1)

1. 문제 : 배수관 미스터리
2. 알고리즘 : 분리 집합, 오프라인 쿼리, 정렬
3. 성공 여부 : 성공 (11분)
4. 풀이 링크 : BOJ 26155 - 배수관 미스터리 풀이
5. 복기 : 정말 전형적인 분리 집합 + 오프라인 쿼리 문제다. 딱 보면 바로 풀이법을 알 수 있는 전형적인 문제다. 난 분리 집합 + 오프라인 쿼리 문제의 끝판왕인 Godzilla 문제를 개인적으로 좋아한다. 이 문제의 하하하하하위 호환 문제가 나오면 당연히 땡큐다😋😆

2024년 5월 12일 (P5)

1. 문제 : K-Shaped Figures
2. 알고리즘 : ?
3. 성공 여부 : 실패
4. 풀이 링크 : 작성 예정
5. 복기 : $N^3$을 최소한 $N^2 \log N$으로 줄여야 할 것 같다. 그러면 벡터 같은 것을 정렬해서 조합론을 이용해 한 번에 계산해야 할 것 같은데... 이를 생각해내지 못해 실패했다.
   그래서 풀이를 찾아봤는데 무슨 말인지 도통 이해가 안간다. 일단 나의 접근법의 방향 자체는 맞는 것 같다. 다음에 제대로 풀어봐야겠다.

2024년 5월 13일 (G1)

1. 문제 : Twirling Robot
2. 알고리즘 : 다익스트라
3. 성공 여부 : 성공 (11분)
4. 풀이 링크 : BOJ 4971 - Twirling Robot 풀이
5. 복기 : 위치 뿐만 아니라 다양한 상태를 정점으로 생각해서 진행하는 전형적인 다익스트라 문제다. 쉽게 풀었다.

2024년 5월 14일 (P5)

1. 문제 : Construct a Graph
2. 알고리즘 : 플로이드 워셜, 해 구성
3. 성공 여부 : 성공 (54분)
4. 풀이 링크 : BOJ 31815 - Construct a Graph 풀이
5. 복기 : 처음엔 힙과 그리디로 접근하다가 뭔가 이상함을 느끼고 일단 후퇴. 그리고 잘 생각해보다가 예전에 내가 풀었던 문제인 그래프 복원 문제와 거의 동일하다는 것을 깨닫고 AC를 받았다.
   역시 문제는 많이 풀어보는게 최고다.😎

2024년 5월 15일 (P4)

1. 문제 : Bundling
2. 알고리즘 : 그리디, 트라이, 트리
3. 성공 여부 : 성공 (33분)
4. 풀이 링크 : 작성 예정
5. 복기 : 처음엔 그냥 정렬로 접근하다가 쉽게 반례를 찾았다. 생각을 계속 해봤는데, 맨 앞에서부터 동일한 문자가 없으면 끊긴다(?) 트라이를 만들어서 각 노드마다 접근할 때 카운트를 해준다. 그리고 모든 문자열을 넣고 루트에서부터 dfs를 시작한다. 카운트 나누기 $K$가 $1$ 이상이면 그 문자까지 집합을 카운트 나누기 $K$만큼 집합을 이룰 수 있다는 말이 된다.
   이런 느낌으로 접근해서 AC를 받았다. 그런데 사실 풀이를 쓸 엄두가 나지 않는다. 어떻게 설명해야 할지 감이 안오네🤔

2024년 5월 16일 (P3)

1. 문제 : 해밍 거리와 쿼리
2. 알고리즘 : 비트 집합
3. 성공 여부 : 실패
4. 풀이 링크 : 작성 예정
5. 복기 : 제곱근 분할법으로 접근했는데 TLE를 받는다. 좀 더 빠르게 할 방법이 도저히 떠오르질 않았다. 알고리즘 태그 까보니깐 비트 집합...? bitset을 이용하는 문제 같다. 주 언어가 Python이라 bitset을 잘 모른다...; 다음에 공부해서 다시 풀어봐야겠다.

2024년 5월 17일 (P4)

1. 문제 : Furry Nuisance
2. 알고리즘 : ?
3. 성공 여부 : 실패
4. 풀이 링크 : 작성 예정
5. 복기 : 대충 리프가 4개 이상인 서브 연결 그래프가 있는지 찾는 문제 같다. 맞나...? 문제에서의 몸통을 어떻게 처리?해야 할지 감이 안와서 dfs로 여러 방법을 시도하다가 결국 실패했다.
   사실 문제 지문이 많이 별로인 것 같다. 번역도 그렇고 처음에 몸통이 정확하게 무엇인지 전혀 이해가 가지 않았다. 지문 자체가 모호한 이런 문제는 진짜 별로다.

2024년 5월 18일 (P5)

1. 문제 : 막대 배치
2. 알고리즘 : DP, 수학
3. 성공 여부 : 실패
4. 풀이 링크 : 작성 예정
5. 복기 : 나는 멍청하다. 예전에 이 문제와 거의 같은 문제인 고층 빌딩 문제를 풀었는데 실패했다...; 이런...😥
   그런데 진짜 이런 문제는 자력으로 푸는 사람이 대단한 것 같다.

2024년 5월 19일 (G1)

1. 문제 : Fractions
2. 알고리즘 : 수학
3. 성공 여부 : 성공 (35분)
4. 풀이 링크 : 작성 예정
5. 복기 : $n$이 작은 케이스에서 일일이 계산해보니깐, $i \times j = n$과 $\gcd(i, j) = 1$을 만족하는 $i$, $j$를 찾으면 되는 것 같았다. 그래서 $2 \le i \le\lfloor\sqrt n\rfloor$ 범위에서 $i$, $j$를 찾아, $p \times i + q \times j = n - 1$을 만족하는 $p$, $q$를 찾으면 $100\,000$이 넘지 않게 출력하는 식으로 AC를 받았다.
   사실 증명하고 푼게 아니라서 풀이를 바로 올리려니 쉽지 않다. 나중에 에디토리얼 보면서 다시 배우고 풀이 올려야겠다.

2024년 5월 20일 (P5)

1. 문제 : Twin Buildings
2. 알고리즘 : 정렬
3. 성공 여부 : 실패
4. 풀이 링크 : 작성 예정
5. 복기 : 좌표로 생각해서 $(x_i, y_i)$ 순으로 내림차순 정렬해서 훑어보면, 계산되는 직사각형의 $x$ 좌표는 $x_i$로 고정되고 $y$ 좌표는 지금까지 나온 $y_j(1 \le j < i)$ 좌표 중 최댓값과 $y_i$의 최솟값이 됨을 알 수 있다. 단 이 문제에서 가로 세로를 회전할 수 있는데, 이는 그냥 회전한 좌표와 인덱스를 같이 넣고, 겹치지 않는 인덱스가 있는지 같이 확인하면서 계산하면 된다.
   사실 위와 같은 풀이를 실패하고 깨달았다. 계산되는 직사각형의 한 좌표는 고정됨을 생각해내지 못해 실패했다.

2024년 5월 21일 (G1)

1. 문제 : Bitovni
2. 알고리즘 : ?
3. 성공 여부 : 실패
4. 풀이 링크 : 작성 예정
5. 복기 : 비트가 총 30개인 점을 이용해서 $O(N^2)$을 $O(N)$ 가까이 줄이는 것 같은데, 도저히 풀이가 떠오르지 않는다...; 이게 진짜 G1인가? 맞힌 사람 보니깐 네임드 랭커 4분 뿐...

2024년 5월 22일 (G2)

1. 문제 : Dessert Café
2. 알고리즘 : DFS
3. 성공 여부 : 성공 (20분)
4. 풀이 링크 : BOJ 20171 - Dessert Café 풀이
5. 복기 : 간선의 비용은 함정인 문제. AC를 받은 풀이를 떠올렸을 때, 설마 하면서 코드를 짰다. 이런 발칙(?)한 문제 좋은 것 같다.

2024년 5월 23일 (G1)

1. 문제 : 천국의 계단
2. 알고리즘 : ?
3. 성공 여부 : 실패
4. 풀이 링크 : 작성 예정
5. 복기 : 작성 예정

2024년 5월 24일 (G2)

1. 문제 : 프로젝트 스케줄링
2. 알고리즘 : DP, 위상 정렬
3. 성공 여부 : 성공 (14분)
4. 풀이 링크 : BOJ 14907 - 프로젝트 스케줄링 풀이
5. 복기 : 굉장히 웰논인 DP + 위상 정렬 문제가 걸렸다. 입력 조건이 조금 까다로웠는데, 파이썬이 이럴 때 참 좋다.

2024년 5월 25일 (G1)

1. 문제 : Directed mazes
2. 알고리즘 : BFS, 구현
3. 성공 여부 : 성공 (47분)
4. 풀이 링크 : 작성 예정
5. 복기 : 각 정점을 네 방향으로 쪼개서 BFS를 진행 및 역추적하는 문제. 사실 문제 알고리즘 자체는 어렵지 않으나, 구현이 상당히 헷갈리는 문제다. 오늘 10시간 운전하고 문제 풀다보니깐, 방향을 넘겨받을 때 너무 헷갈려서 실패할까봐 초조했다. 다행히 AC를 받았다.😉

2024년 5월 26일 (P5)

1. 문제 : 푸앙이와 별
2. 알고리즘 : BFS, 해시 맵
3. 성공 여부 : 실패
4. 풀이 링크 : 작성 예정
5. 복기 : 일단 이 문제를 만든 분께 경의를 표한다. 진짜 아이디어 미쳤다...
   $i$번 정점에 대해, (현재 탐색한 모든 정점 수 $tot$) = ($i$번 정점과 연결된, 탐색한 정점 수 $connect_i$) + ($i$번 정점과 연결되지 않은, 탐색한 정점 수 $disconnect_i$)로 나타낼 수 있다. 이 문제는 끊긴 간선이 주어지므로, 그 간선들을 해시 맵과 같은 자료구조로 나타내자. 그리고 $tot$, $disconnect_i$를 관리함과 동시에 $tot \ne disconnect_i$를 만족하는 $i$번 정점을 찾자. 만족하는 $i$번 정점에 대해, 탐색한 정점이 있다는 뜻이므로 $i$번 정점으로 BFS 진행이 가능하게 된다는 뜻이다. 진짜 어려운 문제 같다.

2024년 5월 27일 (G1)

1. 문제 : RGB트리
2. 알고리즘 : DP, 트리
3. 성공 여부 : 성공 (33분)
4. 풀이 링크 : 작성 예정
5. 복기 : 많이 보이는 유형인 트리 DP + 역추적 문제다. 선택할 수 있는 상태가 3개라서 역추적 부분을 어떻게 구현해야 할지 생각하느라 시간을 살짝 소모한 것 같다.

2024년 5월 28일 (P5)

1. 문제 : 과자의 분할
2. 알고리즘 : DP
3. 성공 여부 : 실패
4. 풀이 링크 : 작성 예정
5. 복기 : $dp(i,j)$를 $i$번째 칸을 포함하는 길이 $j$를 만드는 최적값으로 정의해서 푸는 문제다. $i$번째 지점마다 길이를 관리하는 느낌은 바로 떠올렸지만 이를 $O(N^2)$으로 어떻게 줄여야 할지 도무지 떠오르지 않았다. 역시 DP 문제는 무궁무진하고 어렵다.😥

2024년 5월 29일 (G1)

1. 문제 : 객실 배치
2. 알고리즘 : DP
3. 성공 여부 : 성공 (24분)
4. 풀이 링크 : 작성 예정
5. 복기 : 점화식을 정리하다 보면, $dp(i) = dp(i-1) \times 2 + dp(i-2)$임을 알 수 있다. 이는 행렬 DP로 나타내서 풀어내면 된다.
   누가 봐도 dp 문제인데 $N$이 무진장 크다? 그러면 행렬 dp일 확률이 높은 것 같다.

2024년 5월 30일 (P5)

1. 문제 : 볼록 정다각형
2. 알고리즘 : ?
3. 성공 여부 : 실패
4. 풀이 링크 : 작성 예정
5. 복기 : 정다각형에서는 모든 꼭짓점을 지나는 외접원을 찾을 수 있다. 그러므로 세 점의 외심을 찾고, 외심과 세 점이 이루는 각도를 찾는다. 그리고 $R$의 점의 개수는 최대 $1\,000$이므로 브루트포스로 찾는다.
   위 풀이가 내가 생각한 풀이다. 그런데 외심을 구할 때, ZeroDivision을 어떻게 처리해야 할지 생각이 나지 않아 실패했다. 일단 내가 생각한 풀이는 맞으려나...?

2024년 5월 31일 (G1)

1. 문제 : 버스 노선
2. 알고리즘 : 그리디, 트리
3. 성공 여부 : 성공 (8분)
4. 풀이 링크 : 작성 예정
5. 복기 : 트리의 지름이 되는 경로부터 하나씩 충당한다고 생각하면, 결국 리프 정점의 개수를 $n$이라고 할 때 $\lceil \frac{n}{2} \rceil$가 답이 된다.
   풀이 자체는 정말 떠올리기 쉬운데, 증명이 참 어려운 문제 같다.