PS 문제를 풀 때 유용한 팁들

제가 지금까지 PS 문제를 풀 때 깨달은 유용한 팁들을 한 번 공유해보고자 합니다. 들어가기 앞서서, 여기에 적은 내용들은 전부 지극히 저의 주관적인 생각들입니다. 따라서 제 생각이 틀렸을 수 있으니 참고만 하시면 좋습니다. 그리고 피드백은 언제나 환영이니 댓글로 마음껏 해주시면 감사하겠습니다 :)

 

1. 시간 제한은 1초에 1억(10^8)번 연산이 가능하다고 생각하는게 편합니다.

 

저는 '1초 = 1억번의 연산'이라는 가정을 세우고 가능한 시간복잡도를 계산해봅니다. 주로 정해의 시간복잡도에 따른 연산 횟수를 계산해보면 이 공식이 맞는 것 같습니다. 물론 연산이 간단한가 어려운가에 따라서나 붙는 상수에 따라서 1초에 가능한 연산의 횟수가 커질 수 있긴 합니다. (그래서 저도 계산을 해보았을 때, 1억번을 '약간' 넘는 경우라면 그냥 한 번 시도를 해봅니다.) 그래도 '1초 = 1억번' 이 공식으로 문제를 풀었을 때는 TLE 난 경험은 거의 없었습니다. 

 

2. 알고리즘이 시간내에 돌아갈 수 있음을 시간복잡도로 증명을 할 수 있지만, 역으로 가능한 시간복잡도로 어느 알고리즘이 정해일 지 유츄가 가능합니다.

 

시간 제한에 알맞는 시간복잡도를 먼저 계산하면 이와 같거나 더 빠른 알고리즘들만 고려하는 것으로 선택의 폭도 줄일 수 있습니다. 예를 들어서, 최단거리 문제인데 정점의 개수 V 및 간선의 개수 E에 따라서 가능한 시간복잡도가 O((V+E)logV)까지만 가능하다면 이보다 더 느린 시간복잡도를 가진 O(VE)나 O(V^3)인 Bellman-Ford나 Floyd-Warshall은 고려대상에서 없앨수가 있죠.

 

다만, 예외는 있을 수가 있습니다. 사이트나 채점 시스템 특성상 시간복잡도 상으로는 더 느려도 코드가 더 빠르게 돌아가는 경우도 존재합니다. 이러한 경우에는 시간복잡도에는 붙지 않은 상수가 매우 커서 그럴수도 있습니다. (예전에 SW Expert Academy에서 이런 증상을 가끔씩 겪어봤던 것 같습니다. SW Expert Academy 서버가 좀 상수 영향을 매우 받아서 그런지 상수 커팅이 중요했던것 같습니다.) 

 

3. PS를 할 때는 본인이 제일 자신있는 언어로 시작하는게 제일 좋습니다.

 

언어들마다 항상 장단점은 존재합니다. 예를 들어서 제가 사용하는 언어 중 제일 빠른 C++과 제일 느린 Python을 비교해서 설명해보도록 하겠습니다.

 

C++

 

장점

• 엄청 빠릅니다. 어지간한 문제들은 C++로는 항상 풀립니다. Competitive Programming에서는 특정 언어에서는 못 풀 수 있는 
• 재귀 깊이도 파이썬에 비해서 훨씬 문제가 없습니다. 그리고 무려 PBDS나 Rope같은 자료구조들도 지원합니다.
• C를 해보았다면 STL이랑 C++ 문법 몇 개만 추가적으로 공부하면 됩니다.
• #include <bits/stdc++.h> 이렇게 어지간한 라이브러리들을 묶어놓은게 있어서 어느 라이브러리에 뭐가 있는지를 굳이 안 외우고도 풀 수 있다는 소소한 장점이 있습니다.

 

단점

• 큰 수 연산이나 모듈로 역원 등. 수학 관련하여 직접 구현하는 방법 및 사전 지식을 알고 있어야 구할 수 있습니다. (저만 해도 FLT로만 구현할 줄 알다보니 모듈로를 해주는 값이 소수가 아니면 확장 유클리드 호제법을 몰라서 못 구해요...)
• 문자열을 조작하는 문제등이 나오면 불편하기도 합니다. 특히나 저 같은 경우에는 한 번에 받아야 할 문자열이 공백으로 구분이 되는게 아니라면 그냥 Python을 사용합니다.
• 같은 걸 구현하더라도 C++은 Python에 비해서 비교적 더 길게 적어야 합니다. 그래서 실제로 쉬운 문제라면 저도 그냥 Python을 씁니다.

 

Python

 

장점

• 큰 수 연산이 가능합니다. (큰 수 연산이 지원이 안 되는 C나 C++에서는 곱셈을 해야하면 고급 알고리즘인 FFT를 사용해야합니다. BOJ 13277과 BOJ 15576의 난이도를 비교해보시면 체감이 될 겁니다.)
• 그리고 모듈로 역원을 찾는 함수 등 든든한 built-in 함수들이 많습니다.
• 문자열 조작도 쉬운 편입니다. 그래서 실제로 문자열 문제라면 저도 Python을 씁니다.
• 코드 길이가 비교적 짧아서 읽기도 편합니다. 또한, 배우기도 엄청 쉬운 언어기도 하구요. 

 

단점

• 너무 느려서 시간복잡도 상으로는 괜찮아도 억까를 당하는 경우도 존재합니다. 시간 제한을 더 줘도 못 푸는 경우도 있더라구요.
• 또한, 재귀 깊이에 상한선이 존재해서 필요시에는 비재귀로 구현하는 테크닉을 활용해야하는 경우도 있다고 합니다. (물론 재귀 깊이를 새로 설정해줄 수 있지만, 메모리가 터지는 경우도 있습니다.)
• Multiset을 지원해주지 않는 걸로 알고 있습니다. 또한, PBDS나 Rope를 지원해주지 않는 점도 있습니다. (PBDS는 Segment Tree + Binary Search + Value Compression을 다 구현해주면 되긴 합니다. Rope는 저도 트리 자료구조인 점 빼고는 잘 모르긴 해요.)

 

이렇듯 언어별로 장단점이 존재합니다. 그리고 느린 언어라고 해서 Competitive Programming 등이 아에 불가능하지는 않습니다. 제 주변에 지인만 봐도 Python 유저인데 코드포스 오렌지까지 달았던 사람도 보기도 했습니다. 그리고 코딩테스트 같은 환경은 아에 Python으로도 풀리도록 문제가 갖춰져 있을테니 PS 목적이 코딩테스트 공부라면 더욱이나 상관 없습니다. 본인이 많이 사용해본 걸로 시작하세요! 

 

3-1. 다만 본인이 PS는 처음이고 어느 언어로 시작할지 모른다면 조심스럽게 한 번 C++로 시작 해보시는 걸 추천드립니다.

 

C++를 한 번도 안 배워봤다고 해도 C는 전공 수업 등으로 한 번쯤 공부해보셨을 것이라 생각합니다. C를 해봤다면 C++도 그리 어렵지 않는게 PS를 하면서 쓰는 기술은 사실상 C와 STL밖에 없기 때문입니다. 애초에 C++를 사용하는 이유도 C의 빠른 속도와 우수한 STL을 활용하기 위해서 그렇다고 생각합니다. 그래서 추가적으로 STL이랑 Fast I/O 및 C++ 문법을 몇개 정도 익혀두면 C++로도 쉽게 문제를 풀 수가 있습니다. 이렇게 C를 해본 입장에서는 배우기도 쉬우면서도 속도도 빨라서 상수 커팅 등등을 어느정도 덜 신경써도 되기도 해서 저는 C++를 추천드립니다. 실제로 최상위 잘 하는 사람들은 주로 C++로 문제를 풉니다. (Rust도 쓰는 것 같긴 한데, 일단 제가 저 언어를 몰라서 패스하겠습니다.)

 

다만 C도 안 했거나 자신이 없는데 시간도 없다면 배우기 쉬운 Python을 쓰는 것을 추천드립니다. Python이 그리 어려운 언어도 아니기도 하고, 문제가 생겼을 때 C++의 Segmentation Fault 같이 직접 디버깅을 해서 원인을 알아내야 하는 경우도 거의 없고 어디서 문제가 생겼는지를 인터프리터가 직접 짚어주기도 때문에 디버깅도 쉽습니다. 다만 대회까지 생각이 있으면 시간을 내서 C++도 익히는 걸 추천드립니다.

 

4. 문제를 풀 때 가능하다면 랜덤디펜스를 하는 게 실력 향상에 제일 도움이 되는 것 같습니다. 

 

일단 설명하기 앞서서 저는 랜덤디펜스를 백준에서만 했기 때문에 백준 위주로만 설명하겠습니다. Programmers이나 SWExpertAcademy, Softeer 같은 경우에는 난이도가 어차피 백준에 비해 세부적으로 나누어져 있지 않아서 밑에서 제가 설명할 방법처럼 할 필요는 없고 그냥 어느 알고리즘을 사용하는지 가리고 풀면 될 것 같습니다. 

 

Competitive Programming이나 코딩테스트에는 어느 알고리즘의 문제가 나올지는 아무도 모릅니다. 본인이 아무리 그래프 문제를 잘 푼다고 하더라도 문제가 전부 DP, 수학, 애드 혹으로만 나올 수도 있습니다. 물론 대회 특성상 선호되어 자주 출제되는 알고리즘도 존재하기도 하고, 난이도가 너무 높은 경우에는 안 나오는 경우도 있습니다. 그래도 의도치 않게 해당 문제들이 나와도 풀 수가 있어야 하며 이러한 능력을 향상 시키는 데는 랜덤디펜스가 제일 좋은 것 같습니다.

 

랜덤디펜스는 문제의 난이도 및 알고리즘 태그를 가리고 랜덤하게 문제를 선정해서 시간제한 내에 푸는 겁니다. 세부적인 방법은 각각 사람마다 다를 수 있는데 크게 두 가지가 있는 것 같습니다. 첫 번째로는 난이도 범위를 정하고 랜덤하게 문제들을 받아서 푸는 방법이 있고, 두 번째로는 첫 시작을 어느 난이도로 찝어서 시간 내에 풀면 다음에는 더 높은 난이도를, 풀지 못하면 더 낮은 난이도 문제를 도전하는 방법이 있습니다. (두 번째 방법은 업다운 랜덤디펜스라고도 합니다.)

 

다만 랜덤디펜스라고 해서 모든 태그를 꼭 풀거나 그럴 필요가 없습니다. 본인이 너무 자신이 없거나, 몰라서 공부한 후에 보고싶은 태그들은 제외해서 랜덤디펜스를 돌리기도 합니다. 또한, 푼 사람 수가 너무 적으면 틀렸을 때 답을 복기할 수 없는 경우가 생길 수도 있어서 푼 사람수가 몇 명 이상인 문제들만 랜덤하게 받기도 합니다.

 

제가 랜덤디펜스 돌리는 것을 예시로 삼아서 설명해보겠습니다. 저는 두 가지 방법을 모두 병행합니다. 공통적으로 저는 아래와 같이 제한을 둡니다.

• 푼 사람수 100 명 이상
• 기하 및 내가 아에 모르는 태그는 제외

이러한 조건속에서 저는 여유가 있으면 G3 ~ P5 문제를 아니면 G5 ~ G3 사이의 문제들 중에서 랜덤하게 풉니다. 업다운 랜덤디펜스는 G5부터 시작해서 현재 G3에 머물러 있구요.

 

이 외에도 제가 어쩌다가 알게된 모두의 랜덤디펜스 사이트를 활용해서도 가끔씩 랜덤디펜스를 돌리는데, 여기서는 제가 잘 모르는 태그도 없기도 하고 난이도 폭도 적당해서 이 사이트를 활용하는 것도 좋아보입니다. 코딩테스트 준비하기도 괜찮을 것 같구요.

 

이외에는 (물론 위의 글들도 모두 제 주관이 들어갔지만)아주 개인적인 저의 생각들입니다. 이 부분에 대해서는 의견이 좀 갈릴 수는 있어는 보입니다.

 

• 저는 새로운 태그를 공부한다면 이에 대한 예제나 기본 문제 몇 개 정도는 인터넷에 있는 답을 참고해서 푸는 것도 좋은 방법이라 생각합니다.
  • 이를 통해서 해당 태그가 어떤 식으로 응용되는지 및 어떤 유형의 문제의 꼴을 가지고 있는지 등을 파악할 수도 있고, 구현도 반복하게되어 로직도 익히면서 손에도 해당 알고리즘이 익히겠죠.

• Greedy 문제들은 평소에 문제를 풀 때, 증명하는 과정도 꼭 해보는게 필요하다고 생각합니다. 아에 수식적으로 증명하면 베스트이긴 하지만, 그게 안 되더라도 '~를 하니 이렇게 greedy하게 풀린다~' 이런 생각하는 연습은 필요한 것 같습니다.
  • 저도 어지간하면 이렇게 증명을 최대한 해서 푸는 연습을 합니다. 물론 저도 시간제한이 있는 등의 이유로 대충 짐작해서 greedy하게 푸는 경우도 있지만, 이렇게 푼 문제들은 나중에 왜 이게 greedy하게 풀 수 있었는지 고민을 해봅니다. 이러한 연습들이 있어야 실제 대회나 코딩테스트에서도 greedy 문제가 나오면 greedy일 것이라는 감도 잘 오고 본인의 풀이에 더욱 확신을 갖게 되는 것 같습니다. 그리고 이런 연습을 해야 AC를 대회나 시험 끝나고 알 수 있는 환경에서는 본인의 풀이를 검토할 수가 있겠죠? (예 : HSAT, 삼성전자 B형 Pro 검증, HackerCup)
• DP 문제들은 greedy 보다도 수식으로 꼭 증명해보는 연습이 필요하다고 생각합니다. 결국 DP 문제의 제일 큰 난관은 'DP 테이블을 어떻게 짤 것인가?'인데, 이는 평소에 수식으로 증명하는 연습을 해야 수월하게 계산이 되는 것 같습니다.
  • 또한, 너무 웰노운 DP(예: Knapsack DP, MCM DP 등등.)더라도 그냥 수식을 외우는게 아니라 수식을 이해를 해야 이걸 한 번 꼬아서 DP 테이블에 약간의 variation이 들어간 문제도 쉽게 풀 수 있다고 생각합니다.
  • 이것외에도 DP는 크게 보았을 때의 Knapsack DP, LIS, MCM DP 등등. 특정 유형으로 귀결되는 경우들이 종종 있어서 여러 유형의 DP들을 꼭 풀어보는 것도 중요한 것 같습니다. 저는 만약에 현재 풀고 있는 DP문제가 어떤 유형인지 파악했으면은 해당 DP에서의 유명한 점화식을 조금만 더 비틀면 어지간하면 다 풀렸었습니다.
• 처음으로 PS를 한다면 기본적인 알고리즘들을 먼저 BFS식으로 하나하나 훑어보는게 더 나은 것 같습니다. 특정 알고리즘을 깊게 파는 것은 좀 비추천드립니다.
  • 여기서 깊게 파는 것에 대한 기준은 다음과 같습니다. 실제 제가 했던 예시를 들자면, 저는 Sudoku 문제에서 Backtracking 문제가 재밌어서 DP / Greedy 등의 문제들도 제대로 모르는 상태에서 Dancing Link + Knuth X 알고리즘을 공부했었습니다. 또한, 기하학도 궁금해서 DP / Greedy 보다 Graham Scan을 먼저 공부했었고요...(각각 Solved.ac 기준으로는 D2, P5에 해당되는 알고리즘들 입니다.) 또한 Segment Tree가 그렇게 사기라길래 실랜디도 안 되는 상황에서 공부했었습니다.
  • 이렇게 깊게 파는 것을 추천드리지 않는 이유는 간단합니다. 어차피 본인이 기본 실력이 없는데 이런 어려운 알고리즘들을 배워도 응용 문제들은 못 풉니다. 그리고 사실 어려운 알고리즘들이면 기본 실력도 없으면 이해하기도 어려워요.
  • 그래서 저는 전체적으로 기본적인 Bruteforcing / DP / Greedy / Graph(탐색, 최단거리 등등.)등을 먼저 공부하는게 좋다고 생각합니다. 적어도 최소 골드 하위권(G5 ~ G4)까지의 문제 유형들을 아직 공부해보지 못했다면 이렇게라도 먼저 공부를 하는게 좋다고 생각해요. 

 

여기까지가 제가 생각나는대로 적은 팁들입니다. 추가적으로 생각나는게 있다면 다시 업데이트를 해보도록 하겠습니다.