몇 분 정도 고민한 후에도 감이 안오면 해설을 보는게 좋을까요? / 문제를 보고 어떤 알고리즘이 사용될지는 어떻게 알 수 있나요?

라는 질문에 대한 제 생각을 써봅니다.

 

A. 몇 분 정도 고민한 후에도 감이 안오면 해설을 보는게 좋을까요?에 관해..

 

일단 한줄 요약으로 생각을 정리하면 알고리즘 공부 경험이 적다면/코딩테스트 통과만이 목표라면 답을 빨리 참고하고(30분 이내), 공부 경험이 많다면/대회에서 좋은 성적을 내고 싶다면 고민하는 시간을 길게 가져가는걸 추천드립니다.

 

초보 단계에서는 주어진 문제가 내가 알고 있는 지식의 범위 내에서 풀린다는 확신을 하기가 어렵습니다. 이 지식의 범위에는 알고리즘에 대한 지식과 테크닉에 대한 지식이 모두 포함됩니다. 예를 들어 다익스트라 알고리즘을 공부한적 없는 사람이 최단 경로 문제를 풀어낼 수 있을리 없고, 설령 이분 탐색을 알더라도 매개 변수 탐색을 한 번도 본적이 없다면 매개 변수 탐색을 스스로 떠올리는건 불가능에 가깝습니다(지금에야 다익스트라 알고리즘과 매개 변수 탐색 모두 과장 조금 보태서 정보올림피아드를 공부하는 초등학생/중학생도 익힐 수 있는 내용이라 쉽게 보일 수 있지만 처음으로 세상에 등장할 때에는 세계적인 석학의 손에서 나왔습니다).

 

만약 주어진 문제가 내 지식 범위에서 풀 수 있는 문제라면 문제를 놓고 깊게 고민해보는게 문제 해결 능력을 기르는데에 좋은 훈련이 됩니다. 하지만 30분 정도 고민해도 실마리가 전혀 안잡힌다면 초보 단계에서는 내 지식 범위에서 풀 수 없는 문제일 가능성이 큽니다. 그렇기 때문에 고민하는 시간을 줄이고 풀이를 빠르게 확인하면서 알고리즘/테크닉을 습득하고 구현력을 늘려나가는걸 추천드립니다. 한편으로 내가 새로운 개념을 익히기 위해 의도적으로 어려운 문제를 풀고 있는 상황이라면 상관이 없지만, 그게 아니고 연습용으로 문제를 적당히 골라잡아 푸는데도 풀이를 모르겠어서 답을 봐야 하는 문제가 절반이 넘는 상황이라면 문제 난이도를 조금 더 낮춰서 연습을 하는걸 추천드립니다.

 

하지만 어느 정도 알고리즘/테크닉을 많이 익힌 후에도 조금만 막히면 해설에 의존하는건 별로 좋은 방법이 아닙니다. 그렇게 되면 뭔가 아는게 많아진 것 같은 착각이 들지만 스스로 생각하는 힘을 기르지 못해 새로운 문제를 봤을 때 잘 풀어내지 못할 수 있습니다. 특히 불필요하게 티어에 집착을 하다보면 이런 경향을 보이기 쉬운데 공부를 하는 목적이 티어를 올리기 위함인지 아니면 대회에서 좋은 성적을 내기 위함인지 되짚어볼 필요가 있어보입니다. 노파심에 첨언하자면, PS 공부를 하는 목적이 반드시 대회 수상이어야 한다는 뜻은 아닙니다. 대회에 큰 뜻이 있다기보다는 단지 지적유희이거나 논문을 읽고 구현하며 고난이도 문제를 푸는 것에 더 흥미를 느낄 수 있습니다. 하지만 대회에서 수상을 하고 싶다면 스스로 생각하는 시간을 많이 가져보는걸 추천드립니다. 길게는 일주일 가까이 머릿속에 집어넣고 밥먹을때, 자기 직전에 등등 백그라운드에서 계속 돌리는 것도 좋습니다. 또 고급 개념들을 계속 익히는 것도 좋지만 적당한, 혹은 약간은 쉽지 않나 싶을 정도의 난이도의 문제를 풀어보는 것도 추천드리는데 꽤 낮은 난이도의 문제에서 의외로 고전하거나 새로운 깨달음을 얻어가는 일이 종종 있습니다. 저는 현재 코드포스 2410, solved.ac 기준으로 D3이고 P1 이상의 문제를 풀지 않으면 AC 레이팅에 변화가 없는 상황임에도 불구하고 때때로 골드 상위나 플래티넘 하위 정도의 문제에서 사고가 막힐 때도 있고 좋은걸 배워가기도 합니다. 가장 최근에 유튜브에 올린 2022 카카오 인턴십 코딩테스트를 푸는 영상에서도 (3번은 코딩 실수이니 제외하고) 4번, 5번 모두 대충 플래티넘 하위 정도의 난이도인데 한참 고생을 했고, 또 BOJ에서 최근에 푼 문제중 가장 인상 깊었던 문제는 P5인 BOJ 20304번 - 비밀번호 제작 이네요. 물론 제가 접은지 대충 3년이 다되어가는 퇴1물인걸 감안하셔야 하지만 아무튼 그렇습니다.

 

B. 문제를 보고 어떤 알고리즘이 사용될지는 어떻게 알 수 있나요?에 관해..

 

"어떤 알고리즘을 사용해야 하는지 갈피를 바로 못 잡는 것"에 대한 어려움은 공부를 아무리 많이 했어도 해소가 안된다고 생각합니다. 저도 어려운 문제를 풀어나가다보면 갈피를 못잡을 때가 많죠. 그렇기 때문에 이걸 완벽하게 해결할 수 있는 방법은 없다고 생각하지만 문제를 풀 때 제 머릿속에서 벌어지는 일을 정리해보면 도움이 될 것 같아서 정리를 해보겠습니다.

 

1. 문제를 이해하고 요구하는 시간복잡도 계산(원소 탐색을 최대 50만번 하니까 아마 각 탐색 당 O(lgN) 혹은 O(1)이겠구나)

 

2. 문제에 필요한 연산과 주어진 조건을 보면서 사용되는 자료구조/알고리즘을 유추하기(앞뒤에서 삽입/삭제를 빠르게 해줘야 한다 -> deque,  접두사나 접미사를 가지고 계산을 해야한다 -> 트라이, 그래프로 환원이 가능하고 간선의 가중치가 모두 같은 상황에서 최솟값을 구한다 -> BFS, 탐색 범위가 10^18과 같이 굉장히 큰데 결정 문제로 바꿀 수 있을 것 같다 -> Parametric search 등)

 

3. 이전에 풀었던 비슷한 문제를 떠올리면서 착안

 

4. 여전히 감이 안오면 내가 알고 있는 알고리즘을 하나씩 넣어보면서 상황과 잘 맞아떨어지는지 확인

 

5. 이렇게까지 해도 모르겠으면 문제의 난이도를 슬쩍 확인한 후 난이도가 쉽다면 머리를 쥐어뜯으며 계속 고민, 난이도가 높다면 알고리즘 분류를 먼저 확인하거나 그냥 답을 참고함

 

이런 느낌으로 진행합니다.

 

그리고 이 과정에서 문제에 필요한 연산과 주어진 조건을 보면서 사용되는 자료구조/알고리즘을 잘 유추하기 위해서나 비슷한 문제로부터 착안을 해내기 위해서는 특정 알고리즘을 공부한 후에 다양한 응용 사례와 테크닉을 공부해야 합니다. 예를 들어 BFS만 하더라도 제일 기초는 flood fill이지만 여기서 출발해 거리 측정, 여러 시작점에서의 bfs, 서로 다른 종류에서 동시에 진행되는 bfs, 상하좌우 대신 knights의 움직임대로 bfs 등 수많은 바리에이션이 있죠. 처음 이런 응용 문제를 보고 혼자 힘으로 풀기는 어려울 수 있지만 일단 테크닉을 한 번 익히고 나면 잘 써먹을 수 있습니다. 그렇기 때문에 여력이 된다면 응용 문제를 계속 시도해보는게 좋습니다. 그리고 실전 환경과 같이 알고리즘 분류/난이도를 모른 채로 문제를 푸는 연습도 병행할 필요가 있습니다.

 

두 질문에 대한 답변을 총정리하면

 

1. 알고리즘 공부 경험이 적다면/코딩테스트 통과만이 목표라면 답을 빨리 참고하고(30분 이내), 공부 경험이 많다면/대회에서 좋은 성적을 내고 싶다면 고민하는 시간을 길게 가지기

 

2. 어느 정도 알고리즘/테크닉을 많이 익힌 후에는 조금만 막히더라도 해설에 의존하는 식으로 공부를 하지 말고 생각을 오래 해보기

 

3. 각 알고리즘의 응용 문제를 많이 풀어보기

 

4. 알고리즘 분류/난이도를 모른 채로 문제를 푸는 연습을 병행하기

 

입니다.