취미로 백준을 풀어보려는 사람에게

저는 고등학생 시절 정보올림피아드를 준비해본 적도 있고, 학교 전공 수업에서도 여러 이론들을 접했지만, 꽤 오래 개발만을 하면서 알고리즘과는 멀어져 있었습니다. 그러나 모종의 이유로, 최근 백준을 시작했습니다. 언어는 가장 기본이라 생각되는 c++로 정했습니다. 약 한 달 정도 백준을 풀어본 지금, 백준을 시작하려고 하는 과거의 저에게 알려줬다면 관심있게 들었을 내용들을 소개해보고자 합니다.

 

solved.ac

백준을 시작하려는 마음은 먹었으나, 어떻게 시작해야할지 당혹스러울 수 있습니다. 처음에는 백준에서 제공하는 단계별로 풀어보기탭을 이용하였고, 이 순서대로 문제를 풀어보는 것도 나쁘지 않아 보입니다. 하지만, solved.ac는 훨씬 강한 동기부여를 제공합니다. solved.ac는 내가 해결한 문제들을 바탕으로 나의 티어를 책정합니다. 이 티어를 올리기 위해서라도 백준 문제를 꾸준히 풀게 되었습니다. 또한, 풀만한 문제들을 클래스별로 제공하고, 문제들을 난이도와 태그로 구분하고 있어서, 어떤 문제를 풀어야할지 큐레이션해줍니다. 현재 저는 티어는 고작 골드4에, class 4*의 모든 문제를 풀었다고 이 글을 써보고 있습니다.

제 티어입니다 ㅎㅎ

 

로드맵

클래스4까지 풀어보니 거의 모든 알고리즘 문제들은 아래의 5가지 카테고리 안에 묶일 것 같았습니다. 

• 재귀 구현
  • DFS, BFS로 그래프를 순회하거나, 스도쿠, N-queen 문제처럼 백트래킹을 잘해야하는 문제들입니다. '별그리기'처럼 분할정복을 요구하기도 합니다.
• 다이나믹 프로그래밍
  • 배낭문제나 누적합구하기 등 다양한 유형들이 있습니다.

위의 두 카테고리는 기본적인 원리를 이해하고, 그 이후에는 프로그래밍적인 감각으로 풀어내야하는 유형들이라면, 아래는 기초가 되는 알고리즘들을 알고 잘 적용하는 것이 중요한 유형들입니다.

• 그래프
  • 그래프의 간선(edge)들 중 일부를 택하여, 모든 정점(vertex)들을 연결하는 최소의 방법을 구하는 것은 최소신장트리(MST, Minimum Spanning Tree)를 구하라는 것과 같은 말입니다. 간선 중심의 크루스칼(Kruskal's) 알고리즘은 O(ElogE)의 시간복잡도를, 정점 중심의 프림(Prim's) 알고리즘은 O(V^2)의 시간복잡도를 가지니, 문제 상황에 따라 적절한 알고리즘을 골라야합니다.
  • 어느 정점에서 다른 모든 정점들 사이의 거리들을 모두 알고 싶으면 다익스트라(dijkstra) 알고리즘을 사용해야합니다. 그런데, 주어진 그래프에 음수 거리가 있거나, 음수 사이클의 유무를 알고 싶다면 밸만-포드(Bellman-Ford) 알고리즘을 사용합니다. 각각 O((V + E)logV)와 O(VE)의 시간복잡도를 갖습니다.
  • 모든 두 정점들간의 거리를 알고 싶다면 플로이드-워셜(Floyd-Warshall) 알고리즘을 사용합니다. 무려 O(V^3)의 시간복잡도입니다.
• 트리
  • 전위/중위/후위순회를 알아야 합니다.
  • 트리의 지름을 구하는 법은 다음과 같습니다. 1. 임의의 한 지점에서 가장 먼 노드 a를 찾는다. 2. 다시 그 노드에서 가장 먼 노드 b 를 찾는다. 3. a와 b 간의 거리가 곧 트리의 지름이다. 
• 수학
  • 이 카테고리는 배경 지식이 없다면 정말 풀기 어렵다고 생각합니다. 분할정복으로 피보나치 수를 O(logN)만에 구한다거나, 좌표가 주어졌을때 다각형의 넓이를 구한다거나, 선분들의 교차 여부를 확인한다거나, 정수론적인 지식들을 요구합니다.

 

유용한 라이브러리와 팁

저는 c는 사용해봤지만, c++은 이번에 처음 사용해봤습니다. 미리 알았다면 좋았을지도 모를, c++의 유용한 라이브러리 및 팁들을 소개합니다.

• #include <vector>
  
  • 선언할때 최대 크기를 지정하지 않아도 되는 동적인 배열입니다. 대표적으로, 그래프의 연결상태를 저장하는 인접리스트(adjacent list)를 선언하기 위해 자주 사용됩니다.
• #include <queue>, #include <stack>, #include <unordered_map>
  • 각종 알고리즘 문제를 풀려면 사용해야하는 자료구조들입니다. priority_queue도 queue 라이브러리 안에 포함되어 있습니다.
• #include <climits>
  • INT 범위의 최소/최대값인 INT_MAX와 INT_MIN이 있습니다. 꽤 쓸 일이 많습니다. 물론 #define INF 1e9처럼 적당히 큰/작은 수를 사용하는 것이 더 유용할 때도 있지만요.
• #include <cstring>
  • int, char, bool 처럼 string 타입을 사용하고 싶을때 import 합니다.
• #include <tuple>
  • 2개의 원소쌍인 pair<X, Y> 타입은 따로 import 하지 않아도 기본적으로 사용할 수 있으나, 3개의 원소쌍인 tuple<X, Y, Z>는 tuple 라이브러리를 요구합니다. pair나 tuple을 이용하면, 조건문 속에서 크기 비교를 할 때 사전순으로 편히 쓸수 있어서 유용합니다. 상황에 따라 그냥 아래처럼 struct를 만들어 사용하는 것이 더 유용할 때도 있습니다.

struct Edge
{
    int u, v, w;
};

• #include<algorithm>
  • sort 함수를 제공합니다. 생각보다 쓸 일이 많지는 않았습니다.

 

기타

• 내 코드가 왜 틀렸는지 모르겠을 때에는 testcase.ac에서 반례를 찾을 수 있을지도 모릅니다. 유용하기는 하나, 코딩테스트 등의 실전에서는 쓸 수 없으니 너무 의존하지 않으려고 하고 있습니다.
• 저는 이렇게 해결 코드들을 모으고 있습니다. 어차피 해결한 문제라면 백준에서 확인할 수 있기는 하지만, 문제를 푸는것을 커밋으로 남기는 것이 또 다른 동기부여가 되기도 하고, 어차피 로컬에서 반복적으로 실행해야할 코드를 편히 돌려볼 수 있도록 하였습니다.
• 입출력 양이 매우 많고, 주어진 시간이 짧은 문제들은 입출력에서도 최적화가 필요합니다.
  
  • main 함수의 첫 두줄은 scanf와 printf 사용을 포기하는 대신, cin과 cout의 성능을 최적화합니다.
  • cout 에서 줄바꿈을 출력할 때, endl 대신 "\n"을 사용해야합니다.

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // ...
    
    cout << "..." << "\n"; // endl 사용금지
    
    return 0;
}