[알고리즘 공부팁] 1. 처음 알고리즘 공부를 시작하는 분들에게

본 글은 초보자 및 중급을 위한 글입니다. 코드포스 퍼플 이상 분들은 허허 웃으며 지나가 주시면 됩니다.

제 PS 생활을 소개하자면...

• 대학에 입학하고(2016년) 3월부터 C언어 기초를 시작했습니다.
• 대학 생활동안 3년 정도 PS를 했고, 꾸준하게 했지만 집중적으로 공부한 기간은 한 1년 반정도 됩니다.
• 사이트에서 푼 문제 수를 합하면, 4000문제 가량 문제를 풀었습니다. (BOJ 3000 + dovelet 650 + Project Euler 180 + @)
• 학과 알고리즘 동아리에서 회장을 맡았으며, 2018 고려대학교 프로그래밍 경시대회를 출제/운영했습니다.
• 전국대학생프로그래밍대회동아리연합에서 회장을 하며 UCPC2019를 주최했습니다.
• 2018/2019년에는 SCPC 본선 진출을 했고, 2018 ACM-ICPC 서울 리저널에서 장려상을 받았습니다.
• 종종 알고리즘 및 코딩테스트 강의를 이곳저곳에서 하고 있습니다.

푼 문제 수에 비하면 CP는 여전히 부담스럽고, 실력이 부족하지만 이렇게 글을 올려봅니다.
이미 아래와 같이 고수분들의 좋은 글들도 많아 부끄럽긴 하지만 제 경험을 녹인 글이니 좋게 읽어주세요. 😃

• baactree님의 알고리즘 공부, 어떻게 해야하나요?
• koosaga님의 내가 문제풀이를 연습하는 방법

I. PS란?

PS(Problem Solving)는 주어진 문제를 정해진 언어를 통해 시간 제한과 메모리 제한에서 해결하면 됩니다.
제 주변 대부분의 케이스는 코딩테스트나 알고리즘 문제 해결 대회를 위해 공부합니다.

언어는 보통 C, C++, Java를 많이 사용합니다. 저는 C로 코딩을 시작했고, STL을 위해 C++을 사용하는 케이스입니다.
C++을 추천하는 이유는 코딩테스트의 문제의 경우에는 정해진 시간내에 해결해야하며 시간제한 내에 문제를 해결해야하기 때문입니다.

추가로 말하자면 PS에서는 C++을 사용한다고 객체 지향의 특성을 살리며 코딩을 할 필요는 없습니다.
Class를 선언하고, 이를 활용하여 코드를 작성하는 것은 좋은 습관이지만 PS를 시작하고 코딩테스트를 준비하는 분들에게는 굳이 필요하지 않은 작업입니다.

II. PS에 필요한 2가지 능력

PS/CP는 결국 프로그래밍이고, 프로그래밍에 있어서 Accepted를 받기 위해서는 2가지가 필요합니다.
이런 2가지 능력을 키울 수 있기 때문에 PS를 공부하고, PS 능력을 테스트를 통해 확인하는 것 같습니다.

1. 문제 해결 능력

또다른 말로는 솔루션을 찾는 능력 이라고도 합니다.
문제를 해결하기 위해서는 문제에 필요한 지식이 있어야 합니다.
자료구조, 알고리즘, 해결tip, 수학적 사고 모든 것이 이에 속합니다.

2. 구현 능력

구현 은 자신이 알고 있는 것을 프로그래밍 언어로 변환하는 것입니다.

문제에 정답을 구하는 방법을 알더라도, 구할 줄 모르면 아무 의미가 없습니다.
팀 대회의 경우에는 좋은 역할이 될 수 있지만, 대부분의 대회 또는 코딩테스트는 혼자서 모든 것을 해내야 합니다.

코딩 테스트의 경우에는 STL이 사용불가능 한 경우도 있으니 구현 능력이 더 중요하겠죠?

II. 그럼 PS/CP는 어떻게 연습을 해야할까요?

그럼 이제부터 제 경험을 바탕으로 연습법에 대해서 말씀드리겠습니다.

저도 다 실천하는 것은 아니고, 실천하려고 노력하는 중입니다. 😃

0. 공부가 우선이다.

공부를 하지 않고 문제를 푼다는 것은 알파벳의 존재를 알고 영어 회화를 하는 아기를 바라는 것과 같습니다.
적어도 기본적인 문법, 자료구조, 알고리즘 등은 공부를 해야합니다.

이 경우, 백준님의 알고리즘 강의도 좋습니다. 너무 비싼 강의는 돈 낭비입니다. 차라리 유튜브 강의를 듣는게 더 나을 수도 있습니다.

제 유튜브가 아니더라도 시중에는 좋은 책이 많고, 좋은 강의가 많습니다.
그렇기 때문에 문법과 기초적인 베이스 지식은 검색을 하던, 책을 읽던, 강의를 듣던 어떤 방식으로도 공부가 우선입니다. 최근에는 워낙 많은 책이 나와서 모르겠지만, 역시 종만북 만큼 추천을 많이 받은 책은 없는 것 같습니다.

초심자가 읽기 어려운 감이 있지만, 그래도 설명이 비교적 자세하고 기본 이론을 학습하기에 좋은 책입니다.

연습만 해서는 알고리즘의 사용 폭을 넓히는 것이 어렵습니다. 아래의 연습 방법들과 함께 꾸준한 알고리즘 공부를 병행해야만 알고리즘 실력 향상을 기대할 수 있습니다.

1. 양보다는 질

양보다는 질이다.

문제는 양보다는 질입니다. 좋은 문제를 풀어야 실력이 늘 수 있습니다.
제가 질보다는 양을 선택했던 케이스이기때문에 더 말씀드릴 수 있는 것 같습니다.

알고리즘을 해결하기 위한 능력 중 가장 필요한 능력 중 하나는 위에서 말했듯이 솔루션을 찾는 능력 이라고 생각합니다.
솔루션을 찾지 못한다면, 시간이 있어도 문제를 해결할 수 없습니다.

솔루션을 찾는 능력을 키우기 위해서는 새로운 접근법 을 가진 문제와 여러 접근법을 함께 사용하는 방법 을 배울 수 있는 문제가 좋습니다.

좋은 문제의 선별은 풀어봐야 압니다. 하지만 연습하는 단계에 계신 분들은 하나하나 그렇게 풀다보면 시간 낭비일 수 있습니다. 그렇기 때문에 이미 검증된 문제를 푸는 것은 매우 좋은 방법입니다.

이런 검증된 문제셋에 대한 정보는 위에서 언급한 koosaga님의 내가 문제풀이를 연습하는 방법을 참고하면 좋을 것 같습니다.
난이도가 있는 문제셋을 추천해주시긴 했지만 이 중에서도 저는 다음 셋들을 추천합니다.
후에 다른 포스팅에서도 추천하겠지만 여기서 간략하게 말씀드리면 다음과 같습니다.

• USACO

미국 정보올림피아드 국가대표를 뽑기 위해 사용되는 문제들로 bronze부터 platinum까지 4단계 각 3문제로 이루어진 문제셋입니다. 문제 퀄리티가 좋습니다.

기본적으로 난이도가 높긴 합니다. 하지만 어느정도 실력이 된다면 bronze~silver 초반까지는 풀 수 있을 것입니다. 조금씩 난이도를 높여가며 문제를 해결하는 것을 추천합니다.

공식 페이지에는 모든 solution이 공개되기 때문에 공부에 적합합니다.

• 한국정보올림피아드

한국정보올림피아드 문제는 기본적으로 DP, 그래프 등 전형적인 알고리즘 문제 해결 능력을 키우는 데 도움이 됩니다. 처음하시는 분들은 초등부 문제도 처음에 벅찰 수 있습니다. 하지만 하나씩 풀다보면 실력을 키울 수 있습니다.

• AtCoder

대부분의 분들이 칭찬하는 대회 사이트입니다. 난이도가 전반적으로 높지만 풀이가 제공되고, 대회 플랫폼 중 시간대가 가장 한국인 생활 패턴에 잘 맞다는 장점이 있습니다. 초보분들은 ABC, 중/상분들은 ARC 문제를 보면 됩니다.

• Codeforces

Named에는 이유가 있습니다. 문제 출제자에 따라 지문의 상태가 엉망이거나, 난이도 분포가 미쳐버린 경우도 있지만 대부분의 세트는 괜찮습니다. 후에 아래에 말할 목표 설정에서 목표를 설정하기 용이하고, 버츄얼 대회 등 다양한 기능이 있어 좋습니다. 풀이도 제공되고, 대회의 경우에는 맞춘 분들의 소스코드를 볼 수 있어 배울 점이 많습니다.

준비하는 대회에 따라 성향이 다르니, 기출을 푸는 것도 좋은 방법입니다.

2. 하지만 많이 푸는 것은 도움이 된다!

랭작도 좋은 랭작을 하자

아무리 솔루션을 잘 찾더라도, 구현을 할 수 없다면 이것도 무용지물입니다.
또한 구현할 줄 알아도 속도가 느리다면 대회 제한 시간 내에 문제를 해결하지 못할 수 있습니다.

코딩 테스트를 준비하는 분들이라면 DFS/BFS, 백트래킹, 정렬 등 시뮬레이션 위주 의 구현 문제를 많이 연습해야합니다. 최근에는 DP, 분할 정복 문제의 비율도 높고 난이도도 어렵습니다.

구현 능력을 키우는 데 가장 좋은 것은 많이 푸는 것입니다.
많이 푸는 것도 좋은 문제를 많이 풀면 좋겠지만, 기본적인 문제를 많이 푸는 것도 구현 능력 향상에는 좋습니다.

하지만 이런 많이 푸는 것에도 2가지 방법이 있습니다.

1. 랭킹을 위한 문제 해결 a.k.a 랭작(랭킹을 위한 작업)
2. 처음부터 코드를 작성하는 문제 해결

1번에서의 의미는 다음과 같은 행동을 의미합니다.

• 인터넷에 올라와있는 솔루션 소스 그래도 복사+붙여넣기+제출
• 내가 구현한 소스 복사+붙여넣기+제출

이런 행위는 할 수 있다고 생각합니다. (지나치게 하는 순간 검열됩니다.^^) 하지만 본인의 실력을 위해서라면 하지마세요.
저도 답답하면 인터넷에서 솔루션 소스를 그대로 넣을 때가 있습니다.
하지만 이런 코드 작성법은 절대로 늘지 않습니다.

어느 정도 언어는 익숙한데, 코딩이 막히시는 분들은 다음과 같은 랭작을 추천합니다.

• 내가 30분 내로 코딩할 수 있는 문제
• 풀이를 알고, 구현만 남은 문제

저 같은 경우는 랭작을 하는 날에는 문제를 하루에 15개 내외로 풀었던 것 같습니다.
이정도로 하기는 일상에 영향을 미치기도 하고, 생활과 병행하기에는 5문제 내외가 적당할 것 같습니다.

위에서 추천한 셋에서 랭작을 하는 것도 좋은 방법입니다. (USACO Bronze, 정올 초등부, AtCoder/Codeforces 쉬운 문제 해결하기)

그 외에는 BOJ에서 @automata 님이 만든 문제집인 C++ 배우기(1~50) 에서 C++ 배우기(351~400) 를 추천합니다. 유사품으로 Python 배우기 시리즈도 있습니다.

이 외에도 BOJ에는 공개된 다양한 문제집들이 있습니다. 괜찮은 문제들이 많으니 문제집을 잡고 공부하는 것도 좋은 방법입니다. 하지만 때에 따라 문제집에 빌런이 있으니 이건 아니다 싶은 문제는 버리세요.

제 경험상 1000명 이상이 해결한 문제는 랭작 수준의 난이도 입니다. (삼성 코딩테스트 문제 + 백준님 강의 문제를 제외하고는 그렇습니다. 코딩테스트는 기출을 푸는게 제일 좋습니다.) 그렇기에 1000명이상이 푼 문제들은 북마크를 해서 모아둘 수도 있고, 500명 이상이 푼 문제 중에서 해답이 떠오르는 문제를 북마크해서 풀 수도 있습니다.

3. 오래 붙잡고 있는 것은 결코 도움이 되지 않는다.

한 문제를 오래 붙잡는 경우, 좋은 공부가 될 수 있겠지만 개인적으로는 시간낭비라고 생각합니다.
여기서 붙잡는다는 것은 솔루션이 떠오르지 않아 아무 진척도 없는 단계 를 의미합니다.

코딩 테스트나 대회와 같은 실전에는 계속 붙잡고 있는게 맞습니다.

제 기준의 오래 는 약 1시간 정도입니다. 그 이상의 고민은 실력 향상에도 도움이 되지않고, 본인의 실력이 아직 충분하지 않다는 것입니다. 이럴 때는 해답을 보는 것을 추천합니다.

그렇다고 solution을 그대로 내는 것, 보고 받아쓰기 하는 것은 절대 안됩니다.
그렇게 하는 순간, 그 문제는 앞으로 안볼것이고 그 문제에서 얻을 수 있는 지식은 여러분의 것이 아니게 됩니다.

솔루션을 보고도 이해하지 못한다면, 이를 위한 내용을 공부하거나 문제를 보류하는 것을 추천합니다.
저는 빨간 글씨의 틀렸습니다를 보고 싶지 않아요~ 같은 소리는 하지 맙시다.
빨간 글씨가 억울하면, 억울한만큼 열심히 공부해야하는 겁니다.

결론적으로 솔루션을 보고 코드를 본다면, 자신이 안보고 코드를 작성해서 제출해야 합니다.

솔루션 제공되는 문제들은 많고, 푼 사람이 꽤 많은 문제는 블로거 분들이 대다수 포스팅 했을 것입니다.
연습할 때는 솔루션이 제공되는 대회/분류의 문제를 푸는 것을 추천합니다.

4. 좋은 멘토와 질문

이끌어 주는 자가 있다면 따르자.

실력이 제일 쉽고 편하게 향상 시키는 방법은 좋은 선생님과 함께하는 것입니다.
학교 동아리에 소속된 분들이라면 실력있는 선배에게 배우는 것이 가장 좋습니다.

그 외에도 주변 스터디를 통해서 나보다 잘하는 사람 에게 배우는 것이 가장 좋습니다.
잘하는 사람 은 후배, 동기일 수도 있고, 모르는 사람일 수도 있습니다.

주변에 도움을 받을 사람이 없다면, 백준 슬랙을 추천합니다. 저도 많이 도움을 받았던 공간이며 언제나 고수분들이 상주하고 계십니다.
백준 슬랙을 포함해 QnA에서 질문에는 룰과 도덕이 있으니 이와 관련해서는 꼭 공지를 읽고, 질문하는 것을 추천합니다.

이 포스팅을 통해 @Nyan101 @ltg2030 @wclee2265 에게 감사의 말을 전합니다.

5. 구체적인 목표 설정하기 / 스스로의 기준 설정하기

뚜렷한 목표는 여정의 힘듦을 잊을 수 있는 방법이다.

rank 또는 rating을 목적으로 하는 것은 좋은 방법입니다.
저는 항상 목표는 rank였습니다.

저는 Dovelet 30위안에 들자 목표가 첫 목표였습니다. 이 당시에는 3개월간 약 600 문제 가량을 해결했습니다.

입문하시는 분들은 문제수, 사이트 랭킹, 코드포스 레이팅 등으로 목표를 설정하고 그에 맞는 연습을 하는 것이 좋습니다. 목표를 설정하면 앞으로 해야하는 공부가 보일 것입니다.

제 경우는 실력보다는 공부에서 오는 재미와 (새내기와 동아리 구성원을 위한) 강의가 더 중요했고, 대회 플랫폼이 싫었기에 오히려 문제수나 랭킹에 더 초점을 두었습니다.

제 지인 분들 중에 실력이 정말 빠르게 느신 분들의 경우에는 모든 코드포스 참가하기 + 퍼플/오렌지 찍기 라는 목표를 가지고 있었습니다. 그리고 그 분들은 실천을 통해 목표를 이루었습니다.

직장인의 경우에는 출근의 문제로 어려운 방법이지만, 각자의 위치에서 목표를 가지고 연습을 하는 것이 중요합니다.

목표는 비교적 빨리 이룰 수 있는 부분을 세워야 합니다. 1년에 한번 있는 대회(SCPC, ACM-ICPC)와 같은 목표는 오히려 공부 욕구를 낮출수도 있습니다. 목표를 세분화하여 하나씩 나아가는 과정이 중요합니다.

6. 배움의 끝은 나눔 : 함께 공부하세요.

혼자만 공부하면 +1이지만, 함께 공부하면 +n 입니다.

함께 공부하는 방법은 다양하지만 저는 2가지를 추천합니다.

• 블로그
• 스터디

블로그를 작성하며 자신의 실력을 정돈하는 것도 좋은 방법입니다.
후에 자신이 푼 문제를 다시 리뷰할 수도 있고, 여러모로 좋은 방법입니다.

알고리즘을 포스팅하는 블로거분들이 대회를 여는 경우도 있었습니다. 그 분들은 모두 실력도 좋고 포스팅도 잘하십니다.😃

스터디를 통해 함께 공부하는 것도 좋습니다. 동아리도 좋습니다.
스터디에서는 선의의 경쟁자를 두는 것도 좋은 방법이라고 생각합니다.

저도 PS 초반에는 동아리원보다 푼 문제수가 적은 것은 스스로 용납이 안되어, 밤새 랭작을 하고는 했습니다. 그 결과 둘 모두 실력이 엄청 빨리 늘기도 했습니다.

스터디를 하면 경쟁뿐만 아니라, 서로의 문제 접근 과정에서 배울 점이 많고 시너지를 만들 수 있는 요소가 많습니다. 서로가 멘토가 되어 나아가는 것도 좋은 방법입니다.

III. 마무리

PS를 공부하다보면 힘든 순간들이 많습니다. 스스로에 대한 한계를 느낄 때도 있고, 답답하기도 하고...

그런 분들에 제가 해답은 줄 수 없지만, 도움을 줄 수 있는만큼은 주고자 합니다.

모두 행복하게 공부하길 바랍니다.

감사합니다. 😃