본 글을 작성하는 필자는 PS에 능하지 않으며, 모 기업 인턴 코딩테스트에 나온 문제를 전부 풀고도 합격하지 못한 전례가 있습니다. 따라서, 본 글에 적힌 공부방식 및 팁을 전적으로 신뢰하지는 마시기 바랍니다. 비판적인 태도로 해당 글을 읽고 본인에게 필요한 부분만 취해갈 수 있도록 해주시면 감사하겠습니다.
2021.05.12 : (3. 언어에 관한 이야기) 추가
2021.05.13 : 분류체계 수정(String 유형 추가)
2021.05.17 : 개요 및 분류체계 설명 수정 (Queue and stack에 deque 추가)
2021.05.19 : 분류체계 수정
2021.09.23 : 분류체계 수정(Prefix sum 유형 추가 및 개요 수정), How_To_Study.md 수정 (분류체계 및 말.말.말 업데이트)
2021.09.28 : 말, 말, 말. 업데이트
2021.09.28 업데이트를 마지막으로 본 레포의 업데이트를 종료합니다. 이와 함께 모든 풀 리퀘스트를 허용하며, 본 레포에서 필자가 작성한 모든 부분의 저작권을 티지윙에 양도합니다. (링크로 걸려있는 게시글은 당연히 제외입니다.) 따라서 원하시는 분들이 원하는 대로 수정하고 업데이트 해주시기 바랍니다.
본 글은 다음과 같은 순서로 필자의 알고리즘 공부 방식을 소개합니다.
- 필요한 사전지식
- 알고리즘 분류
- how to practice?
- 추천자료
- 말, 말, 말.
알고리즘 문제 해결(이하 PS)은 단순히 프로그래밍 언어를 안다고 해서 쉽게 접근 가능한 영역은 아닙니다. 필자가 생각하는 PS의 정의는 '수학적, 컴퓨터공학적 지식을 프로그래밍 언어로 녹여내어 문제를 해결하는 분야' 입니다. 그리고 이중에서도 컴퓨터공학적 지식에 조금 더 집중되어있다고 생각합니다.
PS는 기본적으로 문제(정확히는 문제 채점 서버)에서 입력하는 데이터를 문제에서 요구하는 방식으로 정제하고 처리하여 답안을 도출하는 방식으로 진행됩니다. 이는 입력 데이터를 적절하게 저장할 수 있고, 가공할 수 있으며, 출력할 수 있어야 함을 의미합니다. 이부분이 바로 PS를 공부하시는 분들이 쉽게 간과할 수 있는 내용입니다.
데이터를 적절하게 저장할 수 있으려면 데이터 저장에 사용될 자료구조를 현명하게 선택해야 합니다. 데이터를 제대로 가공하려면 가공하려는 방식에 알맞는 알고리즘 이론을 빠르고 정확하게 떠올려야 합니다. 또한 데이터를 가공하는 과정에서 늘어나는 시간복잡도와 공간복잡도를 정확하게 계산하고 제어할 수 있어야 합니다. 데이터를 문제의 요구방식대로 출력하려면 가공된 답안을 정확하게 정리해줄 프로그래밍 기본기가 필요합니다.
즉, 자료구조, 알고리즘 배경지식, 프로그래밍 기본기 등의 이론적 바탕이 일정수준 이상으로 닦여 있어야만 본격적인 PS가 가능하다는 뜻입니다. 만약 본인이 이러한 부분에 있어 많이 미흡하다고 생각되면 잠시 PS를 멈추고 기본으로 돌아가는것도 좋은 선택이 될 수 있습니다.
기본적인 컴퓨터공학적 이론을 어느정도 쌓았다면, 이제는 코딩 테스트에 주로 출제되는 알고리즘 분류를 알아야합니다. 사실 코딩테스트에는 그렇게 복잡한 알고리즘이 출제되지는 않습니다. 컴퓨터공학과 학부생이라면 한번쯤 접해봤을법한 이론적 배경에 한하여 출제됩니다. 즉, 본인의 노력 여하에 따라서 충분히 실력이 개선될 여지가 있다는 것입니다. 물론 이는 필자의 실력이 우월하다는것을 의미하는것이 아니며 필자의 실력이 분류별 알고리즘을 풀며 비약적으로 상승했다는것을 의미하지도 않습니다. 다만, PS를 처음 공부할 때 적절한 분류에 따라서 문제를 풀어보는것은 보다 더 효율적인 접근이 될 수 있다는 것을 뜻합니다. 이러한 관점에서 필자가 공부하면서 분류해놓은 알고리즘 유형은 다음과 같습니다.
- Queue and stack (deque 사용 유형 포함)
- Bruteforce (완전탐색. 백트래킹이 포함됩니다.)
- Sorting
- Binary search
- Heap and hash
- Greedy algorithm (탐욕 알고리즘)
- Graph traversal (DFS, BFS를 포함한 그래프 탐색)
- Implementation (구현 타입의 문제. 분할정복, 재귀, 시뮬레이션 등의 문제가 포함됩니다.)
- Graph algorithm (DFS, BFS를 접목시킨 특수한 그래프 탐색 알고리즘)
- Two pointer
- Dynamic programming (memoization. 해당 형식으로 푼 분할정복 문제가 포함됩니다.)
- Tree
- String (원래 문자열을 다루는 방식이 어떤 알고리즘이냐에 따라 분류했지만, 이제 문자열 유형으로 따로 분류합니다.)
- Prefix sum (구간합 문제. 다른 방법으로 풀 수 있는 문제여도 필자가 구간합으로 풀었을 시 이 유형으로 분류합니다.)
해당 문제 분류는 기본적으로 VSFe 님의 algorithm study repo의 유형 분류를 따랐으며, 필자의 부연설명및 추가 유형을 조금 덧붙인 것입니다. (https://github.com/VSFe/Algorithm_Study)
각 주제에 대해 푸는 문제는 BOJ와 프로그래머스에 수록되어있는 문제들입니다.
BOJ : https://www.acmicpc.net/
프로그래머스 : https://programmers.co.kr/
물론, 필자의 주관이 약간 섞인 이 분류는 절대로 정답이 아닙니다. 5번 대분류 항목에 저술될 '참고자료' 파트에서 주제 분류를 참고할 수 있는 다른 repo들을 더 소개해드리겠습니다.
필자가 적기 가장 부담스러워하는 부분입니다. 본인의 실력이 충분치 않다는것을 알기에 다른 분들께 무작정 이 공부방식을 권유하고 싶지 않기 때문입니다. 따라서 한번 읽어보시고 '아 괜찮겠다' 싶은 부분만 적절히 수용해주시기 바랍니다.
필자는 기본적으로 추후 항목에서 작성될 참고자료 repo 에 분류되어있는 추천 문제들 위주로 풀어보고 있습니다. 또한, solved.ac 에 class 3, 4로 분류되어 있는 문제들도 집중적으로 해결하고 있습니다. 그리고 꾸준히. 최소 하루에 1문제라도 풀되 며칠 연속으로 같은 주제의 문제만 푸는것은 지양합니다.
참고자료 repo에 적혀있는 문제들은 알고리즘 유형별 분류가 이미 되어있기 때문에 그 자체로도 문제를 푸는데에 큰 힌트가 되는 경우가 많습니다. 따라서 추천문제가 아닌 solved.ac의 class 문제를 풀때는 되도록이면 알고리즘 분류를 보지 않고 풀도록 노력합니다.
마지막으로, 알고리즘 문제를 풀기전에 내가 생각해낸 방식의 공간복잡도와 시간복잡도가 문제의 제한조건을 초과하지는 않는지 엄격하게 확인해야합니다. 물론 필자도 이 부분에 대해 잘 인지하고 있다는 확답은 드리지 못합니다. 문제를 풀때 시간초과 및 메모리초과가 종종 발생하기 때문입니다. 이 글을 읽는 분들은 필자보다 훨씬 더 꼼꼼히 복잡도를 계산하시고 적절성을 파악하셨으면 좋겠습니다.
지금 작성하는 파트는 이 글의 존재 의의입니다. 위에 적힌 정보들은 모두 무시하시더라도 이 파트에서 제시된 repo들은 한번쯤 들어가보시길 강력하게 권해드립니다.
- 알고리즘 특강 by VSFe : https://github.com/VSFe/Algorithm_Study
- Java 알고리즘 강의 by rhs0266 : https://github.com/rhs0266/FastCampus
- 코딩테스트 대비 문제집 by tony9402 : https://github.com/tony9402/baekjoon
- 기술면접 백과사전 : https://github.com/gyoogle/tech-interview-for-developer
- 기술면접 백과사전v2 by 한재엽 : https://github.com/JaeYeopHan/Interview_Question_for_Beginner
앞서서 최대한 객관적으로 서술하려 했다면, 이 파트는 솔직하고 주관 가득한 내용들을 적어보고자 합니다. 따라서 이부분은 굳이 읽지 않으셔도 됩니다.
Q. 어떤 언어가 가장 유리하다고 생각하시나요?
A. 비교적 많은 경우에 파이썬이 좋다고 생각합니다. 모든 언어를 다루는 수준이 그리 높지 않다고 가정한다면, 파이썬에서 제공해주는 함수들은 프로그램 구현 소요시간을 줄이는데에 아주 효과적입니다. 하지만 자신이 파이썬 이외의 언어에 친숙하다면 그 언어를 사용하는것이 맞습니다.
Q. 코딩테스트를 완전히 처음 준비해봅니다. 어떤 언어를 선택할까요?
A. 이 질문을 따로 나눈 이유는, 단순히 알고리즘 문제를 더 편하게 풀 수 있는 언어와 기업 입사 코딩테스트를 준비할때 좋은 언어는 서로 다를 수 있기 때문입니다. 물론 처음 접하기에 쉬운 언어는 파이썬입니다. 하지만 최근 코딩테스트에서 해당 기업의 기술 스택에 맞지 않는 언어는 지원하지 않는 경우가 더러 있습니다. 그 예로 N사의 특정 서비스 분야 신입 공채에서는 C++ 언어를 지원하지 않았습니다. 그 서비스 회사의 기술 스택이 Java, JavaScript, python으로 이루어져 있었기 때문입니다. 더불어서 만약 파이썬을 사용하지 않는 회사가 있다고 한다면 그 회사에서 사용하는 언어로 코딩테스트를 준비하는게 더 안전합니다. 이런 관점에서 볼때, 처음부터 Java 언어로 준비하는것도 나쁘지 않습니다. 안드로이드부터 백앤드까지, 우리나라에서 가장 많이 사용하는 언어가 바로 Java이기 때문입니다.
Q. 정말 공부하면 늘긴 느나요?
A. 늘긴 늡니다. 하지만 느는 속도가 현격하게 느릴 수는 있다고 봅니다.
Q. 책을 사서 볼까요, 아니면 유튜브 강의를 볼까요?
A. 앞서 추천드린 repo를 먼저 빠르게 보시고 유형별 문제를 많이 풀어보세요. 천부적인 재능이 있지 않다면 무엇보다 경험이 중요하다고 생각합니다.
Q. 위에 기술된 유형들을 모두 마스터해야 코딩테스트를 통과하나요?
A1. 그런것은 아닙니다. 실제로 특정 기업에서 나오는 문제의 유형들이 어느정도 편향되어있는 경우가 있습니다. 물론 다 할줄 안다면 좋겠지만, 기본적으로 위의 8번 유형까지 확실하게 풀줄 아시면 대부분의 코딩테스트를 통과할 수 있다고 보는것이 정설입니다. (만약 목표가 확실하게 네카라쿠배라면 트리와 DP 유형도 실력을 쌓아두시는걸 추천드립니다.)
A2. 최근 누적합 유형의 문제들도 꽤나 자주 출현하는 것으로 보입니다. 주요 기업 코테를 준비하신다면 누적합 관련 스킬도 충분히 익혀두시기 바랍니다.
Q. 솔직히 컴퓨터공학 이론이 좀 부족합니다. 이론부터 다시 싹 정리하고 PS를 시작할까요?
A. 병행하세요. 우리에게는 시간이 그리 많지 않습니다. 적어도 저는 그렇더라구요.
Q. 이 글은 언제 끝나나요?
A. 여기서 끝납니다. 읽느라 수고 많으셨습니다.