알고리즘 학습법

hyHA·2023년 12월 10일

코딩테스트 언어 선택

공부한 언어가 자바여서 당연히 프로그래머스에서 문제를 풀 때 자바언어로 선택했으나, 점점 문제를 풀수록 자바 라이브러리를 잘 사용하는 것이 중요해져서 라이브러리들을 외우는 것이 코딩테스트의 핵심이라고 오해했던 것 같다.

하지만 코딩테스트의 핵심은 구현(솔루션 로직)을 잘 떠올리는 것이라 생각되어서 파이썬으로 다시 공부를 시작해보려 한다.

또 지금까지는 무작정 문제를 풀기를 반복하다가 이것보다는 문제를 해석하고 그에 맞는 솔루션 로직을 생각하는 논리력을 기르기 위해 책을 보려 했는데, 입문용으로 <파이썬 알고리즘 인터뷰>가 지치지 않고 가볍게 볼 수 있는 책으로 생각되어 이런 저런 점을 고려했을 때 파이썬으로 공부하기로 했다. 그러다가 실력이 좀 늘면 유명한 종만북을 추가로 볼 예정이다.

문제풀이 사이트

지금까지는 프로그래머스에서 레벨0,1단계를 풀고 2단계를 풀어보려고 했으나, 알고리즘 관련 포스팅이 대부분 백준이고, 알고리즘 스터디 구하는 조건들이 대부분 백준 사이트를 기준으로 잡고 있어서, 나중에 스터디에 참여하기 위해서라도 백준으로 공부하는 것이 나을 듯 하다.

백준 사이트 사용방법

'백준 - solved.ac - CLASS - 에센셜 문제/일반 문제' 구조로 되어있는데, 여기서 에센셜 문제를 다 풀고 일반 문제를 다 풀고 다음 단계로 넘어가면 된다.

문제 풀이 방법

1시간 가량 고민해보고, 안풀리는 문제는 답지를 참고하고 몰랐던 부분을 공부하자. 이것을 반복하면 경험이 쌓이면서 실력이 오른다고 한다.

알고리즘 공부하기

알고리즘을 먼저 공부하고 문제에 적용하자. 알고리즘 하나 하나의 개념을 확실하게 잡고 갈수록 뒷부분에서 성장속도가 빠르다. (여러 개의 알고리즘을 사용해야 하는 문제를 만났을 때 등)

또한, 문제를 푸는 과정에서의 실수를 줄일 수 있다.
문제 잘못 읽기, 조건 잘못 보기, 설계 잘못하기, 타이핑 실수 등.

그리고 문제 제출 후 수정 작업을 설계에서 복기한다면 코드에서 복기하는 것보다 코드를 고칠 때 깔끔하고 쉽게 찾을 수 있다.

공부해야 하는 알고리즘

추천하는 개념 블로그 :

파이썬 : 다빈치코딩 알고리즘
c언어 : 라이 블로그, 안즈 블로그

시간 복잡도 -> 완전 탐색 -> 그리디 -> 분할 정복(재귀) -> BFS, DFS (기초) -> DP(초급) -> BFS, DFS, 여러 그래프 자료구조 -> 최단 경로 -> 이분 탐색(조금 더 앞에 해도 됨) -> 슬라이딩 윈도, 투 포인터 -> 유니온 파인드, 최소 스패닝 트리(MST) -> 위상 정렬(잘 안 나오긴 하는데 알면 좋음)

알고리즘을 공부할 때는 어떤 알고리즘을 언제 사용해야 되는지, 시간복잡도가 어떻게 되는지 공부해야 한다. 알고리즘이라는 것은 막일과 비교해서 시간과 공간을 더 효율적으로 쓰기 때문에 만들어졌다.

우리가 문제를 접하고 푸는 방법도 완전탐색(슈퍼 노가다)로 문제를 푼다고 생각을 하고 알고 있는 알고리즘을 대입해서 어떤 알고리즘을 적용하는 것이 좋을지 선택해야 하기 때문에 이론에 대한 이해와 사용하는 경우를 인지하는 것이 중요하다.

알고리즘을 구현한 코드 보기

개념을 잡으셨다면 이제 알고리즘을 구현한 코드를 보자. 구현되어 있는 코드를 보면서 살짝 부족했던 알고리즘 이해나 시간복잡도를 계산하고 코드를 외우기보다는 어떤 순서를 통해 작동하는지 이해하시는 게 중요하다

보통 간단한 문제들이 같이 포함되어 있는데 작성되어 있는 코드를 보지 않고 스스로 코드를 작성할 수 있을 정도면 됩니다.

공부한 알고리즘 문제들 몰아풀기

문제를 읽고 어떤 알고리즘인지 알아차리는 능력을 키우기 위해서는 하나의 알고리즘을 정해놓고 최소 10문제 정도 난이도를 높여가며 이어서 푸는게 좋다.(완전탐색에서 시간복잡도로 알고리즘을 추측하는 것과는 별개)

결국은 다른 문제이지만 하나의 알고리즘을 다루고 비슷한 난이도의 문제이기 때문에 지문에 공통적인 흐름이 존재한다. 지문의 소재(이야기), 입력값들의 범위, 출력 등은 다를 수 있지만 문제를 풀기 위한 알고리즘은 동일하고 이를 은연중에 나타내는 지문, 조건에는 공통점, 특징들이 존재한다. 2~3개의 문제를 푼다고 감이 잡히지는 않지만 8~10번 째의 문제를 이어서 푸신다면 대략 어떤 느낌인지 알 것.

단 문제를 띄엄띄엄 풀게 된다면 의미가 없으니 최소 1주일 정도에 하나의 알고리즘을 몰아서 푸는 게 좋을 듯. 이어서 풀면서 미숙한 구현 실력을 키우자.

단 이렇게 문제들을 몰아서 풀 때 중요한 게 있는데 바로 좋은 문제들을 선정하는 것이 중요합니다. 좋은 문제는 문제의 지문에 오류가 없고 억지스럽지 않으며 구글에 검색을 했을 때 좋은 블로그 풀이 가 있는 문제들입니다. 선정기준은 푼 사람이 최소 2000개 이상으로 잡으시면 편한데 이것도 처음이라면 어렵기 때문에 라이 블로그, 안즈 블로그의 알고리즘 설명 하단에 문제들이 포함되어 있으니 찾아서 풀어보자.

알고리즘 설계하기

어떤 알고리즘을 언제 사용해야 하는지 익혔다면, 문제 풀이를 시작한다.
이때 바로 코드를 짜지말고, 문제와 조건, 알고리즘 개념을 조함해서 설계를 먼저 한다.
감이 안오면 완전탐색으로 문제를 설계하고, 알고리즘을 통해 시간 복잡도를 줄여보자.

조건과 문제를 읽은 뒤 가능한 시간 복잡도를 생각하고 적용 가능한 알고리즘들이 어떤게 있을지 생각한다. 문제와 조건만으로 감이 오지 않으면, 완전 탐색으로 문제를 설계한 뒤 나오는 시간 복잡도를 보고 알고있는 알고리즘들로 시간 복잡도를 최대한 줄여 조건을 만족하는 알고리즘을 찾는다(결국 공부했던 알고리즘 중 하나일 것이다)

다른 사람의 코드 읽기

문제를 풀고 난 후에는 다른 사람의 코드를 읽는다. (최소 3개)

일반적으로 짧을수록 더 잘 작성된 코드인데, 제출한 코드보다 시간과 코드 길이가 더 짧은 풀이가 있다면 보고 배우자. 이 과정에서 다른 사람의 코드를 읽더라고 읽는 연습도 할 수 있다.
같은 결과지만 더 기발하고 효율적으로 작성한 코드들을 찾으면 본인의 것으로 만든다.

다른 사람의 코드를 보지 않았더라면 스스로 생각하고 이해하기까지는 10문제 20문제, 그 이상 풀어야겠지만 다른 사람의 코드를 본다면 더 효율적으로 공부하여 엄청난 가성비 성장을 할 수 있다.

물론 코드를 보기만 하는 게 아니라 새롭게 배운 방법을 토대로 코드를 새로 짜서 제출을 해야 한다.

이렇게 하나의 문제를 한 번만 푸는 게 아니라 2~3번을 점점 나은 방식을 통해 풀면서 새로 익히는 알고리즘에 대해 더 깊은 이해를 하게 되고 구현 능력도 더 빨리 키우게 된다

문제를 풀지 못한 경우

어떻게 풀지 아예 감도 안 오는데 1시간이 지나갔다면 구글에 검색하자. 먼저 작성자의 풀이를 먼저 보고 그래도 모르면 코드를 보자. 코드를 보면서 그대로 치는 것은 추천드리지 않는다.(왜?)

블로그 풀이의 코드까지 봤는데도 이해가 안 되고 코드도 못 치겠다면 해당 알고리즘을 이해하지 못한 상태이니 첫 부분인 1. 블로그, 책으로 알고리즘 공부하기로 가셔서 개념공부를 하자.

1시간 이상 고민하는 것은 집중이 깨지기 쉽고 흥미도 떨어져 효율이 나빠지게 된다.
그리고 1시간 미만으로 고민하는 것은 코딩 테스트 환경을 대비했을 때, 추천하지 않는다고 한다. 코테 환경에서 보통 1시간 정도 고민하는데 이렇게 장시간을 고민하는 것도 훈련을 해 놔야지 실전에서 문제를 풀 수 있다고 한다.