나는 어떻게 PS 및 코딩테스트 문제들을 푸는가?

제가 지금까지 PS를 공부하면서 문제들을 볼 때 어느 과정들을 거쳐서 풀었는 지를 공유하면서, 겸사겸사 팁들도 공유하려 합니다.

코딩테스트는 제가 주로 풀어본 문제들과는 약간 다른 양상이 있지만(좀 더 구현 위주의 문제들이 나오는 것 같습니다.) 그래도 제가 드리는 팁들은 어느정도 먹힐거라 생각합니다.

문제 푸는 순서

제가 문제를 푸는 순서는 주로 다음과 같습니다.

 

1. 문제에서 요구하는 바 및 제한 사항들 확인하기.

2. 요구하는 것 및 문제 형태를 보고 어느 문제인지 짐작하기.

3. 제한 사항을 보고 시간 제한내로 풀리는 시간복잡도를 계산해보기

4. 2번 및 3번에서 생각한 것들을 토대로 문제를 풀 수 있는 알고리즘을 떠올리기.

5. 구현하고 문제 없는지 재점검하기.

6. 틀렸으면 코드에 대한 반례을 찾기.

 

물론 모든 문제들을 이렇게 풀지는 않긴 하지만 주로 이런 순서대로 생각하고 풀게 되는 것 같습니다.

그러면 이제 각각 순서에 대해서 좀 더 자세히 풀어보겠습니다.

 

1. 문제에서 요구하는 바 및 제한 사항들 확인하기.

처음에 문제가 주어지면 '이러이러한 조건들이 주어져있을 때 ~를 구하여라'를 먼저 파악해야합니다.

그러면서 같이 확인 해야할게 시간 및 메모리 제한과 주어진 변수들의 대한 값의 범위도 파악해야합니다.

이걸 먼저 파악하는 연습은 매우 중요합니다.

 

특히나 시간 및 메모리 제한, 주어진 변수들에 대한 제한 사항들은 문제를 푸는데 핵심적인 역할을 하는데, 이걸 어떻게 활용해야할지 모르는 사람들은 그냥 지나치게 됩니다. (저도 초심자때 그랬었구요.)

밑에 다시 설명하겠지만, 1초에는 대략 1억번(10^8)의 연산이 가능하다고 생각하고 문제를 풀면 됩니다. 

 

2. 요구하는 것 및 문제 형태를 보고 어느 문제인지 짐작하기.

몇몇 문제들은 어느 정도 문제 형태를 보고 문제 유형을 유추가 가능합니다.

예를 들어서, '마을들이 왕복이 가능한 도로들로 이어져 있다 ~' 이러한 문제가 있다고 합시다.

그러면 일단 이 문제에서 저 문구가 중요하게 작용된다면, 이 문제는 그래프 문제일 것이라고 유추할 수가 있습니다.

 

물론 이 유추가 항상 옳은 방향으로 이끌어 주는 것은 아닙니다. 

(만약 예시로 들은 문구 이후에 '그런데 마을들을 이어주는 도로들이 하나씩 끊어지기 시작했다. 그러면 각 도로들이 순서대로 끊어질 때, 모든 도시들이 서로 방문할 수 없는 시점을 구하시오.' 이러한 문구가 들어가 있다면 이 문제는 그래프 문제가 아닙니다. Offline Query + DSU 문제죠.)

그래도 이렇게 유추를 하는 연습은 매우 도움이 되기도 하고, 연습을 계속할 수록 더 정교해지게 됩니다.

이러한 실력을 늘리는 방법은 여러 유형들의 문제들을 많이 풀어보는 것 외에는 방법이 없습니다.

 

3. 제한 사항을 보고 시간 제한내로 풀리는 시간복잡도를 계산해보기

위에서 언급한 1초 = 1억(10^8)번 연산이라는 공식이 빛을 발하는 순간입니다.

사실 정확히 따지자면 연산에 따라서 1초에 가능한 횟수가 매우 달라지긴 합니다만, 주로 3~4억번은 어찌저찌 가능하고 1억번 내로는 확실하게 가능해서 편의상 저렇게 생각하는게 좋습니다.

1초에 1억번의 연산이 가능하다는 걸 알면 시간 제한과 변수들의 값 범위를 같이 고려해서 알고리즘 시간복잡도를 유추할 수 있습니다.

 

예시로, 시간제한 1초에 N의 범위가 1 ~ 1'000'000(10^6)라고 합시다.

그렇다면 1초 내로 연산이 가능해야하므로 O(N^2)는 불가능할 것입니다. (최대 10^12번의 연산을 할 수 있기 때문이죠.) 

위 조건에서 가능한 시간복잡도는 O(N), O(NlogN) 정도일 것입니다.

이렇게 계산이 되었다면 다음 단계에서 우리는 위의 시간복잡도를 가지는 알고리즘 및 자료구조들만을 고려하면 됩니다.

즉, 해당 시간복잡도보다 더 느린 알고리즘들은 고려대상에 들어가지 않는 것이지요.

 

저는 2번 및 3번 단계는 주로 병행해서 생각하는 편입니다.

순서를 뒤 바꿔서 생각을 하는 경우도 많구요.

 

4. 2번 및 3번에서 생각한 것들을 토대로 문제를 풀 수 있는 알고리즘을 떠올리기.

앞서 2번 및 3번 단계에서 생각한 내용들을 합치는 과정입니다.

 

예시를 들자면, 문제의 조건이 '어느 두 도시를 최단 경로로 갔을 때의 걸리는 시간을 구하는 것'이라서 그래프 탐색 문제임을 알아내었고.

시간복잡도를 보았을 때 O(V+E)이나 O((V+E)logV) 정도의 시간복잡도를 가지는 알고리즘이 시간내에 풀린다면

우리는 '이 문제는 Dijkstra(시간복잡도 : O((V+E)logV))로 푸는 문제구나'라고 떠올릴 수 있습니다.

심지어 각 경로의 비용이 모두 동일하다면 'BFS로 더 빠르게 풀 수 있겠다'라는 생각도 할 수 있습니다.

 

이외에도 O(V^3)까지도 가능하면 Floyd-Warshall을, 음의 사이클이 존재하는데 O(VE)가 허용되면 Bellman-Ford를 활용해서 문제를 풀 수 있다는 것을 알 수 있습니다.

 

이러한 계산을 할려면 당연히 각 문제 유형에 대한 알고리즘들과 시간복잡도를 모두 숙지하고 있어야 합니다.

팀노트나 검색이 불가능한 상황에서는 구현 방법도 숙지하고 있어야하죠.

 

5. 구현하고 문제 없는지 재점검하기.

문제를 구현했으면 off-by-one 에러 등등이 존재하는 가를 생각하는 과정입니다.

이건 주로 대회 등에서 하는 작업인데, 대회에서는 한 문제를 틀릴때마다 패널티가 추가됩니다.

이를 방지하기 위해서는 점검하는 작업이 필수적입니다.

 

6. 틀렸으면 코드에 대한 반례을 찾기.

당연히 틀렸으면 방금전 제출한 코드에서 어느 부분을 틀렸는지를 확인하는 작업을 해야합니다.

내가 생각한 알고리즘이 틀렸는가? 구현이 잘못되었는가? 등등을 찾아내야 하는데, 이를 빠르게 찾아내는 방법 중의 하나가 반례를 찾아내는 것이라고 생각합니다.

반례도 스스로 생각해내는 연습이 필요한데, 저는 주로 'edge-case들이 무엇이 있을까'를 생각해서 edge-case들을 만들고 한 번씩 대입해봅니다.

 

이로써 제가 문제를 푸는 과정 및 소소한 팁들을 공유해보았습니다.

좀 당연한 소리들만 했지만, 그래도 이 글이 어느 정도 도움이 되었다면 다행입니다 :)