알고리즘 공부를 어떻게 시작해야할까? (Feat. 백준 500문제 푼 기념으로 적는 PS 회고록)

안녕하세요? 코딩중독입니다.

 

 

어제 "백준 6219번 소수의 자격" 문제를 풀었고, 이것이 저의 500번째 푼 문제가 되었습니다.

 

 

 

 

물론, 아직 세자리수 등수에 들지 못하였고, 다른 분들이 보기에 많은 문제는 아니라고 생각할 수 있으나, 저에게 있어서 500문제는 의미가 꽤 큽니다.

 

올해 세운 목표가 500문제를 푸는 것이었고, 오늘은 목표를 달성한 기념으로 저의 PS 회고록을 적으려고 합니다.

 

 

PS에 빠지게 된 이유

제가 PS에 빠지게된 이유는 간단합니다. 바로, '열등감'때문이었죠.

 

저는 대학교에 들어가서 처음 프로그래밍을 접했습니다. 그리고 1학기는 C, 2학기는 Java와 C++, Python을 배웠습니다.

 

처음에는 내용이 어렵지 않아서 수업을 곧잘 따라갔지만, 시간이 지날수록 포인터, 객체지향프로그래밍, 제네릭과 컬렉션 등 난이도 높은 내용은 이해하는 데 많이 어려움을 느꼈습니다.

 

그래서 알고리즘을 공부하기보다는 프로그래밍 언어 과목을 따라가기 급급했습니다. 과제도 다른 사람들에 비해 해결하는 시간이 오래 걸렸고, 지금 생각해 보면 효율적인 코드보다는 어떻게든 결과를 돌아가게만 만든 좋지 못한 코드를 작성했던 것 같습니다.

 

그러한 상황에 저는 마음이 맞는 친구와 알고리즘 동아리에 들어가면서 브루트포스, 그리디 알고리즘, DP 등 여러 가지 알고리즘 기법을 배웠습니다.

 

또한, 그 기법으로 백준 문제를 풀기도 하였는데 저는 그 중에서 해결한 문제가 거의 없었습니다.

 

반면, 제 주변 동아리원들은 대부분 기법을 이해하고 문제를 어느 정도 푸는 것 같았습니다. 저와 같이 동아리에 들어간 친구들도 마찬가지였고, 점점 자신감을 잃어갔습니다.

 

그렇게 제 자신에게 열등감을 느꼈고, 이것은 오히려 PS에 빠지는 기폭제로 작용하였습니다.

 

 

PS를 공부한 방식

PS를 열심히 공부하겠다고 생각하였으나, 정작 무엇부터 시작해야하는지 감이 쉽게 잡히지 않았습니다.

 

저는 나름대로 커리큘럼을 세우기 위해서 구글링을 해 보았고, 정말 귀중한 블로그를 찾게 됩니다.

 

plzrun님의 블로그로, 특히 이 게시글에서 도움을 매우 많이 받았습니다.

 

plzrun님은 백준 강의를 추천해 주셨는데, 저는 8~9만을 낼 거금은 없었기에 포스팅에 나와 있는 커리큘럼을 따라 가기로 하였습니다.

 

입출력 방식에서 시작해서, 기초 자료구조, 기초 수학, DP, 정렬, 그래프, 이분탐색, 분할정복, 그리디, 완전탐색으로 끝이 납니다.

 

자세한 문제 커리큘럼은 아래와 같습니다.

 

 

 

입출력 - 2557, 1000, 2558, 10950, 10951, 10952, 10953, 11021, 11022, 11718, 11719, 11720, 11721, 2741, 2742, 2739, 1924, 8393, 10818, 2438, 2439, 2440, 2441, 2442, 2445, 2522, 2446, 10991, 10992

 

DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052

 

정렬 - 2751, 11650, 11651, 10814, 10825, 10989, 11652, 11004

 

스택 - 10828, 9012, 10799

 

큐 - 10845

 

덱 - 10866

 

문자열 처리 - 10808, 10809, 10820, 2743, 11655, 10824, 11656

 

기타 자료 구조 - 1406, 1158, 1168

 

기초 수학 - 10430, 2609, 1934, 1850, 9613, 11005, 2745, 1373, 1212, 2089, 11576, 1978, 1929, 11653, 10872, 1676, 2004, 6588  

 

그래프 - 1260, 11724, 1707, 10451, 2331, 9466, 2667, 4963, 7576, 2178, 2146, 1991, 11725, 1167, 1967

이분탐색/삼분탐색 - 1654, 2805, 2110, 10815, 10816, 11662

분할정복 - 11728, 1780, 11729, 1992, 2447, 2448, 1517, 2261

그리디 - 11047, 2875, 10610, 1783, 1931, 11399, 2873, 1744 

완전탐색 - 1476, 1107, 1451, 9095, 10819, 10971, 1697, 1963, 9019, 1525, 2251, 2186, 3108, 5014, 1759, 2580, 1987, 6603, 1182, 2003, 1806, 1644, 1261, 1208, 7453, 2632, 2143

 

 

이 문제를 모두 풀어보는 것이 알고리즘의 기초라고 생각합니다.

 

그리고 알고리즘 기법을 새로 배우기 위해서는 백준 강의말고 인프런 강의를 참고하였습니다.

 

권오흠 교수님의 강의인데, 처음에 개념을 익히기 좋습니다. 링크는 이곳이 되겠습니다.

 

정리하자면, 처음에 개념을 인프런 강의에서 배우고, 구글링을 통하여 개념을 다시 한 번 학습한 다음에 plzrun님의 커리큘럼을 따라가는 방식으로 공부를 시작했습니다.

 

 

PS를 공부할 때 주의 사항

plzrun님이 말씀하신 것과도 유사한데, 한 문제에 무조건적으로 몇 시간 이상을 때려 박는 것은 비효율적입니다!!

 

특히, 어떠한 개념을 처음 배웠을 때는 그것을 바로 응용하는 것은 매우 어려운 일이므로, 초반에는 해답을 보면서 푸는 것이 좋습니다. 그리고 그 방식이 장기적으로 오히려 효율적입니다.

 

물론, 어느 정도 기법을 익히고 나서 하나의 문제가 될듯 말듯 안 되는 느낌이 있는 것이라면 어느 정도 시간을 사용하여 풀어내는 것이 의미있겠지만, 제 개인적으로 그것도 1시간 ~ 2시간이 넘어간다면 답의 힌트를 얻기를 바랍니다.

 

그리고 그 힌트를 다른 블로그에서 읽어도 모르겠다면, 조금 더 힌트를 얻는 식으로 단계적으로 해답을 보는 것이 좋습니다. 또한, 그 문제는 풀더라도 반드시 다른 사람의 코드를 참고해야겠죠?

 

마지막으로, 처음 문제를 보고 아예 접근 방식이 떠오르지 않았을 때가 있습니다.

 

저는 커리큘럼을 따라갈 때는 그 문제를 우선 패스하였습니다. 뒤에 있는 문제에서 힌트를 얻어서 풀 수도 있기 때문이죠.

 

하지만, 이 문제를 풀어야 뒤에 문제를 풀 수 있는 경우, 다른 사람의 풀이에서 단계적으로 힌트를 얻습니다. 위에서 언급한 것과 마찬가지죠.

 

커리큘럼을 따르지 않고, 자유롭게 문제를 풀 때도 동일합니다. 충분히 고민을 하였음에도, 아예 갈피가 잡히지 않을 때는 주저 하지 않고 단계적 힌트 방식을 따르시길 바랍니다.

 

 

이후에 어떻게 공부해야 하는가?

사실 위 커리큘럼을 성실히 따라갔다면, 알고리즘의 기초는 잡혀 있다고 해도 무방합니다.

 

이제부터는 본인이 필요하거나 하고 싶은 길을 따라가면 됩니다.

 

만약, 알고리즘이 생각보다 재미가 있거나, 좀 더 어렵고 다양한 개념을 익히고 싶다면 '종만북'을 구매하여 공부하는 것입니다. 참고로, 종만북은 알고리즘 문제 해결 전략 세트 (프로그래밍 대회에서 배우는,전2권)을 줄여서 말합니다.

 

여담으로, 알고리즘 문제 해결 전략 세트 (프로그래밍 대회에서 배우는,전2권)에서 종만이라는 글자가 없는데 왜 종만북이라고 부르는지 의문이 생기실 수 있는데, 그것은 이 책의 저자가 구종만이기 때문이죠.

 

그외에, 본인이 코딩테스트 준비가 시급하다면 바로 코딩테스트 기출 문제를 풀어 보면서 준비하시면 됩니다.

 

위 커리큘럼으로는 자료 구조나 그래프, 그리디적인 사고가 부족할 수 있으나, 충분히 PS 경험을 쌓았기 때문에 새로운 개념을 배우고 응용하는 것에는 어려움이 없을 겁니다.

 

 

정리

많은 사람들이 PS를 어려워하고 기피하려고 합니다. 하지만, 기업에서는 점점 코딩 테스트라는 제도를 도입하기때문에 어느 정도 알고리즘 문제 해결 능력을 갖추어야 하죠.

 

저 또한, PS가 많이 힘들었고 왜 해야하는지 잘 몰랐습니다. 그래도 포기하지 않고 정말 하루도 빠짐없이 문제를 풀었고, 그 과정에서 새로운 것을 알아가는 즐거움과 오랜 시간 노력한 문제를 해결한 희열감은 이루 말할 수 없을 정도였죠.

 

그래서 겨울방학 2개월만에 위 커리큘럼을 전부 해결했으며, 올해는 종만북과 더불어 다양한 알고리즘 대회에 참여하였습니다. 또한, 실제 기업의 코딩테스트를 치르면서 구현 능력을 많이 기를 수 있었습니다.

 

그럼에도, 제가 배워야할 내용은 무궁무진하기때문에 500문제에서 그치지 않고, 앞으로도 계속해서 PS를 이어나갈 것입니다.

 

아무쪼록, 알고리즘 공부를 처음 시작하시는 분이 제 포스팅을 통해 방향성을 잡기를 희망합니다.