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

2024년 3월 5일 (S5)

1. 문제 : Insulator
2. 알고리즘 : 그리디, 수학, 정렬
3. 성공 여부 : 성공 (9분)
4. 풀이 링크 : BOJ 8016 - Insulator 풀이
5. 복기 : 수열 $a$의 순서를 임의로 바꿔서 최댓값이 나오게 하는 문제인데, 너무 빨리 풀려고 하다보니 순서를 임의로 바꾼다는 문장을 읽지 못했다. 그래서 걸린 시간의 대부분을 예제 출력이 왜 24인지에 대해 생각을 하는 것에 써버렸다. 지문을 제대로 읽지 않는 점이 CP만 하면 나오는 내 치명적인 단점인데, 꾸준히 랜덤디펜스를 하면서 고쳐보아야겠다.

2024년 3월 6일 (S4)

1. 문제 : 카드 뽑기
2. 알고리즘 : 구현
3. 성공 여부 : 성공 (15분)
4. 풀이 링크 : BOJ 25185 - 카드 뽑기 풀이
5. 복기 : 최대한 naive하게 구현해보려 했는데, 한번 틀려버렸다. 그 이유는 세 번째 조건을 판단할 때 (a == d and b == c) 이렇게 적어야 하는데, (a == d or b == d) 이렇게 적어버렸다. ㅋㅋ큐ㅠㅠ... 처음에는 왜 틀렸는지 몰랐고, 그냥 순열 뽑아주는 함수 사용해서 코드 다시 짜니깐 AC를 받았다. 어이없는 실수를 줄여야겠다.

2024년 3월 7일 (S3)

1. 문제 : 님비합
2. 알고리즘 : 구현, 수학
3. 성공 여부 : 성공 (9분)
4. 풀이 링크 : BOJ 2685 - 님비합 풀이
5. 복기 : 진법 변환 문제가 나올 때마다 항상 헷갈린다. 그럴 때마다 임시방편으로 아무 낮은 수를 2진수로 직접 변환해보는데, 상당히 시간 낭비다. 진법 변환을 헷갈리지 않도록 잘 알아둬야겠다.

2024년 3월 8일 (S2)

1. 문제 : 다운로드
2. 알고리즘 : 그리디
3. 성공 여부 : 성공 (58분)
4. 풀이 링크 : BOJ 3216 - 다운로드 풀이
5. 복기 : 처음에 순서를 바꿀 수 있는 줄 알고 NP-Hard 문제 아닌가 싶었다. 문제를 제대로 읽자 ㅠㅠ... 그리고 내가 정말 그리디에 약하다는 것을 깨달았다. 사실 시간이 50분 넘어갈 때 S2에서 처음으로 실패하겠구나 생각이 들면서 자괴감이 들고 있었는데, 기적적으로 문득 풀이법이 떠올랐다. 그리디는 딱히 공부법이 없고 그냥 많이 풀어보는게 답이라는데 정말 막막하다. 열심히 해야겠다.

2024년 3월 9일 (S1)

1. 문제 : 컴백홈
2. 알고리즘 : 백트래킹
3. 성공 여부 : 성공 (20분)
4. 풀이 링크 : BOJ 1189 - 컴백홈 풀이
5. 복기 : 처음에 BFS로 접근했다가 잘 풀리지 않아서 백트래킹으로 다시 접근해서 AC를 받았다. 시간복잡도는 $O(2^n)$에 가까운 $O(3^n)$같다...? 적어보니깐 이상하다. 사방으로 뻗어나갈 수 있고 $prev$를 제외하면 세 곳인데, 경로 중 일부를 제외하면 결국 선택지는 두 곳 아니면 한 곳 밖에 남지 않게 됨을 알 수 있다. 시복 계산 어렵다 ㅠ

2024년 3월 10일 (G5)

1. 문제 : Constellations
2. 알고리즘 : 기하학, 분리 집합, 브루트포스
3. 성공 여부 : 성공 (9분)
4. 풀이 링크 : BOJ 5081 - Constellations 풀이
5. 복기 : 지문을 그대로 구현하는 분리 집합 기초 문제라서 그런지 쉽게 풀었다. 하지만 처음에는 가장 가까운 별을 하나만 고려하는 코드로 짰는데, 다행히 예제가 그걸 걸러주어서 바로 제대로 다시 짜서 AC를 받았다. 아마 예제가 걸러주지 않았다면 맞왜틀에 빠졌을 것 같다. (그런데 지문이 불친절한 것 같긴 하다...)

2024년 3월 11일 (G4)

1. 문제 : Polygraph (Small)
2. 알고리즘 : 브루트포스
3. 성공 여부 : 성공 (44분)
4. 풀이 링크 : BOJ 12601 - Polygraph (Small) 풀이
5. 복기 : 처음에 문제 제목을 보고 그래프나 분리 집합을 곁들인 백트래킹으로 접근을 했다. 문제 제목을 보고 잘못된 길로 빠지지 않게 노력해야겠다.

2024년 3월 12일 (G3)

1. 문제 : 약수
2. 알고리즘 : DP, 수학, 정렬
3. 성공 여부 : 성공 (57분)
4. 풀이 링크 : BOJ 19576 - 약수 풀이
5. 복기 : 처음에 그리디로 접근했다. 당연히 되지 않았고, $N$이 $5\,000$이길래 $O(N^2)$ DP일 것 같았는데 점화식이 바로 세워지지 않았다. 다행히 50분 넘어갈 때 점화식을 제대로 세우고 AC를 받았다. 첫 실패인가 싶었는데 다행이다. 모호한 풀이는 생각나는데 코드로 제대로 풀어내질 못할 때 속상했다. 사실 점화식을 적어보지 않고 머릿속으로만 정리를 해서 그런 것 같다. 이제 DP로 접근할 땐, 점화식을 꼭 적어보면서 풀어야겠다.

2024년 3월 13일 (G2)

1. 문제 : Firetrucks Are Red
2. 알고리즘 : DFS, 트리, 해시 맵
3. 성공 여부 : 성공 (12분)
4. 풀이 링크 : BOJ 18085 - Firetrucks Are Red 풀이
5. 복기 : 시간 제한이 지나치게 넉넉하고 $d$의 제한이 $10^9$인데 메모리 제한이 그에 비해 타이트하길래, 이 문제는 적당한 메모리 최적화하는 문제구나 싶었다. 그래서 적당히 해시 맵 쓰고 DFS 돌리니 너무 쉽게 AC를 받았다. 아무리 생각해도 G2 치고 쉽길래 난이도 기여를 보니 다들 분리 집합, MST로 풀었더라...? 당황했다. 그래서 그냥 내가 기여를 G4 주고 이 문제의 난이도를 G3으로 내려버렸다. ㅋㅋㅋㅋㅋㅋㅋㅋ 나도 아마 알고리즘 태그를 보고 풀었으면 MST로 접근했을 것 같다. 역시 태그를 보지 않고 시간 제한 안에 풀어보는 연습을 하니 적당히 쉬운 알고리즘으로 풀어버리는 좋은 능력이 생기는 것 같다.

• 2024년 3월 14일 ~ 2024년 3월 17일은 해외 여행 일정으로 쉬어갑니다.

2024년 3월 18일 (G1)

1. 문제 : 그래프 만들기
2. 알고리즘 : DP
3. 성공 여부 : 실패
4. 풀이 링크 : BOJ 12909 - 그래프 만들기 풀이
5. 복기 : 내가 접근한 방법은 다음과 같다. 현재 정점의 개수를 $n$으로 차수마다 개수를 $res$ 배열로 잡자. 최대로 나올 수 있는 차수는 $n-1$이다. $1$부터 $n-1$ 차수까지 살펴보면서 각 차수가 존재한다면, 그 차수인 정점에 정점 하나를 붙이면 $1$ 차수인 정점 하나 증가, $i$ 차수인 정점 하나 감소, $i+1$ 차수인 정점 하나 증가한다. 이 방법으로 dfs를 진행 및 해시 DP를 이용해서 커팅을 했다.
   위 방법으로 계속 접근하다가 결국 TLE의 늪에서 빠져나오지 못하고 실패했다... 결국 2차원 DP로 풀어냈는데, 조금 아쉽다. 핵심 포인트인 정점의 개수, 차수까지 잘 접근했는데 이를 2차원으로 접근할 생각만 했으면 풀어냈을 것 같다. 앞으로는 관찰을 잘해야겠다.
   p.s. 위에 서술한 방법으로 해시 최적화를 조금만 하니깐 PyPy3로 뚫렸다...! 정말 아쉽다 ㅠㅠ

2024년 3월 19일 (G2)

1. 문제 : FEB
2. 알고리즘 : 애드혹, 해 구성
3. 성공 여부 : 실패
4. 풀이 링크 : BOJ 28034 - FEB 풀이
5. 복기 : 문제의 핵심 포인트는 다음과 같다.
   - F...F를 $S_F$, $S_F$의 길이를 $n$이라고 하자.
   1. $S_F$가 맨 앞이나 맨 뒤에 있을 때엔, 가능한 개수는 $0$, $1$, $\dots$, $n$이다.
   2. $S_F$의 양쪽 문자가 동일할 때엔, 가능한 개수는 $n+1$, $n-1$, $\dots$이다.
   3. $S_F$의 양쪽 문자가 동일하지 않을 때엔, 가능한 개수는 $n$, $n-2$, $\dots$이다.
   위 세 경우가 문제의 핵심 포인트인데, 난 이 세 경우를 느리지 않게 다 찾았다. 하지만, 이걸 $O(N)$으로 풀어낼 방법이 도저히 떠오르지 않았다. 결국, 가능한 수의 최소와 최대 그리고 증가 인자만 정리하면 되는 것이었다. 속상하네... 역시 애드혹은 쉽지 않음을 뼈저리게 느꼈다.
   그런데 솔직히 G2보단 어려운 듯. 그래서 P4 줘버렸다. 문제 운이 없었다. 문제 선정할 때 푼 사람의 수도 적용해야 하나 심각하게 고민 중이다.

   

2024년 3월 20일 (G3)

1. 문제 : 알 수 없는 문장
2. 알고리즘 : DP
3. 성공 여부 : 성공 (12분)
4. 풀이 링크 : BOJ 1099 - 알 수 없는 문장 풀이
5. 복기 : 솔직히 쉽게 풀었다. 1차원 DP 문제라 그런지 바로 눈에 보였다. $N$이나 길이가 최대 $50$이란 점에서 최적화를 하지 않아도 뚫리겠다 싶어서, 신경쓸만한 점도 많지 않았다. 그래도 자만하지 않고, 풀이 작성할 때 점화식을 직접 적어보며 남들에게 어떻게 쉽게 설명할지 고민해보았다. 원래 남들에게 설명해줄 수 있을 때, 진짜 공부가 된 것이라고 했으니...!
   아니 근데 DP 문제가 많이 걸리는 것은 기분 탓인가... 아니면 이 티어 구간에 DP가 많은 건가...

2024년 3월 21일 (G2)

1. 문제 : 유니온 파인드 복원
2. 알고리즘 : 분리 집합, 위상 정렬, 해 구성
3. 성공 여부 : 성공 (23분)
4. 풀이 링크 : BOJ 22996 - 유니온 파인드 복원 풀이
5. 복기 : $2$번 질의는 바로 처리해야 함은 떠올랐지만, $1$번 질의를 처리할 때의 간선 순서를 생각치 못해 맞왜틀 시전하다가 결국 위상 정렬로 AC를 받았다. 난이도 기여를 보니깐 간선을 타고 DFS를 진행해서 리프 정점에서 나아가는 간선부터 출력하는 느낌으로 한 것 같은데, 뭐 어떻게 보면 유향 트리에서 위상 정렬도 거의 비슷한 느낌이니깐...? 거의 정해로 푼 것 같긴 하다.
   문제 출제자 입장으로 보면 이런 참신한 문제를 어떻게 만드는걸까 신기하다.

2024년 3월 22일 (G1)

1. 문제 : 트리의 높이 줄이기
2. 알고리즘 : 그리디, 트리
3. 성공 여부 : 실패
4. 풀이 링크 : BOJ 2275 - 트리의 높이 줄이기 풀이
5. 복기 : 바보같이 루트에서 현재 정점까지의 거리를 고려하지 않아서 실패했다. 루트에서 DFS를 진행해서 현재 높이가 $H$보다 크다면 그 차이만큼 $res$에 더하고, 더한 값만큼 인자로 넘겨주고 진행하는 AC 코드와 거의 비스무리하게 짰다. 그런데 현재 줄인 비용 $cost$와 앞으로 남은 높이랑만 비교를 해버렸다. 아이고 아까워라 ㅠㅠ
   난이도 P5로 올라가나 싶었는데...

2024년 3월 23일 (G2)

1. 문제 : 최대공약수 하나 빼기
2. 알고리즘 : 누적 합, 세그먼트 트리, 수학
3. 성공 여부 : 성공 (59분)
4. 풀이 링크 : BOJ 14476 - 최대공약수 하나 빼기 풀이
5. 복기 : 아찔하다. 거의 버저 비터로 성공했다. 처음에는 약수 개수 카운트하며 $N-1$개가 되었을 때 최대공약수 $g$에 곱해주는 그런 느낌으로 접근했는데 잘 풀리지 않았다. 시간이 끝나갈 때, 안되면 안되는거지 마음으로 세그 박았는데 뚫렸다... 🙄
   시간복잡도가 $O(N \log N \log 2\,000\,000\,000)$로 보기만 해도 숨막히는데 뚫리네. (시간복잡도가 정확하게 맞는지는 모르겠다)
   아무튼 앞으로 구간 정보를 처리할 땐 일단 한번 해보자는 마음으로 세그를 시도해야겠다.

2024년 3월 24일 (G1)

1. 문제 : Projection
2. 알고리즘 : 구현, 기하학, 해 구성
3. 성공 여부 : 성공 (38분)
4. 풀이 링크 : BOJ 17963 - Projection 풀이
5. 복기 : $maximum$과 모순인 경우는 바로 어떻게 해야 할 지 떠올랐는데, $minimum$을 구하는 방법은 바로 떠오르지 않았다. 다행히 필요한 인덱스끼리 짝짓는 방법이 늦지 않게 떠올라서 구현할 수 있었다.
   3D 기하학을 베이스로 한 깡구현, 깡해구성 문제라 푸는데 머리가 복잡했다. 특히 처음엔 어디부터 $(0,0,0)$인지가 굉장히 헷갈렸다. 이런 문제 다시는 만나고 싶지 않아요...

2024년 3월 25일 (P5)

1. 문제 : 유물 복원
2. 알고리즘 : DP, 수학
3. 성공 여부 : 실패
4. 풀이 링크 : BOJ 17075 - 유물 복원 풀이
5. 복기 : 일단 BOJ 1286 문제의 풀이가 이 문제의 배경지식으로 사용된다. 난 이 문제를 풀어본 적이 없어서, 공식을 찾아내는데 꽤 시간이 많이 들었다...
   결국 가중치를 $O(NM)$에 구하긴 했는데, 이 뒤는 생각이 잘 나지 않았다. 뭔가 냅색 DP 냄새가 풀풀 풍겨왔지만, '$K$의 배수에 딱 맞게 어떻게 채워' 라는 생각으로 접근하질 않았다. 나란 사람 바보...
   저번 DP 문제에서도 비슷한 상황인데, 인자를 하나 더 늘려 DP를 해볼 생각을 꼭 해봐야겠다.

2024년 3월 26일 (G1)

1. 문제 : LCM
2. 알고리즘 : 수학
3. 성공 여부 : 실패
4. 풀이 링크 : BOJ 11414 - LCM 풀이
5. 복기 : $\gcd(x,y)=\gcd(x-y,y)$ 이걸 몰라서, 랜덤디펜스 시작하고 최초로 도중 포기했다...;
   내가 확실히 정수론에 대한 배경지식이 정말 약하다는 것을 깨달았다. 어디선가 PS는 수학과 비슷하다? 라는 문장을 본 적이 있었던 것 같다. 이 문제를 포기하고 풀이 보면서 공부하는데 떠오르더라. 수학을 다시 공부해야 하나...

   

2024년 3월 27일 (G2)

1. 문제 : 연습시즌
2. 알고리즘 : DP
3. 성공 여부 : 성공 (41분)
4. 풀이 링크 : BOJ 9023 - 연습시즌 풀이
5. 복기 : 처음엔 그리디로 접근했는데 역시나 안됐고, 스택으로 접근해야 하나 고민하다가 결국 네 개의 인자로 dp 진행하는 방법을 찾아내 AC를 받았다.
   근데 처음에는 휴식 유무가 아니라 연속 휴식 일수로 인자를 설정해서, 메모리 제한이 $128$ MB인데 뚫릴까 싶어서 해시 dp로 AC를 받았다. 왜 처음부터 휴식 유무로 생각을 못했을까...?🙁 아무튼 지문도 복잡하고 dp 문제임이 바로 보이진 않는 그런 문제여서 꽤 힘들었다.

2024년 3월 28일 (G1)

1. 문제 : 리그 오브 레전설 (Large)
2. 알고리즘 : DP, 수학
3. 성공 여부 : 실패
4. 풀이 링크 : BOJ 17272 - 리그 오브 레전설 (Large) 풀이
5. 복기 : 1차원 선형 점화식은 행렬 곱으로 나타내서 풀어낼 수 있음을 처음 알았다. 지금까지 몰랐던 나 자신이 부끄럽지만, 이걸 기회로 많은 것을 배웠다. 이제 1차원 DP지만 아무리 $N$이 무지막지하게 커도 꼭 풀어낼 수 있을 것 같다!

2024년 3월 29일 (G2)

1. 문제 : 재미있는 숫자 게임
2. 알고리즘 : DP, 게임 이론
3. 성공 여부 : 실패
4. 풀이 링크 : BOJ 16876 - 재미있는 숫자 게임 풀이
5. 복기 : 수의 범위가 $10\,000$인 점과 $M$의 범위가 $100$ 밖에 안되길래, 각 턴마다의 상태를 다음 턴으로 넘겨주면서 각 숫자마다 DP를 진행하면 됨을 보자마자 알아챘는데... 게임 이론의 핵심인 승패 케이스를 나누는 것을 못했다. 게임 이론 문제를 많이 접해보지 않아서 정확하게는 모르지만, 무조건 결정되는 승패케이스로부터 시작해서 각 상태를 가져오거나 넘기는 느낌으로 진행하면 웬만한 게임 이론은 다 풀리는 것 같다. 하지만 안타깝게도 이 문제에서 그걸 못찾아서 실패했다.
   음... 현재 숫자 $n$이 선형이니깐 확실하게 케이스를 나누는 방법을 생각하지 못한 것 같다.
   많은 게임 이론 문제를 접하는 것만이 답인 것 같다.

2024년 3월 30일 (G3)

1. 문제 : 출퇴근
2. 알고리즘 : 다익스트라
3. 성공 여부 : 성공 (12분)
4. 풀이 링크 : BOJ 20313 - 출퇴근 풀이
5. 복기 : 내가 제일 자신있어 하는 알고리즘인 그래프, 그중에서도 다익스트라 문제가 걸렸다. 너무 쉽게 풀어버렸다. 그런데 간선 이동할 때마다 마법을 한 번씩만 사용하게끔 코드를 짜서 1틀 해버렸다. 역시 자만은 금물이다.

2024년 3월 31일 (G2)

1. 문제 : Stuck in a Rut
2. 알고리즘 : 구현, 정렬
3. 성공 여부 : 성공 (58분)
4. 풀이 링크 : BOJ 20652 - Stuck in a Rut 풀이
5. 복기 : 어떻게 풀지는 바로 생각이 났지만, 이를 코드로 구현하려니 생각보다 복잡하고 구현량이 많아서 꽤 힘들게 풀었다.

   

   그리고 위와 같은 케이스를 고려를 하지 않아서 처음에 틀렸는데, 그때 시간이 얼마 남지 않아서 굉장히 당황했었다. 다행히 문제 예제가 친절해서 위와 같은 케이스를 고려하는 코드를 바로 짤 수 있었다. 아마 예제가 불친절했다면 실패하지 않았을까...?🤔