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

2024년 4월 1일 (G1)

1. 문제 : Martian Pits
2. 알고리즘 : BFS, 구현
3. 성공 여부 : 성공 (55분)
4. 풀이 링크 : BOJ 5120 - Martian Pits 풀이
5. 복기 : 전형적인, 상태가 많은 BFS 문제다. 그래서 아이디어는 어렵지 않게 바로 떠올려서 코드를 짰지만, 생각보다 신경 쓸 부분이 많아서 정리가 잘 되지 않고 복잡했다. 이렇게 발상하는 능력보다 구현하는 능력이 중요한 문제도 중요한 것 같다. 내 타이핑이나 생각을 정리하는 시간이 조금만 늦어졌어도 실패했을 것이다.

2024년 4월 2일 (P5)

1. 문제 : Maximal Area
2. 알고리즘 : 분할 정복, 세그먼트 트리, 스택
3. 성공 여부 : 성공 (10분)
4. 풀이 링크 : BOJ 11861 - Maximal Area 풀이
5. 복기 : 히스토그램 문제와 $N$ 제한만 다르고 완전히 똑같은 문제다. 문제 운이 좋았다.
   dnc + segtree는 바로 생각이 났지만, 스택 풀이는 바로 생각이 나지 않았다. 그래서 풀이 글 적을 때 다시 스택 풀이법을 공부하게 되었다. 이제 잊지 말아야지.

2024년 4월 3일 (P4)

1. 문제 : Prehistoric Programs
2. 알고리즘 : 그리디, 정렬
3. 성공 여부 : 실패
4. 풀이 링크 : BOJ 26137 - Prehistoric Programs 풀이
5. 복기 : 각 문자열이 사용되기 위한 조건까지 파악했는데, 앞쪽과 뒤쪽을 나눠서 살펴볼 생각을 하지 못해 결국 틀렸다. 결국 그리디 접근법을 파악하지 못한 것이다. 역시 난 그리디에 약한 것 같다.
   그리고 이 문제 꽤 간단한 문제인데 증명이 어려운 그런 깔끔한 문제로 느껴졌는데, 알고 보니깐 꽤 웰논 문제인 것 같았다. 문제 로직 자체가 대회에 여러 번 출제된 것 같았다. 역시 실력도 실력이지만 깡으로 문제 많이 풀기도 중요한 것 같다.

2024년 4월 4일 (P5)

1. 문제 : 교수님 서운해 잉잉
2. 알고리즘 : DP
3. 성공 여부 : 성공 (58분)
4. 풀이 링크 : BOJ 25967 - 교수님 서운해 잉잉 풀이
5. 복기 : 점화식은 되게 빨리 세웠는데 의문의 맞왜틀을 계속 받았다. 알고 보니깐 문자의 위치를 잘못 계산했다... 하... 😑
   그런데 위치 다시 계산하니깐 TLE를 받기 시작했는데, 잘 생각해보니깐 거리 구할 때의 제곱 연산이 1억번 이상 연산하면 터질 것 같아서 거리 전처리해서 제출하니깐 AC를 받았다. 자칫하면 속상하게 실패할 뻔 했잖아...

2024년 4월 5일 (P4)

1. 문제 : Vrsta
2. 알고리즘 : 세그먼트 트리, 오프라인 쿼리, 좌표 압축
3. 성공 여부 : 성공 (16분)
4. 풀이 링크 : BOJ 27551 - Vrsta 풀이
5. 복기 : 웰-논 문제가 걸렸다. 카운팅 배열을 세그먼트 트리로 나타내서 원하는 인덱스를 이분 탐색 느낌으로 찾는 문제인데, 대표적으로 중앙값과 사탕상자 문제가 있다. Vrsta 문제는 좌표 압축 기법만 추가된 문제이다. 그래서 무난하게 풀어버렸다.
   난이도가 플래로 올라오니깐, 자체 난이도가 높은 알고리즘들의 기본 문제가 잘 걸리는 것 같다. 덕분에 P3까지 올라가지만, 이게 공부가 되긴 하겠지...?

2024년 4월 6일 (P3)

1. 문제 : Free Willy
2. 알고리즘 : 양방향 탐색, 해시 맵
3. 성공 여부 : 실패
4. 풀이 링크 : BOJ 11106 - Free Willy 풀이
5. 복기 : DP, BFS 모두 접근해봐도 풀리질 않았다. 어떻게 보면 문자열이 나타날 수 있는 상태의 최대 개수는 $N!$이니깐 당연히 불가능하긴 하다. 결국 못풀고 알고리즘 태그를 보니 양방향 탐색이라는 처음 보는 알고리즘이었다. 그래서 부랴부랴 공부하고 풀어보니깐 신기하게도 시간 제한이 널널하게 뚫렸다. 정말 신기한 알고리즘인 것 같다.
   대충 설명하면 분기 수 $b$, 정답 $d$일 때, 시작점에서 탐색을 시작하면 지나가는 상태는 최대 $b^d$개인데, 시작점과 도착점에서 동시에 탐색을 시작하면 지나가는 상태를 $b^{d/2}$개로 줄일 수 있게 된다. 앞으로 자주 써먹을 것 같다. 이걸로 문제도 내봐야겠다

2024년 4월 7일 (P4)

1. 문제 : Multiplication Game
2. 알고리즘 : 게임 이론, 수학
3. 성공 여부 : 성공 (18분)
4. 풀이 링크 : BOJ 15724 - Multiplication Game 링크
5. 복기 : 결론부터 말하자면 P4에 있을만한 문제는 아닌 것 같다. 난이도에 비해 훨씬 더 쉽게 느껴진다. 일단 핵심 TC가 예제에 전부 나와 있다. 당연히 소인수의 개수가 하나인 경우는 생각하기 쉽고. 너무 쉽게 코드가 짜져서, 혹시나 예제에 나와있지 않은 엣지 케이스가 있나 찾아본다고 10분 정도 버린 것 같다. 도저히 찾아지지 않아서 그냥 제출해봤는데 AC.
   게임 이론 자체가 높은 평가를 받긴 하지만, 같은 P4인 게임 이론 문제에 비해서 현저히 쉬운 것 같다. 그래서 난이도 P5로 기여해서 현재 P5로 내려갔다.

2024년 4월 8일 (P3)

1. 문제 : Cebula
2. 알고리즘 : 기하학, 볼록 껍질
3. 성공 여부 : 성공 (26분)
4. 풀이 링크 : BOJ 7949 - Cebula 링크
5. 복기 : 가장 높고 넓은 성 문제, 감옥 건설 문제와 거의 동일한 문제. 다른 점은 collinear한 경우도 볼록 껍질에 포함이라는 점인데, 솔직히 이 점이 2254, 17403 난이도인 P4에 +1을 줄 정도로 유의미한 영향을 주지 않는 것 같다. 그냥 hull을 구성하는 연속하는 세 점이 ccw 값이 양수인 것이 하나라도 있는지만 검사하면 되는 걸...?
   아 그런데 지문이 좀 별로다. 폴란드어로 되어 있는 문제라 그런지 번역기를 돌려도 깔끔하게 번역이 되지 않는다. hull을 만들고 남은 점들을 어떻게 처리하는지가 모호하게 적혀 있는데, 이것 때문에 몇번 틀렸다. 그래서 정답 비율이 22.917% 밖에 안되겠지...;;

2024년 4월 9일 (P2)

1. 문제 : Repetitive String Invention
2. 알고리즘 : ?
3. 성공 여부 : 실패
4. 풀이 링크 : 작성 예정
5. 복기 : 느낌이 LCP 배열인데 난 아직 LCP 배열을 공부하지 않았다. 그래서 일단 스위핑 + 조합론 느낌으로 접근하려고 했는데, 잘 찾아지지 않았다. 요즘 너무 바빠서 피곤한 탓에 하품도 계속 하고... 그래서 그냥 LCP 배열을 공부하고 업솔빙 각이다 싶어서 30분 째에 포기하고 알고리즘 태그 깠는데 누적 합...?😶 허허... 이걸 어떻게 누적 합으로 풀지...? 일단 오늘은 취침하고 내일이나 한번 다시 풀어봐야겠다.

2024년 4월 10일 (P3)

1. 문제 : 인재야 머쉬맘 잡았어?
2. 알고리즘 : 그리디, 브루트포스
3. 성공 여부 : 실패
4. 풀이 링크 : BOJ 17221 - 인재야 머쉬맘 잡았어? 풀이
5. 복기 : 일단 아직 못풀었다. 나중에 업솔빙 예정. 일단 내가 생각했을 때엔, 반격한 다음 버프를 쓰는 것이 최적일 것이다. 증가량은 퍼센트지만 감소량은 수치이기 때문에, 최대한 체력을 증가시킨 다음, 버프를 최대한 쓰는 것이 이득이다. 그래서 반격 $i$번, 버프 $j$번으로 브루트포싱했는데 틀린다... 뭐가 문제일까?
   (2024.04.12 추가) AC를 받았다. 난 체력이 올라가지 않으면 '반격 몇번 후 공격'은 고려하지 않고, 반격으로만 or 공격으로만 고려했는데 반례가 있었다. 바로 1 2 5 1. 반격 $3$번 후 공격 $1$번이 정답이다. 그리고 버프를 사용할 수 없는 상태일 때, '반격 $i$번 후 공격'을 고려해야 했는데, 그냥 넘어가버렸다.
   생각해보면 이 문제는 정말 고려해야 하는 부분이 많은 문제 같다. 되게 좋은 문제라고 생각이 든다. 공부 잘하고 갑니다!

2024년 4월 11일 (P4)

1. 문제 : Vampiros
2. 알고리즘 : DP, 수학
3. 성공 여부 : 실패
4. 풀이 링크 : BOJ 13686 - Vampiros 풀이
5. 복기 : 연속 3번으로 태그 까도 풀이를 모르겠는 문제 걸려서 당혹스럽다... 일단 이 문제도 업솔빙 예정
   (2024.04.18 추가) 며칠동안 못풀고 끙끙 앓다가, 오늘 씻는데 갑자기 메모리 최적화할 방법이 떠올라서 그 방법으로 다시 시도했더니 AC를 받았다.
   $300$번 반복했더니 WA를 받고, $500$번 넘어가면 MLE를 받고, 이게 무슨 저울질인가 싶었다. 그런데 지금 다시 생각해보니 정말 나는 바보였다. 아무튼 내가 자신없어 하는 DP, 수학 문제를 결국 혼자 힘으로 풀어낸 것이 뿌듯하다.

2024년 4월 12일 (P5)

1. 문제 : 우주비행사 정민
2. 알고리즘 : BFS, 구현
3. 성공 여부 : 실패
4. 풀이 링크 : BOJ 30055 - 우주비행사 정민 풀이
5. 복기 : 차원 이동을 차원 $2$에서 차원 $1$로 이용할 수 있는지 몰랐다. 진짜 이 점 때문에 계속 맞왜틀해서 실패했다. 실패하고나서 질문 게시판에 반례보고 차원 이동을 차원 $2$에서 차원 $1$로 이용할 수 있게끔 코드 5줄 추가하니깐 AC 받았다. 하... 진짜 스트레스😶
   지문이 길어서 그런지, 차원 이동의 방향을 당연히 단방향이라고 착각해버렸다. 여기서 나의 문제점인 '지문 제대로 안읽기'가 드러나는 것이지 뭐 ㅠ
   지문에서 차원 $2$에서 차원 $1$로 오는 예시 하나만이라도 넣어줬으면 좋았을 것 같다... 안그래도 지문이 너무 길어서 한눈에 다 들어오지도 않는데 떼잉😑

2024년 4월 13일 (G1)

1. 문제 : 병아리의 변신은 무죄
2. 알고리즘 : DP, 수학
3. 성공 여부 : 성공 (20분)
4. 풀이 링크 : BOJ 16467 - 병아리의 변신은 무죄 풀이
5. 복기 : 2024년 3월 랜덤디펜스에서 28일에 풀었던 리그 오브 레전설 (Large)와 $99\%$ 동일한 문제다. 이때, 실패하면서 '1차원 선형 점화식은 행렬 곱으로 나타낼 수 있다.'가 머릿속에 똑똑히 각인이 된 것 같다. 문제를 보는 순간 바로 풀이가 떠올랐다. 😄

2024년 4월 14일 (P5)

1. 문제 : 초직사각형
2. 알고리즘 : 그리디, 수학, 정렬
3. 성공 여부 : 성공 (49분)
4. 풀이 링크 : BOJ 21761 - 초직사각형 풀이
5. 복기 : 각각 $A$, $B$, $C$, $D$인 카드 더미에서 각각 가장 낮은 값을 뽑아서 비교해봐야 하는 것은 직관적으로 알 수 있었다. 하지만 $(a - A_{min})bcd$, $a(b - B_{min})cd$, $\dots$ 이렇게 비교하는 방법은, 각 합이 최대 $200\,000\,000\,000$가 될 수 있기 때문에 TLE는 물론, 오버플로우 문제도 생긴다. 그래서 변수를 잘 쪼개면 $A$와 $B$에 대해선 $(a - A_{min})bcd \le a(b - B_{min})cd = (a - A_{min})b \le a(b - B_{min})$임을 이용해서 풀어냈다.
   사실 처음엔 $abc$, $abd$, $acd$, $bcd$를 구해놓고 비교하는 느낌으로 접근했는데 TLE를 받고 변수를 더 쪼갠 다음 많은 조건 분기 느낌으로 구현을 시도했다. 그런데 코드가 너무 길어져서 생각해보니 최대 3번($(a,b)$, $(Choice_{prev},c)$, $(Choice_{prev},d)$)만 비교하면 되는 것을 깨닫고 AC를 받았다.
   구현할 부분?이 생각보다 많아서 AC를 받는 시간이 늦어졌다. 타이핑 연습이라도 해야 하나...?

2024년 4월 15일 (P4)

1. 문제 : Justice Served
2. 알고리즘 : ?
3. 성공 여부 : 실패
4. 풀이 링크 : 작성 예정
5. 복기 : 일단 사람을 정점으로 생각한다면 그래프의 형태는 DAG가 된다. 그래서 스택을 이용해서 그래프를 만든 다음에 가상 루트에서의 거리 - 1이 답인 줄 알았다만... WA를 받고 바로 반례를 찾았다. 그래서 세그먼트 트리로 접근해서 완전히 포함하는 구간의 개수가 답인 줄 알았는데 예제 1번에서 틀렸다. 그러다가 시간이 다 돼서 실패했다. 업솔빙 해야겠다. 😥

2024년 4월 16일 (P5)

1. 문제 : Blurred Pictures
2. 알고리즘 : 이분 탐색
3. 성공 여부 : 성공 (41분)
4. 풀이 링크 : BOJ 17555 - Blurred Pictures 풀이
5. 복기 : 처음에 14줄 코드 제출했는데 WA가 떴다. 이유는 $a_i$를 왼쪽 위 꼭짓점으로 삼는 정사각형만 고려해서였다. 그래서 $a_i$를 왼쪽 위, 아래 꼭짓점으로 삼는 정사각형 2개, $b_i$를 오른쪽 위, 아래 꼭짓점으로 삼는 정사각형 2개를 고려하는 코드로 다시 짜니깐 AC를 받았다.
   보통 알고리즘이 단순하면 발상이 어려운데, 이 문제는 알고리즘도 발상도 쉬워서 알고리즘 태그를 보니깐 세그가 있었다. 굳이...? 🙄
   아무튼 사람들이 P5라고 하는 문제를 복잡하지 않고 쉽게 풀어내서 뿌듯하다.

2024년 4월 17일 (P4)

1. 문제 : 호텔예약
2. 알고리즘 : DP
3. 성공 여부 : 실패
4. 풀이 링크 : 작성 예정
5. 복기 : $dp(r, m, f, c)$를 $r$번째 방까지 고려했을 때, $c$ 쌍의 커플을 포함한 $m$명의 남자, $f$명의 여자한테 방을 나누어 주었을 때의 최적값이라 잡고, 냅색 dp로 풀어내면 되는 것 같은데... 메모리 제한 $128$ MB가 발목을 잡는다. 어떻게 풀어야 할까?

2024년 4월 18일 (P5)

1. 문제 : Mike Sees The Storm (Small)
2. 알고리즘 : DP, 수학
3. 성공 여부 : 실패
4. 풀이 링크 : 작성 예정
5. 복기 : 젠장 또 DP + 수학 문제야...😤 요즘 할 일이 너무 많아서 일단 업솔빙은 나중에... 밀린 문제가 너무 많다 ㅠ

2024년 4월 19일 (G1)

1. 문제 : 배열 정렬
2. 알고리즘 : 다익스트라, 해시 맵
3. 성공 여부 : 성공 (13분)
4. 풀이 링크 : BOJ 28707 - 배열 정렬 풀이
5. 복기 : 배열을 하나의 노드로 생각해서 다익스트라로 풀어내는 문제다. 솔직히 이 문제가 왜 G1까지 올라왔는지 모르겠다. 배열 자체를 해시 맵의 키로 한다는 발상이 그렇게 어렵지도 않은 것 같은데...🤔

2024년 4월 20일 (P5)

1. 문제 : Delete the Points
2. 알고리즘 : ?
3. 성공 여부 : 실패
4. 풀이 링크 : 작성 예정
5. 복기 : 거리가 가까운 두 점부터 처리하면 될 것 같은데 잘 안된다. 무엇이 문제일까?

2024년 4월 21일 (G1)

1. 문제 : 손은 컴퓨터보다 빠르다
2. 알고리즘 : 애드혹, 해 구성
3. 성공 여부 : 실패
4. 풀이 링크 : BOJ 13313 - 손은 컴퓨터보다 빠르다 풀이
5. 복기 : 최대한 초기 정점을 다시 색칠하러 되돌아오게끔 그래프를 짜야 할 것 같은데... 쉽지 않았다. 업솔빙 예정
   (2024.05.09 추가) 공식 에디토리얼을 보고 참고해서 나만의 그래프를 짜보았다. 이런 문제는 쉽지 않은 것 같다.

2024년 4월 22일 (G2)

1. 문제 : 평균값 수열
2. 알고리즘 : 수학, 애드혹
3. 성공 여부 : 성공 (26분)
4. 풀이 링크 : BOJ 5485 - 평균값 수열 풀이
5. 복기 : 처음엔 단순히 인접한 두 원소의 차이를 구해 그 중 최솟값에 $1$을 더한 값이 답인 줄 알았으나, WA를 받고 반례를 찾았다. 그리고 범위를 줄여나가는? 그런 방식을 택해 AC를 받았다. 사실 직관적으로 범위의 최소와 최대가 뒤집히면서? 진행되는 것은 쉽게 알 수 있다. 왜냐면 두 범위에서 선택한 두 수의 특정 수까지의 거리가 같아야 하기 때문이다. 평균이기 때문. 그런데 이를 풀이로 적어내는 것이 더 어려웠다. 이런 문제는 증명 같은 것을 어떻게 해야 하나 싶다.

2024년 4월 23일 (G1)

1. 문제 : Fastest Route
2. 알고리즘 : DP, 비트마스킹
3. 성공 여부 : 성공 (10분)
4. 풀이 링크 : BOJ 22526 - Fastest Route 풀이
5. 복기 : 현재 클리어한 스테이지를 비트로 나타내서 진행하는 간단한 bit dp 문제가 걸렸다. 이런 유형의 문제는 거의 $N$이 매우 작다. $2^N$을 배열로 나타낼 수 있는 크기 그리고 최단거리 느낌이면 웬만하면 bit dp다. 난 개인적으로 외판원 순회 알고리즘을 굉장히 좋아하기 때문에, 이런 유형의 문제는 웬만하면 쉽게 풀 수 있는 것 같다. 😎

2024년 4월 24일 (P5)

1. 문제 : Arithmetic Progressions
2. 알고리즘 : 브루트포스, 이분 탐색, 정렬
3. 성공 여부 : 성공 (20분)
4. 풀이 링크 : BOJ 16740 - Arithmetic Progressions 풀이
5. 복기 : $n$이 작고 모든 원소가 서로 다르다길래 두 포인터 느낌으로 브루트포스 + 이분 탐색으로 시도하니깐 AC를 받았다. 너무 쉬워서 알고리즘 태그를 보니깐 dp가 찍혀있네...? 어림도 없지. 바로 난이도 G3 줬다. 플래 급은 절대 아닌 듯 하다. 결국 현재 이 문제는 G1로 내려갔다.

2024년 4월 25일 (P4)

1. 문제 : Energy Stones
2. 알고리즘 : DP, 그리디, 정렬
3. 성공 여부 : 실패
4. 풀이 링크 : BOJ 23933 - Energy Stones 풀이
5. 복기 : 처음엔 냅색 dp로 접근하다가 도저히 안풀려서 혹시나 해서 그리디로 접근했는데 역시 안됐다. 실패하고 풀이 찾아봤는데 그리디 + 냅색 dp...?
   그리디와 냅색 dp가 합쳐질 수 있다는 것을 처음 알았다. 그리고 뭔가 이런 유형의 문제는 그들만의 웰-논 문제인 듯 하다. 꼭 알아놔야겠다.

2024년 4월 26일 (P5)

1. 문제 : 직각 다각형
2. 알고리즘 : 기하학, 정렬
3. 성공 여부 : 성공 (56분)
4. 풀이 링크 : BOJ 3442 - 직각 다각형 풀이
5. 복기 : 처음에 바보같이 백트래킹으로 접근하다가 TLE 받았다. 그리고 다음과 같이 핵심을 찾아내서 아슬아슬하게 AC를 받았다. 뿌듯하다.
   • 방향이 정해진 점이 존재한다. 예를 들어, 가장 왼쪽 아래점에서부터는 반드시 북쪽으로 향한다.
   • 축에 평행한 직선마다 포함된 점은 반드시 짝수가 된다.
   • 각 점은 각 방향마다 하나의 변을 이루고 있어야 한다. 즉 직선에 포함된 점들은 최대로 변을 이루고 있어야 한다. 즉 앞에서부터 인접한 두 점끼리 이으면 된다.

2024년 4월 27일 (P4)

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

2024년 4월 28일 (P5)

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

2024년 4월 29일 (G1)

1. 문제 : Klee in Solitary Confinement
2. 알고리즘 : ?
3. 성공 여부 : 실패
4. 풀이 링크 : 작성 예정
5. 복기 : 실패해서 알고리즘 열어봤는데 DP? 왜일까? 어차피 쿼리는 최대 한 번만 적용 가능한 것이면 그냥 간단한 구현 문제 같은데 왜 DP인지 이해가 가지 않는다. 내가 생각을 못하는 반례가 있는걸까...?

2024년 4월 30일 (G2)

1. 문제 : 문자열 생성 2
2. 알고리즘 : 그리디
3. 성공 여부 : 실패
4. 풀이 링크 : 작성 예정
5. 복기 : 사실 이번 문제는 풀 수 있을 줄 알았는데, 수정 $\rightarrow$ 반례 $\rightarrow$ 수정 $\rightarrow$ 반례 $\rightarrow$ $\dots$ 이 과정을 반복하다가 시간이 지나버렸다...😥 4연속 실패는 좀 충격적이다. 요즘 많이 바빠서 ps를 제대로 못하니 그런걸까. 일단 바쁜 일 모두 끝내면 4월 밀린 풀이 전부 적어야겠다.