오늘을 기점으로 백준에서 제공하는 문제들을 64일 연속으로 풀게 된 날이다. 백준 문제들의 난이도를 알려 주는 solved.ac를 이용하면 매 2^N일 스트릭을 기록할 때마다 배지를 주는데, 64일 배지를 받은 기념으로 지금까지 풀어온 감상에 대해 얘기하려 한다.
PS에 제대로 관심을 가직 시작한 것은 2021년으로, 개인 사정으로 휴학을 했을 때 뭔가 공부를 하는 게 낫지 않을까 싶어서 시작했던 것이 PS였다. 지금 돌이켜보면 그때 웹 개발이나 열심히 했으면 좋았을걸 싶긴 하지만 웹에 대해서는 좀 더 나중에 흥미를 붙이게 되었기 때문에...
책과 함께 시작하기
사실, PS를 시작했을 때부터 백준에서 문제를 푼 것은 아니다. 정확히 말하자면, 가장 처음에 남들도 하니까 따라서 백준 계정을 만들어서 고작 몇개 풀어본 게 다였다.
나는 본격적으로 시작하기 위해서 PS 입문자들에게 추천하는 <알고리즘 문제 해결 전략>, 일명 하얀책을 1, 2권 모두 구매해서 공부했다. 그냥 아무런 생각 없이 일단 책을 구매했고, 책을 다 읽었을 때 즈음하여 책에 대한 리뷰를 보는데 이 책은 오래 돼서 알고리즘의 최근 동향을 담고 있지 못하다는 글도 있었고 아무튼 그랬지만, 내 기준에서는 이 책을 통해서 정말 많은 지식을 얻을 수 있었다.
오히려 입문자의 입장에서는 최신의 동향보다는 에센셜한 내용을 알고 싶을 뿐이다. 물론 PS에 더 흥미를 붙이면서 CTF에 나가고 하는 정도라면 최근에는 어떤 것들이 떠오르고 있는지와 같은 것들을 머리에 새길 필요도 있겠지만, 나는 애초에 입사할 때에 코딩 테스트를 통과하는 정도의 수준만 되자가 목표였기 때문에...
잠시 이야기의 방향이 벗어났는데, 하얀책에서는 알고스팟이라는 사이트를 통해 책에 나오는 문제들을 직접 채점할 수 있었다. 처음에는 이 사이트를 이용해서 문제를 풀었고, 책을 다 읽을 때 쯤에는 거의 대부분의 문제를 풀었었다. 처음에는 하루가 걸리든 이틀이 걸리든 나 혼자의 힘으로 문제를 푸는 것을 중시했는데, 주변에서 그렇게 하는 것보다는 한 시간정도 고민해도 답이 안 나오면 그냥 답지를 보고 공부하는 것이 훨씬 낫다고 하길래 그렇게 했다. 물론 문제를 풀 때에는 답지를 그대로 베끼는 것이 아니라, 풀 때만큼은 나 혼자서 푸는 것을 중요시했다.
사실 알고스팟은 그렇게 추천할만한 사이트는 아니다. 문제의 양도 적고, 사이트가 오래되고 이용자가 매우 적으며(질문과 같은 글이 한 달에 한두 개 올라오는 정도다) 사이트가 매우 느려서 언제 사라져도 이상하지 않을 사이트라 생각한다. 더욱이 solved.ac 서비스가 등장하고 나서는 백준의 편의성이 더 증가했다.
하얀책에 나오는 난이도는 하/중/상 3단계로 나누어져 있지만 특히 상 난이도는 solved.ac의 플래티넘 난이도도 거뜬히 넘을만한, 아무리 입문자에게 추천하는 책이라지만 상당히 어려운 내용으로 이루어진 경우도 있었다. 아무튼 책을 다 읽고, 나는 백준으로 옮겨서 문제들을 다시 풀기 시작했다.
백준과 solved.ac의 문제 모음 활용하기
처음 백준을 풀었을 때에는 백준 내부의 "단계별로 풀어보기" 기능을 이용해서 문제를 풀었다. 그러나 문제점이 하나 있었다. 문제를 접하기도 전에 문제에서 요구하는 사고 방식을 알게 된다는 것이다. 예를 들어, "동적 계획법 1"이라는 단계에서 문제를 골라서 풀면 문제를 클릭하기도 전에 '이 문제는 동적 계획법으로 푸는 문제구나'라는 것을 알게 된다. 실제로 문제를 접했을 때는 아무런 힌트도 주어지지 않기 때문에, 이런 방식은 좋지 않다고 느꼈다.
그래서 나는 solved.ac를 이용하기 시작했다. 좀 더 문제가 잘 정렬되어 있었다. 난이도 별로 찾아볼 수 있는 것도 좋았지만, 클래스별로 문제를 풀어볼 수 있다는 점이 매력적으로 느껴졌다. 이미 나는 책으로 이런저런 내용들을 배웠기 때문에 클래스 1, 2는 스킵하고, 클래스 3정도부터 찬찬히 등반하는 걸로 했다.
그렇게 날이 지나고, 클래스 3/4/5를 전부 취득했다. 클래스 3부터는 각각 48문제가 수록되어 있고, 그중 특정 개수 이상을 풀면 클래스 3, '에센셜'로 지정된 문제를 모두 풀면 클래스 3+, 48문제를 모두 풀면 클래스 3++을 취득하는 형태이다. 나는 3++, 4++, 5++를 모두 취득하는 것을 목표로 했고, 클래스 5++를 취득했을 때에는 총 144문제를 풀었다.
클래스 6도 똑같이 풀려고 했는데, 이때부터 수학적인 개념이나 배경 지식을 요구하는 문제들이 좀 등장하기 시작해서 클래스 6을 푸는 것보다는 적당히 난이도에 대한 감을 잡았기 때문에 난이도를 집어서 하루에 하나씩 풀기로 했다.
최근에는 골드 3 난이도를 '푼 사람 수'로 내림차순 정렬해서 안 푼 것들부터 계속 밀었었다. 그리고 바로 어제 푼 사람 수로 정렬했을 때 골드 3의 한 페이지를 전부 풀어서 오늘부터 골드 2 문제를 풀게 되었다.
코딩테스트, 그리고 프로그래머스와의 관계
실제로 코딩테스트에서는 기본적인 알고리즘에 대한 구현, 혹은 그것의 응용이 나오며 가끔 카카오 공채같은 경우 마지막 문제에서 만점 방지용으로 좀 어려운 난이도의 문제가 나오는 경우가 있다(맞추지 못한다고 해도 당락에 거의 영향이 없다고 한다). 특히 수학적인 배경 지식을 활용하는 문제가 거의 나오지 않고, 대부분 무언가를 구현하는 문제가 많았다.
코딩테스트는 대부분 프로그래머스라는 사이트에서 진행하기 때문에, 자신이 평소에 백준을 풀 때와의 느낌과는 좀 다를 수 있다. 회사마다 다르지만 IDE 사용 자체를 금지하고 프로그래머스에서만 푸는 것을 요구하는 회사도 있기 때문에 코딩테스트를 목표로 하는 사람이라면 적어도 1~2주 전부터는 프로그래머스 시스템에 익숙해지기 위해 해당 사이트에서 문제를 풀어 보는 것을 추천한다.
IDE를 사용하지 못하면 자동 완성 등도 사용할 수 없기 때문에 priority_queue에서는 top()을 쓰다가 queue에서는 front()를 써야 한다는 점이나 push_back()을 써야 하는지 push()를 써야 하는지도 헷갈릴 수 있다. 물론 코딩테스트를 진행하는 도중 언어 레퍼런스 문서는 열 수 있기 때문에 그곳에서 참조를 해도 되지만 가장 효율적인 것은 몸에 익히고 있는 것이기 때문에...
또, 프로그래머스에서는 코딩테스트 기출 문제도 수록되어 있기 때문에 코딩테스트에 나오는 문제는 어떤 식인지를 알 수 있다는 점도 하나의 장점이다.
프로그래머스를 사용하면서 불편했던 점은 테스트 케이스를 추가하는 UI가 좀 불편했다는 점, 편했던 점은 문제를 풀 때 테스트 케이스를 몇 개 틀렸는지 알려주는 점이다. 백준처럼 퍼센테이지가 올라가다가 틀렸습니다가 뜨는 게 아닌, 모든 테스트 케이스에 대해서 돌린 다음 그 결과를 띄워 주는 방식이다(물론 테스트 케이스의 데이터에 대해서 알려 주지는 않는다).
처음에 봤던 코딩테스트가 카카오에서 봤던 코딩테스트였던 걸로 기억하는데, 카카오는 실전에서도 코드를 제출하면 실제 테스트 케이스에서도 모두 정답인지 아닌지를 알려 줬다. 그래서 원래 이런 줄 알았는데, 타사의 코딩 테스트를 다시 프로그래머스에서 봤을 때는 코드를 제출하면 "제출하였습니다" 메시지만 나오고 테스트 케이스를 돌려본 결과를 알려 주지 않았다. 그래서 좀 당황했는데, 코딩테스트를 몇 번 치르고 나니 오히려 카카오가 특이 케이스였음을 알게 되었다. 문제 수도 많고 시간도 길며 난이도도 평균 이상이었기 때문에 아마 이렇게라도 해 준 것이 아니었을까 생각이 든다.
지금 생각해보니 대부분의 코딩테스트에서는 검색조차 금지한 반면 카카오에서는 검색도 허용되었었다. 그러나 다른 코딩테스트에 비해 난이도가 어려웠다고 생각이 들었는데, 아마 오픈북 시험을 준비하시는 교수님의 마음이 이런 마음이 아닐까 싶다.
어떤 알고리즘을 중점적으로 밀었나
이런저런 알고리즘 지식을 다지고 도전한 것이 양날의 검처럼 작용했다고 느꼈을 때가 있다. 어떤 문제들은 구현만 복잡한 완전 탐색 문제인데, 완전 탐색이라고 하면 뭔가 시간 초과가 걸릴 것 같아서 머리만 싸매다가 못 풀게 된 적이 있었다. 그러니 적절한 알고리즘이 떠오르지 않는다면 일단 브루트포스로 밀어볼 생각을 하는 것도 중요하다.
거기에 또 중요한 것은 기본적인 자료 구조의 사용을 숙지하는 것. 스택, 큐를 이용한 문제는 단골 문제라는 느낌이 강하다. 문자열을 다루는 문제도 단골이다. 데이터가 전부 파싱되어 있지 않고 "a b c"라는 스트링 하나로 주어지는 경우가 많기 때문에, 문자열을 파싱하는 알고리즘은 꼭 숙지해야 한다(C++ 기준 stringstream을 통한 문자열 파싱).
또한, 그래프를 다루는 문제. 길찾기 혹은 최소 비용 찾기는 대부분 다익스트라 또는 플로이드-워셜 알고리즘 등을 이용해 푼다. 또한, 문제에 주어진 데이터를 그래프로 가공할 수 있어야 한다.
BFS나 DFS 알고리즘도 중요하다. 특히 최단 거리를 찾는 문제에서 BFS를 자주 사용하게 될 것이다. 가끔 문제를 제대로 이해하지 못하면 최단 거리라는 말만 듣고 BFS가 아니라 다익스트라부터 썼다가 오히려 시간 초과가 나는 경우가 생길 수 있다. 또, Union-Find를 이용하는 상호 배타 집합 문제도 가끔 나온다.
그리디 알고리즘을 이용하는 경우도 있다. 떠올리는 방식 자체는 간단하지만 뭔가 허점이 있을 것 같고 정당성을 증명하기가 좀 복잡한 경우가 있지만, 그리디 알고리즘 문제를 몇 번 풀어 본다면 유사한 문제가 나왔을 때 확실히 떠올리기는 쉽다.
반대로 수학적 배경 지식을 요구하는 문제같은 경우에는 그렇게 본 적이 없었던 것 같고, 백준에서는 그렇게 자주 나올 수가 없었던 다이나믹 프로그래밍 문제도 많지 않았던 것 같다. 물론 이러한 알고리즘이 앞으로의 코딩테스트에 나오지 않는다는 보장은 할 수 없기 때문에 소홀히 하라는 말은 아니다. 나도 백준에서 다이나믹 프로그래밍 문제를 매우 많이 봤기 때문에 사실 푼 문제 수는 다이나믹 프로그래밍이 상위권에 있다.
마치며
나는 solved.ac에서 클래스 3, 4, 5를 모두 풀었고, 플래티넘 5 티어에 있으며 골드 3정도까지는 큰 고민 없이 문제를 풀 수 있도록 능력을 길렀다. 아마 이정도 레벨만 돼도 대부분의 코딩테스트를 통과하는 데에는 문제가 없을 것이라고 생각한다.
또한, 64일동안 스트릭을 유지하면서 느껴본 건 감을 유지하는 것이 중요하다는 것이다. 위의 스크린샷을 보면 회사에서 일하기 전에도 상당히 문제를 꾸준히 풀었었는데, 퇴사 후 다시 백준 풀이를 시작했을 때에 시작하는 며칠 간은 다시 몸에 익게 하느라 살짝 고생했던 기억이 있다. 대부분의 회사가 공채를 하는 시기가 비슷비슷하기 때문에 코딩테스트가 몰려 있는 기간이 있을 수 있고, 나 역시 약 2달 조금 안되게 매주 코딩테스트를 봤던 것 같다. 적어도 이러한 기간 동안이라도 감을 잃지 않도록 하는 것이 중요하다고 생각한다.
(+추가) 결국 스트릭 자체는 크게 중요한 것이 아니라는 것이다. 물론 스트릭을 유지하면서 본인이 성취감을 얻는 타입이라면 스트릭을 유지하는 것이 좋지만(내가 그런 타입이다), 굳이 스트릭을 유지하지 않아도 어느 정도 실력을 높이거나 감을 유지하는 선이라면 몇 번을 빼먹건 상관은 없다.
https://www.youtube.com/shorts/VOk0_wfaDcU (대충 꾸준히 해야 한다는 강박에 사로잡혔을 때 역효과가 일어날 수 있다는 영상이다.)
나는 스트릭을 유지하는 게 좋아서, 아침에 일어나서 '졸린데 더 잘까'라는 생각이 들 때 백준 한 문제는 풀고 잤던 적도 있고, 동기들이랑 한강에 놀러 갔을 때에도 노트북을 들고 가서 돌아가는 길 23시가 다 끝나가는 택시에서 버저비터를 울린 적도 있다(solved.ac 기준으로는 오전 6시가 되기 전에만 풀면 되지만). 뭔가 나도 꾸준히 해야 한다는 강박에 사로잡혀 있는 것 같지만 지금까지는 잘 해왔으니 앞으로도 잘 할 수 있을 거라고 믿고 있다.
뭔가 글을 써보니 회고록이 아니라 "코테 통과하려면 저처럼 하세요"같은 글이 된 것 같은데, 전혀 그런 의도를 통해 쓴 건 아니고...평소에 정보를 기록하는 글을 좀 쓰다 보니까 글의 톤이 이렇게 된 것 같다. 물론 이 글을 보고 누군가 방향성을 잡아서 코테를 통과하면 기쁠 수도 있겠다.
'공부 > PS' 카테고리의 다른 글
[BOJ 1949] 우수 마을 (Gold II) (0) | 2022.11.17 |
---|---|
PS에 편한 C++ 문법 (1) | 2022.09.29 |
최단 거리 알고리즘의 이해 (0) | 2022.09.22 |
KMP 알고리즘 (0) | 2022.02.13 |