백준 알고리즘 공부 방법 - baegjun algolijeum gongbu bangbeob

최근 알고리즘을 공부해야겠다는 생각이 부쩍 들었다. 우선은 무엇을 어떻게 공부해야 하는지 알아야 할 것 같아서 자료를 찾아보았다. 앞으로 아래의 내용을 참고하여 꾸준히 공부해보려고 한다.

알고리즘 문제

코드업: 기초 100제
백준 온라인 저지: 삼성
코드포스 - 블루레벨 정도의 실력까지.
탑코더 알고리즘 튜토리얼: 초심자 추천
프로그래머스: 카카오
알고스팟
코딩도장
Hackerearth
Hackerrank

알고리즘 공부 방법

• 기본 개념/문법 이해하기
  • 책
  • 인터넷
    • LibreWiki: 이론 한 눈에 정리
    • visulgo: 정렬, 트리 등 원리 시각화
    • Geeksforgeeks
    • 기본 코드 학습: Geeks for Geeks 풀이 샘플
  • 앱
    • 알고리즘 도감
    • Geeksforgeeks
• 기본 알고리즘 코드 학습하기
• 백준에서 아래의 문제를 50문제씩 풀어보기
  • 그리디 알고리즘 문제
  • 탐색 문제(완전 탐색, BFS, DFS)
  • 기본 동적 프로그래밍
  • 기출문제

고급

• 그래프이론
• 중급 및 고급 동적 프로그래밍
• 문자열

알고리즘 기본 개념

• 시간 복잡도(중요! 계산해보아야 함)
• 자료구조: 선형/비선형
• 정렬

좋은 알고리즘의 조건

• 입력: 외부에서 제공되는 자료가 0개 이상 존재
• 출력: 적어도 2개 이상의 서로 다른 결과를 내야 한다.
• 명확성: 수행과정은 명확하고 모호하지 않은 명령어로 구성된다.
• 유한성: 유한 번의 명령어를 수행한 후 유한 시간 내에 종료한다.
• 효율성: 모든 과정은 명백하게 실행가능(검증 가능)한 것이어야 한다.

책

• 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략(종만북)
• 프로그래밍 콘테스트 챌린징(노란책)
• Competitive Programming 3 by Steven Halim
• Introduction to Algorithms(CLRS)

문제 푸는 방법

1. 시간을 정해놓고, 그 시간을 넘겨도 못 풀면 답을 본다. 처음에는 많은 풀이와 사실을 아는 게 더 중요하다.
2. 적정 난이도의 문제: USACO 추천
3. 다른 사람의 코드를 본다. 좋은 코딩법을 배울 수 있고, 코드를 읽고 이해하는 능력을 키울 수 있다.
4. 풀이를 논리적으로 설명할 수 있을 때 코딩을 한다.

기타

• 언어는 C++, Python
• 책을 정독하고 본인의 언어로 개념을 알 때까지 구현한다.
• 내 말로 설명하자: 글이나 말로 설명한다.
• 알고리즘은 내 언어로 추상화해서 기억
• 직접 코드를 짜서 확인해본다. 반복 숙달, 디버깅 능력
• 문제 유형과 풀이를 세분화한다. (예: DAG에서 최장경로 구하기, 트리의 지름 구하기 등)

• 참고 자료
  https://www.youtube.com/watch?v=ukkLCl9yBvE
  https://www.slideshare.net/startlinkio/startlinklive-algoshipda
  https://blog.yena.io/studynote/2018/11/14/Algorithm-Basic.html

• 공부 후기 참고: https://qkqhxla1.tistory.com/990

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

어제 "백준 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를 이어나갈 것입니다.

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