PS를 공부하는 뉴비들을 위한 안내서

문제 풀이(Problem Solving)를 잘 하기 위해서는 어떤 노력을 해야할까요?

 

 

시작하기 전에, 제가 대체 뭐하는 사람이길래 이런 글을 쓰는지는 알려드려야 글에 설득력이 생길거라고 생각합니다.

제가 지금까지 걸어온 길은 다음과 같습니다.

• '15 대학 입학, C언어와 C++ 기초 공부 시작
• '15 교내 프로그래밍 대회 대상
• --공백기 (군대), 개인 공부--
• '19 5월 Codeforces Candidate Master 달성
• '19 SCPC 5등상
• '19 ACM-ICPC 서울대회 본선 진출 (ANZ1217)
• '19 11월 Codeforces Master 달성
• '20 8월 Codeforces GrandMaster 달성
• '20 SCPC 4등상
• '20 ACM-ICPC 서울대회 특별상 (INPISA)
• '22 졸업/취직

이 외에도 21년 교내대회 출제를 포함해 몇몇 대회들의 검수를 진행하였고, PS관련 수업이나 과외도 꽤 했습니다.

지금까지 제가 해온 공부와, 옆에서 보아온 다른사람들의 사례들을 토대로 여러분께 PS공부를 어떻게 하는게 좋은지 말씀드리고자 합니다.

 

이제 입문하고자 하는 뉴비분들이나 실력이 막힌것 같아 공부 방법을 바꿔야겠다고 생각하시는 분들이 보시면 특히 좋을 것 같습니다. 그리고 제 주관적인 생각이 아주 많이 담겨있으니, 반박시 여러분이 다 맞습니다.

 

코딩테스트?

이 글은 코딩테스트를 대비하기 위한 분들을 위한 글이 전혀 아닙니다.

 

코딩테스트는 말 그대로 코딩, 즉 '원하는 것을 코드로 찍어낼 수 있는가?' 를 테스트하기 위해 하는 시험입니다.

코테를 무난하게 통과할 정도의 코딩 실력을 가지는 것은, PS를 공부하는 목표가 아니라 PS공부를 시작하기 전 당연히 갖춰야 하는 것 중 하나입니다.

특히 2022년 1월 현재 기준으로, 코딩테스트에 알고리즘이나 문제해결력을 요구하는 경우가 더더욱 적어지고 있습니다.

당장 어렵다고 평가되는 카카오 코딩테스트마저도 작년의 경우 시간복잡도를 계산하는 등의 PS적 사고가 없더라도, 단순히 요구하는 내용에 대한 코딩을 할 줄 아는지를 평가하기 위한 문제들이 출제되었습니다.

 

https://www.acmicpc.net/workbook/view/1152

문제집: 삼성 SW 역량 테스트 기출 문제 (baekjoon)

개인적으로는 이 문제집의 문제들 중 아무거나 하나 집어서 1시간 이내에 정답을 맞을 수 있다면 충분한 코딩실력을 갖춘 상태라고 생각합니다.

 

 

알고리즘

어떤 문제를 풀기 위해서는 특정한 알고리즘이나 자료구조를 사용해야 합니다.

그런데 주변을 보면 너무나도 비효율적으로, 이 알고리즘 공부를 하시는 분들이 꽤나 보입니다.

• "오늘은 이 알고리즘에 대해 공부해야지!" 공부할 알고리즘을 하나 정한다.
• 백준사이트에서 해당 알고리즘 기본문제를 켜놓고, 각종 블로그와 책과 코드를 '참고'해서 어떻게든 정답을 얻어낸다.
• 기본문제를 풀었으니 이제 이건 아는 알고리즘이다! 그리고 새로운 알고리즘을 또 정해서 위에서부터 반복한다. 이 루프만 돌려도 솔브닥 티어가 굉장히 빠르게 올라가고, '뭔가 하고 있다'는 생각이 든다.
• 대회 등에서 '공부'했던 알고리즘을 조금 응용한 문제가 나온다. 손도 대지 못한다.

대회등에서 실전 문제들을 풀게 되면, 문제에서 대놓고 '무슨 알고리즘을 써서 푸는 문제입니다' 라고 광고하지 않습니다. 보통은 다음과 비슷한 과정을 거쳐 문제를 풀게 됩니다.

• 문제를 어떤 관찰을 통해 일반적인 유형의 문제로 바꾼다.
• 이 일반적인 문제는 @@알고리즘/자료구조를 사용하여 ##의 시간복잡도에 풀 수 있음이 잘 알려져 있다.
• 이를 코드로 구현하고, 디버깅한다.

알고리즘 자체를 공부하고 여기에서 파생되는 문제를 푸는 것으로는 이와 같은 프로세스가 쉽게 나오지 않습니다.

우리가 문제를 읽으면 특정한 알고리즘을 먼저 인식하는 것이 아니라 일반적인 문제나 상황을 먼저 인식하기 때문에, 반대로 공부해야 효율적입니다. 특정한 문제유형을 보고 이 문제를 어떤 알고리즘/자료구조로 풀 수 있는지 숙고하는 과정을 많이 거쳐봐야, 여러분이 처음 보는 유형의 문제를 보더라도 이와 같은 프로세스를 쉽게 돌릴 수 있게 됩니다.

 

몇 가지 문제를 준비했습니다.

시간복잡도와 구현 속도를 고려하여, 각 문제를 풀기 위해 가장 효율적인 방법은 무엇인지 맞혀봅시다.

 

길이가 \(10^5\)이고, 절대값이 \(10^5\)이하인 자연수만을 원소로 가지는 배열 \(A\)가 있습니다.

 

1. 임의의 원소 \(x\)가 \(A\)에 존재하는지 판별
2. 1번과 같은 쿼리가 \(10^5\)번 주어짐
3. \(A\)의 최소/최대값 찾기
4. 3에서 \(A\)의 원소 하나를 다른 값으로 변경하는 쿼리 역시 \(10^5\)번 주어짐
5. \(l\)번 인덱스에서 \(r\)번 인덱스까지의 부분 합을 구하는 쿼리가 \(10^5\)번 주어짐
6. 5에서 \(A\)의 원소 하나를 다른 값으로 변경하는 쿼리 역시 \(10^5\)번 주어짐
7. \(A\)에서 \(k\)번째로 작은 원소를 찾는 쿼리가 \(10^5\)번 주어짐
8. 7에서 \(A\)의 원소 하나를 다른 값으로 변경하는 쿼리 역시 \(10^5\)번 주어짐

바로바로 답이 나오셨나요? 풀었는데 확신이 없나요? 아니면 감이 잘 오지 않나요?

어떤 문제를 풀고난 후에, '\(n\)이 더 크다면?', '문제의 이 조건이 존재하지 않는다면?' 같은 생각을 하는 버릇을 들이면 큰 도움이 됩니다.

 

이렇게 각 문제 유형별로 필요한 알고리즘이 무엇인지 공부하다보면, 일반적으로 웬만한 문제를 풀기 위해서 그렇게 많은 알고리즘을 알 필요는 없다는 사실을 알 수 있습니다.

다음과 같은 알고리즘만 제대로 알고 있어도 90%이상의 유형은 문제없이 해결할 수 있습니다.

 

자료구조

• 배열, 스택, 큐, 덱, Priority Queue, BBST(C++ set, map)등의 기본 내장 자료구조
• 그래프, 트리
• ★★★ Segment Tree ★★★
• Union-Find (Disjoint Set)

알고리즘

• 기본적인 DFS, BFS와 여기에서 파생되는 알고리즘(위상 정렬, Dijkstra 등)
• 이분 탐색, 투 포인터, 스위핑
• ★★★ Dynamic Programming ★★★
• (특히 문자열의) 해싱

그 외

• 소수와 최대공약수 등 기본적인 정수론 지식
• 중고등학교 수준의 수학 지식

 

이 친구들을 공부하고 언제든지 써먹을 수 있을정도로 익숙해지셨다면, 나머지 10%의 문제도 맞출 수 있도록 이 외의 다른 알고리즘을 공부하시면 됩니다.

 

알고리즘 자체를 아는것 보다 해당 알고리즘이 어떻게 응용되어서 쓰이는지를 학습하는게 더 중요하다는 사실을 잊지 맙시다.

예를 들어 SCC를 공부 했다면, 주로 2-SAT 문제를 푸는데 SCC가 사용된다는 것을 알아야 하며, 어떤 유형의 문제들을 2-SAT으로 변형하여 풀 수 있는지를 공부해야 합니다.

 

 

그래서 어떤 문제를 풀어야 하나요?

일단 알고리즘을 공부하고 싶으시다면, 백준 단계별로 풀기와 솔브닥 CLASS(~7)가 가장 좋은 것 같습니다.

분류도 잘 되어있고, 공부하기에 좋은 문제들이고, 푼 사람도 많아 도움을 얻기 좋기 때문입니다.

https://www.acmicpc.net/step

단계별로 풀어보기

https://solved.ac/class

solved.ac - 문제 › CLASS

 

 

대회, 즉 Competitive Programming를 준비하신다면 Codeforces(코드포스) 문제들을 푸시는걸 추천합니다.

https://codeforces.com/

Codeforces

단순히 PS가 아니라 대회를 준비하게 된다면, 우리에게 '시간'이라는 한 가지 더 제약이 생기게 됩니다.

그래서 다양한 난이도 분포의 여러 문제들이 주어졌을 때 이를 주어진 시간안에 풀어나가는 연습을 해야 하는데, 이를 일반적인 상황에서는 연습하기 힘듭니다.

 

하지만 코드포스를 참가함으로써 이에 대한 연습을 충분히 할 수 있게 되고, 나와 비슷한 사람들은 어느정도 풀었는지, 목표하는 실력이 되기 위해서는 어느정도 속도로 문제를 풀어야 하는지 알 수 있게 됩니다.

또한 본인의 레이팅이 실시간으로 오르내리는 것도 볼 수 있다보니 뚜렷한 목표의식도 생기게 됩니다.

 

대회가 열리는 시간대가 새벽시간이다보니 사람에 따라 많이 힘들 수 있습니다. 이를 위해 원하는 시간대에 가상으로 대회에 참가할 수도 있으니 알아두시면 좋습니다. 대회가 열리지 않을 때 연습용으로도 사용할 수 있습니다. 물론 대신 레이팅은 바뀌지 않습니다.

 

같은 이유로 Atcoder도 추천합니다.

https://atcoder.jp/

AtCoder

 

또는 굳이 이런 사이트가 아니더라도, 백준에서 이와 비슷한 문제 셋들을 찾아 시간제한을 두고 푸셔도 됩니다.

ICPC나 학교 대회 문제들도 좋고, USACO문제들도 좋습니다.

 

 

공통적으로, 문제들을 풀고 나서는 꼭 복기를 합시다.

 

문제를 손도 대지 못했다면 어떤 관찰을 못해서 그랬는지

WA를 맞았다면 내가 제출한 코드는 논리적으로 왜 틀리는지, 어떻게 고쳐야 하는지

TLE라면 시간복잡도를 올바르게 계산했는지, 또는 무한루프가 돌만한 부분이 있었는지

'왜' 틀렸는지를 알고, 다음에는 절대 그렇게 틀리지 않도록 노력해야 합니다. 그게 공부를 하는 이유입니다.

 

 

쉬운 문제 빨리 풀기

적당히 쉬운 문제(솔브닥 기준 실버 이하)를 아무거나 하나 골라서 풀어봅시다.

3분 이내에 풀이를 생각해 내고, 10분 이내에 구현을 끝낼 수 있나요?

 

대회를 준비하시는 분들이 종종 잊는 사실이 있습니다. 어려운 문제를 푸는 능력도 중요하지만, 쉬운 문제를 빠르게 해결하는 능력도 그만큼 중요합니다.

 

생각해보면 당연한 말입니다. 여러분은 제한시간 안에 많은 문제를 풀어야 합니다. 쉬운 문제들을 빠르게 해결해 놓은 다음, 대부분의 대회 시간은 어려운 문제에 투자해서 풀 확률을 높이는 것이 당연한 전략이 될 것입니다.

하지만 여러분이 어려운 문제를 풀 수 있다 하더라도 쉬운 문제에도 30분에서 1시간 정도의 시간이 걸린다면, 어려운 문제를 풀 기회조차 없어지게 됩니다.

 

그리고 조금 웃긴 말이긴 하지만, 빠르게 타자를 칠 수 있다면 이 점에서 역시 유리합니다.

 

 

해설은 언제 보면 되나요?

모르겠으면 바로 보면 됩니다.

 

여러분이 당장 풀이를 모르는 문제를 고민해서 대체 무슨 이득이 있나요?

그 고민하는 시간에 더 많은 문제를 보고, 유형을 익히고 공부하는게 훨씬 더 빠르게 실력을 올리는 방법입니다.

특히 대회를 준비하신다면 그렇습니다.

조금이라도 더 많은 문제를 보고 머릿속에 넣어 실력을 쌓아야 하는데, 한 문제가 안 풀린다고 1주일동안 고민해서, 심지어 그렇게 해서 답을 알아냈더라도 본인이 얻는 이득은 전혀 없습니다. 해설을 보면 그 사고 과정을 즉시 알 수 있으니까요.

 

한 10분 고민해서 모르겠으면 해설을 봅시다. 아무리 길어도 2시간은 넘길 이유가 없습니다. 푼 다음에 출제자 등 다른 사람들의 코드도 참고합시다. 더 효율적으로 구현한 코드를 보고 공부할 수 있습니다.

 

 

 

문제는 하루에 어느정도 풀면 될까요?

 

 

보고 공부할 책을 추천해 주세요

필요 없습니다.

 

여러분이 구글에 비스무리한 키워드만 쳐도 관련한 블로그 포스팅이 많이 나오는데, 그걸 보고 공부하시는게 훨씬 효율적입니다.

물론 책을 보고 하고 싶어하는 분들이 이해가 안되는건 아닙니다. 저도 데이터 쪼가리보다는 인쇄물이 더 좋거든요.

 

파란책 - 설명이 자세하고 차근차근 공부할 수 있습니다. 다만 쓸데없는 잡내용이 꽤 많고, 이 책에 연결되어 있는 Online Judge 사이트가 메우 불편합니다. 제가 공부할 때는 이 책으로 공부했습니다.

http://www.yes24.com/product/goods/42415865

알고리즘 트레이닝 : 자료 구조, 알고리즘 문제 해결 핵심 노하우 - YES24

초록책 - 전체적으로 알고리즘을 어떤 방향으로 공부해야 하는지 틀을 잘 잡아줍니다. 그런데 뒤로 갈수록 설명이 없다시피합니다.

http://www.yes24.com/product/goods/72274740

알고리즘 트레이닝 : 프로그래밍 대회 입문 가이드 - YES24

종만북 - 지금도 알고리즘 하겠다고 하면 이 책을 사시는 분들이 많습니다. 실제로 설명 퀄리티도 좋고, 연결된 OJ 사이트도 나쁘지 않은데 (https://algospot.com/), 아무래도 오래된 책이다 보니 요즘 PS 트렌드와는 맞지 않는 내용이 꽤 있습니다.

http://www.yes24.com/product/goods/8006522

알고리즘 문제 해결 전략 세트 - YES24

 

 

마치면서

이쪽 공부를 혼자서 끙끙대고 하는건 정말, 엄청나게 힘든 일입니다.

가능하면 멘토를 해줄 만한 사람 한 명 정도, 그런 사람도 없다면 같이 공부하는 사람들정도는 만들어 놓는게 정신건강에 좋습니다.

 

그리고 여러분이 이 분야에 발을 들인 이상, 죽을 힘을 다해 노력하셔야 합니다.

개발 같은 경우 여러분이 하다가 결과가 좋지 않아도 뭔가 노력해서 개발을 한 흔적이 남지만, PS는 결과가 좋지 않으면 모 게임에서 1000만원 쓰고 무과금인것처럼 n년 공부하고 무수상으로 남을 수 있습니다. 이력서에 solved.ac 플래티넘 Codeforces 블루 써놔도 아무도 몰라요.

 

PS 탈출은 지능 순입니다. 여러분이 이루고 싶은것 빠르게 이루고 빠른 탈출하시길 기원합니다.

 

 

진짜 마지막으로 또 참고할만한 갓님들의 글 소개합니다.

 

https://baactree.tistory.com/52
https://koosaga.com/217
http://wookje.dance/2019/04/16/how-to-study-algorithm/
https://subinium.github.io/how-to-study-problem-solving/