0. Introduction (23.08.20 수정)

개요

파이썬으로 코딩테스트를 준비하면서 공부한 알고리즘 내용을 내가 알기 쉽게, 남에게 설명하듯 작성하고, 많은 문제를 풀이하고, Write-Up을 작성하고, 적은 경험이지만 남들에게 공유하고 싶다 라는 생각으로 만든 목적성 분명한 블로그입니다.

목표는 24년 SW-Maestro 합격이고, 이를 위해 각종 알고리즘을 공부중이며, 각 알고리즘마다 Solved.ac 기준 GOLD III을 무리없이 풀이할 수 있다면 다음 알고리즘을 넘어가는 방식과, 이를 달성하기 위한 목표 시간을 설정하여 공부중입니다.

공부 순서는 다음과 같습니다.

1. GREEDY (그리디)
2. IMPLEMENT (구현)
3. DFS / BFS (그래프 탐색)
4. MST (최소 스패닝 트리)
5. SORT (정렬1, 정렬2)
6. SEARCH (탐색)
7. BINARY_SEARCH (이분 탐색)

이후 추가 예정

문제를 풀기 위한 준비

• 문제를 읽고 이해하기 : 문제 설명을 공격적으로 읽으며, 문제가 원하는 바를 완전히 이해하는 과정이 필요하다. 전체의 기능에 큰 영향을 미치지 않는 작은 실수도 용납되지 않는다.

• 재정의와 추상화 : 자신이 다루기 쉬운 개념을 이용하여 문제를 자신의 언어로 풀어쓴다. 또한 현실 세계의 복잡한 개념을 어느정도 본질만 남겨두고, 축약하여 다루기 쉽게 표현해야 한다. 이 과정을 추상화라고 한다.

• 계획 세우기 : 문제를 어떤 방식으로 해결할지 결정하고 사용할 알고리즘과 자료구조를 선택한다.

• 계획 검증하기 : 설계한 알고리즘이 모든 경우에 요구조건을 정확히 수행하는지 증명하고, 수행에 걸리는 시간과 사용하는 메모리가 문제의 제한 내에 들어가는지 확인해야 한다.

• 계획 수행하기 : 프로그램 구현을 한다.

• 회고하기 : 문제를 해결한 과정을 돌아보고, 개선하는 과정이다. 문제의 간단한 해법, 접근 방식, 문제를 해결하는데 결정적인 깨달음을 기록한다. 기록이 쌓이면 문제들간에 공통으로 필요한 통찰들이 패턴화 되기도 한다.

만약 문제를 풀지 못했을 때는 초보시절에는 너무 한 문제에만 매달리는것도 좋지 않다. 일정 시간이 지나도 답을 찾지 못할 때에는 다른사람의 소스코드나 풀이를 참조하되, 반드시 복기를 동반해야 한다. 자신이 문제를 해결할 때 취했던 접근들을 되새겨보고 자신이 왜 이 풀이를 떠올리지 못했는지 살펴봐야 한다.

문제 해결 전략

직관은 해당 문제를 해결하는 알고리즘이 대력적으로 어떤 형태를 가질지를 짐작할 수 있게 해준다. 이는 막막한 문제들을 해결해나가며 점차 경험을 쌓아 나가야 생긴다.

체계적인 접근울 위한 질문들

1. 비슷한 문제를 풀어본 적 있던가
2. 단순한 방법에서 시작할 수 있을까
3. 내가 문제를 푸는 과정을 수식화 할 수 있을까
4. 문제를 단순화 시킬 수 있을까 (제약조건 없애기, 계산 변수 줄이기 등.)
5. 그림으로 그려볼 수 있을까
6. 수식으로 표현할 수 있을까
7. 문제를 분해할 수 있을까
8. 뒤에서부터 생각해서 문제를 풀 수 있을까
9. 순서를 강제할 수 있을까
10. 특정 형태의 답만을 고려할 수 있을까 (정규화)

진행 상황

23.05.02

현재 이분탐색 공부중이며 목표는 2023.05.30 까지 이분탐색 태그의 문제를 GOLD III 까지 올리기 입니다.

알고리즘을 공부하면서 따르는 커리큘럼은 "이것이 코딩테스트다 with Python"의 커리큘럼을 따르며, 관련 알고리즘은 따로 공부하는 방식으로 확장해 나가는 중입니다.

23.05.12

이분탐색의 수준을 이전보다 끌어올렸으며, 이분탐색 구현에는 문제가 없어 앞으로 문제풀이를 위해 bisect모듈을 이용하기로 하였으며 수학을 병행해 공부하기로 하였습니다. 지금까지 푼 이분탐색 문제는 총 21문제이며 SILVER III 정도의 수준입니다. 목표까지 남은 기간은 약 3주이며, 조금 심화적인 문제를 풀이할 필요가 있다고 느꼈습니다.

조만간 순서 상관없이 이분탐색에 대한 내용을 정리하고, 이분탐색과 더불어 매개변수 탐색도 풀이할 예정입니다.

23.05.23 -> 23.05.24

이분탐색과 매개변수 탐색을 이용하여 아이디어를 구상해 풀이하는 시간이 실버 3~1 기준으로 평균 20분정도 걸립니다. 2023.05.02일 세운 목표 이분탐색 태그 GOLD III 만들기는 어려울것 같아 (티어를 올리려면 높은 등급의 문제를 풀이해야하는데 이분탐색의 높은 등급 문제는 트리나 그래프에서 이분탐색 응용이라 아직 풀기에 난이도가 높음.) 우선 이정도 해두고 다음 목표로 넘어가려 합니다. 현재 이분탐색은 27문제 풀이하였으며 티어는 SILVER II 입니다.

• 수학 문제 풀이하기 목표는 실행을 못했습니다. PS를 공부하는 시간을 줄여 수학을 공부하려 했는데, 핑계지만 시간을 내는것이 어려워서 따로 시간을 들여 공부하기로 했습니다.
  매일매일 목표를 책에 기록하는 방식으로 억지로라도 진행해야 뭐든 될 것 같습니다.

• 블로그에 알고리즘 정렬하기목표는 진행했습니다. 우선 정렬과 탐색파트를 정리하였고, 그래프 관련한 부분은 모든 알고리즘을 공부하고 정리한 이후 차순위로 미루기로 했습니다. 우선 다양한 알고리즘을 접해보고 공부하는것이 우선이지, 충분히 투자한 그래프를 다시 정리를 위해 되돌아가는것은 시간적으로 비효율적이라 생각했기 때문입니다.

• 새로운 목표를 설정합니다. 우선 이번에 공부할 것은 세그먼트트리와, BST라고 하는 이진 탐색 트리 입니다. 이진 탐색 트리의 경우 기본형을 공부하는것을 마쳤고, 이 문제를 풀이하면서 원리까지 파악했습니다. 세그먼트 트리를 먼저 공부하고, 문제를 조금 풀이한 다음에 DP를 공부하며 개인적으로 코딩테스트의 꽃인 DP에 많은 시간을 투자할 생각입니다.

• 추후 공부 방법은 "태그 가리기"입니다. 태그를 가려 문제만 보고 적절한 해결 전략을 펼쳐 어떤 문제가 나와도 풀이 할 수 있도록 공부할 생각입니다.

정리하자면 6월 공부할 목표는 세그먼트트리, DP이며, 트리를 공부하다가 조금 더 응용해야하는 부분이 생긴다면 추가로 공부할 생각입니다.

(24일 목표 변경) 세그먼트 트리를 공부하기 위해 트리를 공부하려고 하는데 트리를 공부하기 전에 재귀를 공부하는것이 좋을 것 같다는 생각을 하였다.
따라서 재귀 먼저 공부한 뒤, 트리를 공부할 예정이다.

23.05.28

작성일 기준으로 재귀 및 분할 정복 문제풀이는 실버 1 수준 문제까지 풀이 할 수 있다. 우선 목표가 트리와 이진 탐색 트리 문제 풀이였고, 이해하기 위해서는 재귀의 매커니즘을 공부할 필요가 있어 선행 학습 한 만큼 재귀 카테고리는 여기까지 하고 더이상 심화 문제는 나가지 않으려고 한다.

현재 성취도를 판단했을때, 맨 처음 재귀를 공부할 때 2시간 정도를 모두 써서 겨우 실버 3 수준의 문제를 풀었지만 나름 실버 1 수준의 문제 풀이를 30분 내외로 한다.

오늘 목표를 다 끝내고 약간의 시간이 남아 간단한 그래프 탐색 문제를 풀이하였는데, 실버 수준의 문제는 10분이면 풀이할 수 있을 것 같은 자신감을 가질 수 있었다.

지금까지 문제풀이에 대한 성취도이며, velog에 업로드한 재귀 문제를 기준으로 총 6문제 정도 풀이하였다.

스트릭은 아직 까지 유지중이며, 목표 100일 달성까지 50% 정도 완성하였다. 중간중간 근무 때문에 스트릭 프리즈를 사용한 것 말고는 성공적이다. 앞으로도 목표를 향해 열심히 나아가야겠다.

23.06.03 -> 23.06.06

이번달부터 다이나믹 프로그래밍 문제를 집중적으로 풀이하기로 했다.
6월에는 메모이제이션등 DP에 대한 스킬과 점화식 작성요령에 대해 숙지하고, 7월부터는 태그를 가리고 다양한 문제를 접하면서 BOJ 뿐만 아니라 Programmers나 Leet Code 등 다양한 플랫폼에서 많은 문제를 접해보는것이 목표이다.

5월 한달은 조금 뭐랄까 공부가 하기 싫었던 적이 많았던거 같다. 특히 트리나 재귀등 흥미 없는 분야를 죽치고 공부하는것과, 개인의 욕심으로 인해 고급 자료구조를 공부하는등 실력에 비해 높은 수준을 요구하는 것들을 공부했던것이 그 원인이었던 것 같다.

원래 트리 자료구조와 세그먼트 트리같은것들을 조금 더 공부하려고 했는데, 흥미가 너무 떨어져서 조금 일찍 끝내고 DP로 넘어간다.

하기 싫었음에도 한 문제라도 계속해서 잡고 있었던건 스트릭 탓이 제일 크지 않나 싶다.
시간이 없는 날이더라도 쉬운 문제는 꼭 하나씩이라도 풀이하였다.
오늘부터 새로 시작하는 알고리즘은 평소에도 공부하고 싶어서 아껴뒀던 분야이다.

이번달의 계획은 아래와 같다

• DP 기초
• 최단 경로 알고리즘 (다익스트라 등..)
• 다른 알고리즘과 결합된 DP

ps. 공부했던 알고리즘들도 정리해야 하는데 할 시간이 없다,,
ps2. 알고리즘 뿐 아니라 또다른 목표였던 책 읽기와 북 리뷰는 작성중이다.

(6일 리뷰)
오늘 현충일 기념,, 인하대학교 2023 프로그래밍 경진대회 문제를 시간을 두고 풀이해봤다.
2문제 풀었다..ㅋㅋ
적어도 실버 문제는 다 풀 수 있어야 하는데, 일단 연습해야할건 기초 자료구조와, 완전탐색이다.
나는 완전탐색이 의외로 어렵다고 생각하는데, 경우의 수를 모두 구한다거나,, 뭐 이런걸 어떻게 탐색해 나갈지가 막막하다.. 이것도 역시 감이겠지만,, 좀 연습해봐야 할 필요가 있겠다.

23.06.12

100일 스트릭이 60일만에 깨져버렸다. 휴가동안에 여행을 하루 갔다온 날이 있었는데, 스트릭 프리즈를 사두고 걸어두는것을 까먹어버렸다. 이왕 이렇게 된 김에 남은 휴가기간동안은 그냥 놀아버렸다.
오늘을 기점으로 다시 100일 채우기 도전은 시작한다.

마지막 기록은 60일이다.

종만북을 가져왔다. 종만북을 참고용으로해서 CPP 문법을 파이썬으로 적절히 수정해서 풀이할 생각이다. 내용을 보니 자료구조부터 시작해서 중, 고급 알고리즘까지 범위가 다양하다. 대회 알고리즘을 공부하는것이 아니기때문에 여기에 현혹되서 굳이 파고들 생각은 없다.

지금은 휴가 전 공부하던 DP를 중점적으로 공부하고, 완전탐색 부분을 조금 더 공부해봐야겠다.

23.06.26

오랜만에 쓰는 것 같은데 별 일 없었다. 그냥 문제풀기 바빴을 뿐.
종만북을 이용해 DP를 시작하였다. 예전에는 읽기 벅찼는데 지금도 벅차다. 이 사람의 생각을 따라가기 위해 코드 하나하나를 말그대로 뜯어보고있다. 그러니 이전보다는 훨씬 실력이 올라갔다고 자신한다.

DP중에서 메모이제이션 적용기법을 중점적으로 공부했고, 대표적 문제인 LIS 문제를 짚어보는 중이다. DP 최적화문제기법을 책에나온 예제문제 또는 이와 같거나 최대한 비슷한 문제를 백준에서 찾아 풀어보고 있고, 앞으로 몇주간은 경우의 수 또는 확률론에서 다이나믹프로그래밍과, 다이나믹 프로그래밍 테크닉에 대한 내용을 읽고 공부할 예정이다.

제 2회 초콜릿컵에 참가하였다. 참가한 대회가 이것만 있는건 아니긴 한데, 그래도 풀 수 있는 문제는 다 풀었다고 자신하는 대회이자, 상품도 받았다..! 여기서 특이했던 문제 유형은 인터렉티브 인데 어,, 내가 컴퓨터에게 질문하고 컴퓨터가 나에게 답을 하는 방식의 특이한 문제였다. 매커니즘은 이해했는데 최악의 경우 계산을 못해서 틀린 문제이다. 조금 더 시간 있었으면 풀었을듯.

이 와중에 머리에 꽃밭도 피웠다. 영어랑 친해져서 MIT의 알고리즘 수업을 들어보는것이 꿈이다. 당장은 이래저래 핑계거리가 있어서 못하지만, 조금 내가 알고리즘을 잘한다 라고 판단했을때 도전에 있는 강의를 들으며 공부해보고 싶다.

논문 읽기 또한 꿈이었는데, 그럴필요 없이 MIT의 적당한 난이도의 LECTURE NOTE를 다운로드 받아 읽어볼 생각이다.

책 읽는 취미가 생겼는데, 독후감을 써서 올리자는 생각만 1달이 넘어갔다. 바로 실행해야 하는데 그러지 못해 조금 아쉽고, 사실 임시저장된 부분에 몇개 써둔게 있긴하다. 올리진 못했을뿐,,

일단 7월까지는 DP를 푸는게 좋을 것 같다. 사고력의 확장이 필요한데, 이를 통해 다양하게 생각하는 방법을 배우는 것 같다. 재귀를 이용한 풀이를 하니 난이도가 조금 더 올라가는듯.

재귀를 구현할 때 SRTBOT으로 문제를 분해하는 방법을 들어보았다. 음.. 이건 조금 더 이해해야 할 문제이다.

23.06.30

5월부터 쓰기 시작한 이 글이 이제 2달이 다 되어가고 있다. 6월 먼슬리 리뷰를 대체한다. 지금의 모토는 느리지만 확실하게이다. 스트릭을 유지할 때에는 문제풀이에 급급했었다. 라는 생각이 스트릭이 깨지고 나서 들기 시작했다. 아니 그 전부터 알고 있었는데 그냥 무시했던것일수도 있다.

6월은 DP를 위주로 공부하였다. 6월 초는 동빈북을 이용했지만, 이전에 사놓은 종만북을 다시 펼쳐보았더니 조금 더 욕심이 생겨 종만북의 CPP코드를 Python으로 바꾼다면 이 책도 도움이 많이 되지 않을까라는 생각에서였다. 사실 절대 만만한 책이 아니라고 느꼈다. 그런데 도전욕구와, 해결했을때 커다란 성취감이 들었고, 7월까지 종만북을 이용하여 DP를 풀이할 예정이다. 예전에는 거의 암기하여 문제를 풀이하기 바빴다라는 느낌이라면 지금은 연구하는 느낌이다. 실제로 코드를 보면 한번에 이해가지 않아서 직접 손으로 과정을 따라가며 문제를 이해하는 중이다. (2장 넘기는데 10시간이 넘게 들었다..)

최근 읽은 책 중 "몰입" 이라는 책이 있었다. 내가 하고 있는 일에 몰입한다는 느낌을 받았고, 책에서 말하는 내 능력치의 최대를 발휘해보려고 노력하고 있다.

앞서 말했듯 7월도 DP를 중심으로 정리하고 공부할 것 같다. 6월에 백준을 플랫폼으로 주최하는 대회 몇개를 나갔는데, 도움이 많이 되는 것 같다. 난이도는 높았지만 그래도 풀 수 있는 문제가 있음에 감사했다.

백준 기능 중 하나인 그룹 기능이다. 내가 직접 시간을 넣고 문제를 넣어서 대회처럼 풀 수 있도록 한 기능인듯하다. 아직 한번도 안써봤지만 7월부턴 이 기능도 적절히 이용해서 실전에 더욱 가까워질 수 있도록 할 것이다.

목표를 확실히 할 필요가 있다. 내가 PS를 시작한 것은 SWM 때문이다. 최근 주객전도가 좀 되어 알고리즘 문제풀이와 알고리즘 대회쪽으로 치우쳐진것 같은데, 우선 많은 알고리즘을 접해보는것이 우선이라는 사실을 알아야 한다. 코딩테스트에서 대회 알고리즘처럼 어려운 문제는 잘 안나온다..! 이제 시간이 많이 남지 않았다. 조금 더 선택과 집중을 하자.

23.07.06

추상적으로 계획했던 DP공부를 구체적으로 잡아서 업데이트겸 하여 다시 기록한다.
지금까지 DP는 최적화 문제에서의 DP를 공부하였고, 현재 공부중인 부분은 경우의 수와 확률에서의 DP 적용이다. 이번달까지 DP 테크닉을 조금 더 공부하고 (TSP나 베낭문제 등) solved.ac 플레티넘 V를 찍는것이 목표이다.

추후 계획은 아직 미정이지만, 그래프 카테고리로 다시 넘어가 최단경로 알고리즘을 공부 한 뒤, 자료구조를 이용한 문제들 (트리라던가, 우선순위 큐라던가..)을 공부할 예정이다.

자료구조를 공부하고 나면 트라이나 KMP같은 문자열을 다루는 알고리즘을 공부하고, 네트워크유량을 공부한 뒤 고급 자료구조를 공부할 생각이다.

이 시점이 되면 코딩테스트 준비 비율은 조금 줄이고, 포트폴리오를 준비할 생각이다. 지금 운영하고 있는 챗봇 서비스 산돌이 관련한 내용과, 프론트엔드부터 백엔드, 데브옵스까지 모두 경험할 만한 개인 블로그 만들기 프로젝트를 시작할 생각이다. 아마 올해말 또는 내년 초에 시작하지 않을까 싶다.

이때부터는 코드포스 대회도 조금씩 나가볼 생각이다. 이걸 위해서라도 영어공부를 좀 해야 할듯,, 이제와서 할거였으면 진작에 할걸 하는 후회도 조금 있는데, 늦지 않았다.

23.07.17

요 며칠간 싸지방 컴퓨터가 안돼서 PS를 못했다. 대신 수학공부에 조금 더 집중하였다. 내가 가지고 있는 책은 수학 리부트 인데 집합 -> 숫자 -> 수식 -> 함수 -> 기하 로 넘어가는 이 기초적인 과정들을 통해 알고있지만 알지 못했던 것들을 짚어보면서 이전에 공부했듯이 암기가 아니라, 이해를 기반으로 공부할 수 있다는 것이 장점이다.
내가 수학공부를 다시 시작한 이유는 오로지 DP와 같이 사고력을 요하는 문제들 때문인데, 이것도 마찬가지로 미리할걸 이라는 생각이 좀 들지만 후회는 하지 않는다. 다시 돌아간다해도 안했을 거니까..

아무튼 조금 계획보다는 PS를 하는게 차질이 생겼지만, 오늘부터 다시 시작하는 마음으로 계획했던 PS문제 3개를 우선 풀고 그 다음 진도를 나가볼까한다.
그 다음 진도에서는 동적계획법 테크닉 파트로, DP에서 수량을 구하는 것이 아니라 값을 구하는 테크닉을 요한다. 이 단계에서는 보통 백준기준 PLATINAUM 이상의 문제들이라 이때 다이아 수준의 문제를 풀어보는것을 목표로 하고 있다.

그다음은 8월 6일에 있는 Solved.ac의 아레나 참여인데, 대회 연습겸 티어 올리기 겸 해서 참여할 생각이다.

추후에는 아직 뭘 해야할지 정하지 못했는데, 종만북으로 탐욕법 읽기랑, 최단거리알고리즘을 공부할 생각이다.

모두 금빛으로 채우기까지 얼마 남지 않았다!

23.07.24

8월부터는 이 글을 따로 떼어 TIL 항목으로 옮기고자 한다.
Velog를 쓰면서 처음 알았는데, Today I Learned 라고 매일매일 내가 오늘 공부한 것을 기록하는 포스팅이다. 하루를 회고하고 다음을 계획한다는 점과, 따로 떼어 보면 내가 이때 무엇을 계획했는지 알기 쉬울 것 같아 내린 결정이다.

아무튼, 우선 기초적인 다이나믹프로그래밍은 끝냈다. 사실 끝냈다는 표현은 맞지 않는다. 책을 읽는것만 마친 상태이기 때문이다. 이전보다 재귀함수를 구현하는데 익숙해졌고, 탑다운 방식에서 기저 사례와 부분문제를 만드는 속도는 비약적으로 빨라졌다고 평가한다.

다만 약한것은 구현이다. 소위 말하는 피지컬이 딸린다. 아무래도 경험 부족인데, 욕심을 조금 버리더라도 일정 시간이 지나면 답을 참조해서라도 많은 것을 보는것이 나을 것 같다. 지금처럼 몇시간이고 틀린 방법으로 생각을 이어나가는것이 좋지 않다는걸 몸으로 깨달았다.

이제부터 공부할 내용은 동적계획법 테크닉이라는 부분인데, 이 부분에는 외판원 순회, K번째 LCS 구하기, 베낭문제 들이 수록되어있다. 이 부분을 공부하게 되면 훨씬 더 많은 테크닉들을 사용할 줄 알게 되고, 응용단계에 들어설 수 있을것이라고 본다.

8월 안으로 풀 문제는 아래 문제이다,

어렵다. 매우 어려운데, 일단 해보려고 한다. 지난주에 목표했던 바이므로 아마 나는 해낼것이다.

최종 목표

1. Solved.ac 티어 Platinaum V ✅
2. 24년도 SWM 합격
3. Solved.ac 스트릭 100일간 깨지지 않기 (= 꾸준히 하기)
4. 여기 문제 다 풀기
5. 전역 이후 23.10월 기업 코딩테스트 문제 위주 풀이
6. 1000문제 풀이

도전

1. 24년 중순 전 이 강의 청취