궤도
자료구조, 알고리즘 공부를 시작하려 한다면... 본문
이 글은 2021년 8월부터 12월까지 진행된 코딩테스트 대비 알고리즘 튜터링 알튜비튜의 회고글입니다.
코딩테스트 때문에 알고리즘 공부는 해야겠는데 막막한 분들을 위한 글...
근데 '일주일이면 너도 합격할 수 있다!'이런 글은 아닙니다. 최소 3개월은 투자해야 해유
아직 과제 마감이 끝나진 않았지만, 사실상 끝나기도 했고 또 언제 이 글을 쓸 시간이 생길지 몰라 지금 쓴다.
왜 시작했는가?
TMI니까 짧게 요약하면...
학교에서 (적진 않은) 돈을 받고 하는 튜터링 프로그램이 있었다. 정해진 시간에 줌 회의실 열어두면 학생들이 들어와 프로그래밍 언어나...개발 관련한 질문을 하는 그런 프로그램이었는데...3개월동안 1명 왔나? 암튼 그랬다.
물론 그거 말고도 해야 하는 업무가 몇 개 있었지만 아무튼 받는 돈에 비해서 할 일은 아주 적은 소위말해 개꿀인 프로그램이었다.
이 이야기는 그 개꿀 프로그램을 최저시급도 못 받는 강행군으로 스스로 몰아넣은 이야기다.
1학기에 이어 2학기에도 프로그램을 하게 됐다. 이번에도 업무는 비슷했고, 학생들은 오지 않을게 분명했다.
어차피 졸업하는 입장에서 한 번 더 잉여롭게 시간을 죽이며 돈을 받아갈 수 있었지만...이런저런 사건들과 이상한...사명감에 휩싸여 이상한 프로젝트를 기획하게 된 것이다.
솔직히 나 혼자 기획했다면 저어어어얼대로 못했을 것이다. 하지만 나에겐 킹왕짱 진짜 멋있는 동료들이 있었다.
아무튼...교수님께 우리끼리 정리한 내용을 공유드렸고, 오케이를 받았다.
자료구조, 알고리즘에 대한 이론 공부는 2-2, 3-1에 들었던 수업으로 했다지만 제대로 문제를 풀어보며 공부를 한건 사실상 올해 3월부터였는데, 당시에 무슨 정신으로 알고리즘 특강을 열겠다고 한건지 모르겠다.
홍보를 하고 모집을 받고, 우린 태평하게 'ㅎㅎ 15명정도 오실까요? 미달이면 홍보를 더해야겠어요' 이런 말을 했ㄷ..ㅏ...
이후 이야기는 기니까 각설하면 처음에 20명정도의 수강생을 생각했는데 정신차려보니 약 55명으로 시작했다는 이야기다.
물론 지금 끝까지 함께하신 분들은 25분..? 정도 계시는데 예측했던 수치보다 많은 숫자긴하다. 다들 대단하시다.
알고리즘을 공부하신 분들이라면, 그리고 이게 정규 학기와 병행하는 프로젝트란걸 아신다면...
이게 말도 안되는 스케줄이란걸 아시겠지만, 우린 다 열정이 넘쳐서 브레이크를 잡아줄 사람이 없었다.
구성
우리보다 자료구조, 알고리즘을 잘 가르치시는 분들은 많다. 뭐 당장 우리학교 교수님들, 유투브 선생님들, 책, 강의...
아무리 열심히 공부를 했다지만 학부생이 가르칠 수 있는 깊이에는 한계가 있을게 분명했다. 그래서 코드 리뷰를 추가했다.
1. 매주 특정 알고리즘을 주제로 강의식 튜터링 진행
2. PS 과제
3. 제출된 과제에 대한 코드리뷰
3번이 핵심인 셈인데, 인력난과 우리의 경험치 부족으로 이 부분을 제대로 신경쓰지 못한 것 같아 아쉽다.
그리고 우리 스케줄이 빡빡하다보니 뒤로 갈수록 제출되는 과제도 적어졌고... 아무래도 우리 과제보단 교수님들의 과제가 더 중요하니까
커리큘럼은 이렇게 짰다.
단계별로 풀어보기
단계별은 @jh05013님이 관리하고 계십니다. 단계제목설명정보총 문제내가 맞은 문제1입출력과 사칙연산입력, 출력과 사칙연산을 연습해 봅시다. Hello World!112if문if문을 사용해 봅시다.53for문for문을
www.acmicpc.net
이건 백준의 단계별로 풀어보기인데, 나도 처음 알고리즘 공부를 시작할 때 이 목록의 문제들을 순서대로 풀기도 했고, 진짜 좋다.
다만 자료구조 파트를 다 하고(그래프 빼고), 알고리즘을 배우는게 좋을 것 같아 약간 순서를 바꾸긴 했다.
물론 많은 언어가 자료구조와 간단한 알고리즘을 라이브러리로 제공하지만, 라이브러리를 보기 전 직접 구현해보도록 했다.
내가 쓰는게 어떤건지 알아야 응용도 할 수 있고, 뭐 그렇게 생각했다.
과제 문제를 고를 때는 역시나 저 단계별로 풀어보기에 있는 문제들을 몇개 참고했다.
하지만, 풀이가 거의 비슷한 문제들도 꽤 있었고 우리가 매주 나가는 과제 문제가 (겨우) 6개였기 때문에 모든 과제 문제의 풀이가 달랐으면 했다. 일주일에 6(+2)문제가 나가는데 겨우??라고 생각할 수도 있지만, 그 주제를 대표하는 6 문제를 고르는건 참 어려웠다.
https://github.com/tony9402/baekjoon
GitHub - tony9402/baekjoon: 코딩테스트 대비 문제집(Baekjoon Online Judge)
코딩테스트 대비 문제집(Baekjoon Online Judge). Contribute to tony9402/baekjoon development by creating an account on GitHub.
github.com
그래서 추가로 이 레포지토리를 참고했다.
진짜 좋은 레포지토리라고 생각한다. 특히 푼 사람이 많지 않은 문제라면 이 문제가 정말 괜찮은걸까?라고 생각하며 꺼리게 될 수도 있는데, 이 레포는 그런 숨어있는 좋은 문제들을 많이 소개하고 있다.
당연한거지만 이렇게 과제후보로 정한 문제들은 다 풀었다. 그래도 10개 골라오면 1개 살아남는 그런 잔인한 방식은 아니었고
내 선에서 잘린게 대충 1/5 정도고, 제안했는데 잘린건 그보다 적으니까 10문제 풀어오면 7~8문제 정도는 살아남은 셈이다.
준비
그냥 만들었던 강의자료 아무거나 들고왔다.
'스택, 큐, 덱'은 라이브러리가 있는 자료구조지만 앞서 말했듯이 다 직접 구현해보는걸 지향하여 ppt에도 관련한 내용을 넣었고
'최단경로'는 워낙 어려운 주제기도 했는데 이런 저런 예시들을 가져오며 알고리즘 수행 결과를 단계별로 보여주도록 했다.
튜터링 시간에는 라이브 코딩도 했는데, 해당 알고리즘의 아주 기본만 담은 기본 문제와 이를 응용한 응용 문제로 나누어 풀었다.
함께 실시간으로 코딩을 하면 코드를 짜는 과정이나, 갑작스러운 상황에서 어떻게 대처해야하는지 볼 수 있지 않을까 싶어 넣었다.
라이브 코딩 자료 역시 미리 다 준비는 해두기 때문에 큰 사고가 있었던 적은 없고, 거의 간단한 실수가 대부분이었다.
과제는 항상...응용 문제와 비슷한 난이도라고 생각하고 냈는데 체감은 그렇지 않았나보다.
대놓고 어려운 문제를 1문제 정도 섞긴 했었다.
당연히 우리가 준비하는 코드들도 다 코드리뷰를 거쳤다. 그랬는데도 가끔 발견하지 못한 것들이 있긴 했다.
아니 회고가 너무 길어지네 그냥 빨리 적으면
주제 알고리즘 6문제에 추가로 구현 문제도 매주 2개씩 나갔다.
요즘 점점 많은 회사들이 구현 문제를 내는 것 같아서 넣기도 했고, 대다수의 회사가 코너 케이스를 제공하지 않다보니 반례를 만드는 연습을 할겸 넣기도 했다.
코드리뷰 기준은 크게 3개였다.
1. 문제가 맞았는가? 풀이가 이상한데 답은 맞았습니다를 받은 경우는 없나? (이런 경우가 없지 않나 생각할 수 있지만 있다.)
2. 시간복잡도면에서 비효율적인 부분은 없나? (O(n)이 가능한 풀이인데 O(n^2)이라던가...TLE로 잡히지 않는 비효율적인 부분들)
3. 가독성은 괜찮나? (코드를 함수로 분리하거나, 인덴테이션이 너무 깊게 들어가지 않도록)
그걸 어떻게 알아채냐고 물어본다면...사실 잘 모르겠다.
그냥 내가 그 문제를 푼적 있으니까 내가 했던 실수나 비효율적인 부분이 그대로 나타나는 코드도 있었다. 그리고 내가 단순히 모범답안 코드를 봤다면 코드리뷰가 어려웠겠지만 문제를 직접 풀면서 더 좋은 코드를 짜기 위해 고민했었기 때문에 할만했다.
한편으론 내 시야 이상의 무언가를 발견할 수 없었다는 의미기도 하다. 이 부분은...개선할 방법을 대충 구상하긴 했다.
회고는 여기서 끝났고, 이제 제목과 관련한 이야기를 해보도록 하자
혼자 공부한다면
일단 자료구조에 대한 이론 지식은 있는게 좋지 않을까 싶다. 실제 코딩테스트에선 이 문제가 어떤 알고리즘으로 풀리는 문제인지 알 수 없다. 라이브러리만 달달 외운다면 특정 상황에서 어떤 자료구조와 알고리즘을 사용해야할지 판단하기 어려울 수 있다.
(예를 들어 TLE를 막고자 스택, 큐 같은걸 사용한다거나...)
이론이 그렇게 어려운 것 같진 않아서 금방 배울 수 있다. 저 위에서 말한 유투브 선생님께 가도 괜찮고, 전공자라면 교수님 강의 자료를 보거나 뭐...우리 자료를 봐도 괜찮다. 교수님 강의 자료로 배운 사람들이 많든 자료니까 허허
공부하는 순서는 역시나 앞서 말한 백준의 단계별 풀이 문제를 순서대로 푸는걸 추천한다.
알고리즘을 처음 공부한다면 이게 어떤 알고리즘의 문제인지 파악하는 것부터가 어렵다. 그리고 비슷한 스타일의 문제가 뭉쳐있기도 해서 처음엔 어렵지만 비슷한 문제를 연속해서 풀어보며 이해하기도 좋다. 프로그래머스도 좋긴 하지만 문제의 수가 백준에 비해선 많이 적고, 난이도 책정이 너무 포괄적이다.
단계별 풀이 문제를 다 풀었다면
https://www.acmicpc.net/workbook/top
인기 문제집 - 1 페이지
www.acmicpc.net
여기가서 그냥 맘에드는거 풀면 좋다. 맨 위에 삼성 기출문제가 있는데 구현능력 키우기엔 삼성 문제가 좋다. (어렵다)
https://www.acmicpc.net/workbook/codeplus
code.plus 문제집 - 1 페이지
www.acmicpc.net
그 옆에 코드플러스 들어가서 풀어도 좋다. 근데 난이도가 급발진 하는 문제도 있으니 그냥 풀고 싶은걸 풀어라
다만 아쉬운게 있다면 알고리즘 유형이 문제집 이름에서 드러난다는 점인데
전체 문제가서 적당히 원하는대로 필터링해서 풀면 된다.
이건 내가 쓰는 필터링인데 제출한 적 없는 문제 중에서 실버~골드 문제를 맞은 사람이 많은 순서로 정렬했다.
정렬은 그냥 많은 사람이 풀었으면 괜찮은 문제겠거니~ 하고 저렇게 정렬했다. 필터링 옵션이 많으니 입맛대로 골라쓰세유
이걸 단계별로 진행해야하는건 아니고 그냥 이거했다가 저거했다가 하는게 좋다.
왜냐하면 단계별 풀이 목록에도 정말 다양한 난이도의 문제가 있고, 괜히 안풀리는거 붙잡다가 흥미를 잃을 수도 있다.
그리고 문제 풀면 꼭 다른 사람 코드를 4~5개는 찾아봤으면 좋겠다. 내가 몰랐던 라이브러리를 알 수도 있고, 리팩토링을 하는데 도움이 될 수도 있다. 문제가 풀렸다고 그대로 커밋하지말고 완성된 코드를 짧게 쳐다보며 리팩토링을 해도 좋다. 맞았습니다를 받기 위해 넣어뒀던 이상한 코드들을 발견할 수도 있고, 내가 이걸 어떻게 풀었는지 정리할 수 있다.
스터디라면
알고리즘 스터디를 해본적이 없어 잘 모르겠지만...
사람이 모인 김에 상호 코드 리뷰는 꼭 넣었으면 좋겠다. 그냥 각자 공부하고 점검하면 뭐 혼자 공부하는거랑 똑같으니까
다만 단점이 있다면 코드리뷰를 하려면 내가 그 문제에 대해 알고 있어야 하고 그럼 스터디원들이 푸는 문제가 획일된다. 어떤 문제를 풀지 정하는 데에도 시간이 걸릴테고...
저 위에서 내가 추천한 문제 목록 레포도 있고, 검색하면 추천 문제 목록이 굉장히 많다. 잘 찾아봐서 잘 결정하시면 된다.
그리고 패널티는 알아서 잘 정하시겠지만, 코드 카피도...신경써야 한다.
구글에 백준 OOOO번 이렇게만 검색해도 풀이 코드가 저어엉말 많다. 만약 패널티가 빡세다면 패널티를 피하기 위해 그냥 적당히 코드 복붙해서 제출할 수도 있다.
사실 가장 맘편한건 신경쓰지 않는 것이다. 카피를 해봤자 본인 손해니까...
근데 난 스터디 프로그램을 이끄는 튜터라 이걸 신경쓸 수 밖에 없었다.
취지에도 맞지 않고, 안좋은 습관이 생길 수도 있고, 가장 큰 이유는 구글링해서 나오는 코드가 완벽한게 아니다.
당장 내가 공부하면서 올린 코드들도 지금보면 눈뜨고 볼 수 없고, 아예 방향이 잘못된 코드들도 있다.
뭐...결론은 소규모 스터디에서 카피 잡는건 정말 어려운 일이고 그냥 맘편하고 싶으면 개인의 양심에 맡기도록 하자
마무리
이 모든 글은 개인의 경험에 기반한 것이라 별 도움이 안될 수도 있다. 어차피 개인적인 회고글에 가깝기도 하다.
하지만 알고리즘이 너무 좋아서 대회도 나가고 그럴게 아니라면, 그니까 그냥 코테 통과를 위해 알고리즘 공부를 한다면 알고리즘에 반년 이상의 시간을 쏟지 않았으면 좋겠다. 전공자라 이론 베이스가 있다면 1~3달만 써도 될 것이다.
저는 알고리즘이 너무 좋아서 이 글쓰고 또 문제하나 풀러갈 예정이구요...
저희 깃허브도 정말 튜터들끼리 정성을 다해 꾸린 깃허브니까 참고하셔도 좋습니다
그리고 알튜비튜는 그냥 알투비트가 생각나서 지은 이름이다.
