[6개월 안에 백준 플래티넘 달성하기] 18. 중간 점검 | 백준 Class 문제 특징 | 문제 풀이 과정 공유 | 코테 팁
2023년 10월 1일부터 시작한 프로젝트가 벌써 3개월이 지났습니다.
현재까지의 진행상태와 풀이 경험에 대해 간단히 글을 남기고자 합니다.
현재 상태
새로운 아이디로 시작하여 0점에서부터 1290점 골드 2까지 점수를 올렸습니다.
물론 완전히 백지상태가 아니기 때문에 초반에는 점수를 빠르게 올릴 수 있었습니다.
하지만 과거에 포기했었던 구간부터는 난이도가 어느 정도 있는지라 하루에 한 문제씩 천천히 점수를 쌓아갔습니다.
78일 동안 매일매일 문제를 풀고 있습니다.
백준 Class 3까지는 그래도 하루에 여러 문제를 풀 수 있었는데 그 뒤로는 난이도 때문에 한 문제씩만 풀고 있습니다.
Class 4까지 모든 문제를 풀었고 현재는 Class 5 문제를 풀고 있습니다.
Class 단계별로 문제를 풀고 있지만 난이도의 차이도 어느 정도 있긴 하지만 그보다는 알고리즘의 차이가 더 큰 거 같습니다.
Class 1,2 에는 주로 구현과 문자열에 대한 문제
Clsss 3 에는 bfs, dfs, dp 등
Class 4 에는 bfs, dfs, dp, 재귀, 다익스트라 등
Class 5 현재에는 정수론, 최소 신장 트리에 대한 문제를 추가적으로 풀었습니다.
갈수록 어려운 알고리즘이 등장하는 구조입니다. 어려운 알고리즘일수록 기본적인 티어가 높습니다.
예를 들어 bfs를 이용하는 기초적인 문제가 실버 4 라면 다익스트라를 이용하는 기초적인 문제는 실버 1입니다.
따라서 모든 알고리즘에 대해 알고 있다면 다익스트라 골드 4,5 정도의 문제는 어렵지 않게 풀 수 있습니다.
그에 반면 bfs의 골드 4,5 문제는 난이도가 확 올라갑니다.
따라서 사실상 티어가 큰 의미가 없습니다.
문제 풀이 과정
문제를 많이 풀다 보니 어느 정도 문제 풀이 순서에 대한 규칙이 생긴 거 같아서 이를 공유하고자 합니다.
첫 번째로 문제를 간략하게 정리합니다.
문제가 매우 길 경우에도 핵심 조건만 따로 정리하면 문제를 다시 확인할 때 시간을 아낄 수 있습니다. 또한 조건들을 바탕으로 알고리즘을 유추하기도 편해집니다.
그래프 문제로 예시를 들자면 대략적으로 아래와 같이 정리할 거 같습니다.
- 양뱡향
- 마을을 두 개의 분리된 마을로 분할
- 마을과 마을 사이에는 길이 없어야 됨
- 마을 내부의 임의의 두 집 사이에 경로는 항상 존재
- 마을 내부에는 최소 하나 이상의 집이 있다.
- 최소 유지비
두 번째로 시간제한, 메모리 제한, 입력문의 제한을 확인합니다.
제한을 제대로 확인한다면 문제에 적용할 수 있는 알고리즘의 폭을 줄일 수 있습니다.
예를 들어 백준에서 시간제한 1초는 1억 회의 계산을 의미합니다. 만약 입력된 N=100,000이라면 O(n^2) 시간 복잡도의 알고리즘은 100억 회를 계산하기 때문에 사용할 수 없습니다.
마찬가지로 가끔 N=100,000,000,000,000 인 큰 수가 주어질 때가 있는데 이럴 경우에는 무조건 O(log n) 시간 복잡도의 알고리즘을 사용해야 됩니다.
이런 식으로 제한 사항을 통해 알고리즘을 유추할 수 있습니다.
세 번째는 문제를 풀면 됩니다.
문제를 해결할 아이디어가 있다면 그대로 풀면 됩니다.
하지만 해결에 대한 감이 오지 않을 경우 저는 다음과 같이 해주었습니다.
- 직접 결과값에 도달하는 경우를 확인하여 규칙성이 있는지 확인하는 방법
말 그대로 노가다 작업을 통해 규칙을 찾아주는 것입니다. - 다양한 알고리즘에 적용해 보면서 해당 문제가 풀리는지 역으로 추적하는 방법
위 두 가지 방법으로도 안 풀리고 계속 생각해도 아예 감이 오지 않을 경우 알고리즘 분류를 확인해 줬습니다.
70~80%는 알고리즘 분류를 보고 나면 해결이 되었습니다.
분류를 봐도 모를 경우 포기하고 해설을 봤습니다.
보통 처음 접하는 알고리즘 유형이거나 수학문제일 경우 풀이를 많이 보았습니다.
개인적으로 너무 오랫동안 풀이에 대해 생각하는 것보다는 스스로의 기준을 정하고 일정 시간이 지나면 해설을 보는 것이 시간을 좀 더 아낄 수 있는 방법이라고 생각합니다.
다각형의 면적 문제의 경우 수학 이론을 모르면 거의 풀 수 없는 문제입니다.
마지막으로 문제를 풀고 난 뒤에 더 좋은 풀이를 확인합니다.
백준에서 [맞힌 사람]을 보면 메모리와 시간을 효율적으로 짠 코드를 순서대로 보여줍니다.
여기서 적당히 첫 페이지에 있는 여러 사람들의 코드를 보면서 나랑 같은 알고리즘을 썼는지, 풀이과정이 같은지, 본인 코드보다 어떤 점에서 시간이 더 빠른지 등등 비교해 주면서 본인의 코드를 수정해 주었습니다.
해당 과정을 통해 같은 코드라도 더 효율적으로 구현할 수 있는 방법을 알아갈 수 있었습니다.
또한 아예 다른 풀이과정일 경우에는 코드를 해석하고 직접 구현도 해주었습니다.
하지만 주의점이 있습니다.
- 정말 고인물들의 풀이(어려운 풀이)일 경우에는 확인하지 않았습니다. 현타도 올뿐더러 아무리 봐도 이해가 되지 않습니다.
- 어떤 입출력 메서드를 썼는지에 따라 메모리와 시간이 다른 경우도 있기에 이를 감안하고 봤습니다.
ex) 자바의 경우 Scanner vs BufferReader
끝으로
저에게 코테는 암기 영역인 거 같습니다. 예전에 풀었던 기억 혹은 비슷한 문제를 풀었던 기억으로 문제에 익숙해지면서 풀 수 있는 거 같습니다. 이런 점이 제 스스로의 한계 때문인 거 같아서 슬프기도 하지만 그냥 많은 문제를 풀어보면 어느 정도 해결되지 않을까 싶기도 합니다.
저는 코테 풀기를 여러 번 포기한 적이 있습니다.
그때 당시 재귀함수가 도저히 이해가 되지 않아서 몇 시간 동안 붙잡았던 기억이 있습니다. 강제로 이해하고 암기한 뒤 다음 날 까먹어서 다시 못 풀고를 반복하며 내 머리로는 안 된다는 결론을 가졌었습니다. 하지만 시간이 지나면서 또다시 재귀함수를 풀고, 못 풀고 이를 반복하면서 자연스럽게 뇌에 익숙해져 어느 순간부터 이해가 되었던 거 같습니다.
그러니 포기하고 싶은 분들이 계신다면 너무 안 풀린다고 좌절하지 마시고 분명 어느 순간 이해가 되는 시점이 딱 올 거니 꾸준히 푸시는 것을 추천드립니다.
이해가 되는 순간 왜 내가 그렇게까지 어려워했는지 의아하게 되실 겁니다.
저는 남은 3개월 동안에도 꾸준히 문제를 풀어서 플래티넘에 달성해 보도록 하겠습니다.