September 18, 2019 19:00

세미나 운영에 대한 회고

알고리즘 동아리 운영에 있어 세미나를 어떻게 진행해야 할지는 정답이 없는 문제입니다. 너무 양이 많으면 기죽는 회원들이 생기지만 너무 적으면 세미나인지도 모호합니다. 난이도를 보아도 너무 어려우면 진입장벽이 생기고 너무 쉬우면 숙련자들에게 큰 의미가 없습니다. 종강이 다가올수록 줄어드는 관심 또한 문제이며, 방학 때는 정말 좋아하는 사람이 아니고서야 별도의 공부를 하지 않는 경우가 많습니다. 제가 회장으로 있는 알고리즘 동아리인 AlKor도 예외는 아니어서, 방학 때 별도의 세미나를 진행하지 않았습니다. 비록 일부 회원들이 ‘숭고한 알고리즘 캠프’에 참가하긴 하였으나, 세미나의 기준을 참가한 회원들에게 맞출 수도 없는 노릇입니다. 방학을 아무 세미나나 모의고사 없이 끝내기 싫어서 초급반 / 중급반 / 고급반 / 졸업반으로 나뉜 모의고사를 BOJ에서 2주간 진행하였습니다.

이 글은 기본적으로는 각각 15문제로 구성된 모의고사의 선정 방법, 의미 및 풀이를 서술하고자 합니다. 누군가에게는 풀고 싶었던 문제의 풀이가 적혀있을 수도 있고, 모의고사를 조직하는데 영감을 받을 수도 있으며, 재미로 이 동아리는 어떻게 하나 읽어볼 수도 있습니다. 어느 쪽이든 재미가 있었으면 좋겠습니다.

초/중/고급반 모의고사

분반은 기본적으로 3개(초급반, 중급반, 고급반)으로 나뉘어져있습니다. 각 분반의 실력을 콕 찝어말할 수는 없지만 대략 프로그래밍 기초 / 알고리즘 및 자료구조 기초 / ICPC 참가 정도의 수준입니다. 이 세 그룹에게 의미가 있어야 할 본 모의고사의 목적은 크게 다음과 같습니다.

• 1학기 세미나 내용 복습 가장 기본이 되어야 합니다.

• 세미나를 통해 배운 알고리즘 없이 문제 해결 대회나 온라인 저지에는 틀에 박히지 않은 문제들이 많습니다 (누군가에게는 이것도 ‘웰노운’으로 보일 수 있겠지만요). 알고리즘과 자료구조의 범주에서 벗어나 다양한 종류의 문제를 소개하고 싶었습니다.

• 예습하면 좋을 내용 제시 시간상의 이유로 1학기 때 가르치지 못했으나 이 정도는 알고 있으면 좋을 정도의 개념을 요구하는 연습문제를 알려주고 싶었습니다. 물론, 이런 문제들의 비중이 높으면 모르면 도저히 풀 수 없는 수준이 되기 때문에 유의해야 합니다.

• 도전적인 난이도의 문제 접근 몇몇 분들은 ‘킬러 문제’라고도 부르는 문제들이 있습니다. 이런 문제는 해당 모의고사를 많이 풀 것 같으면 의미가 있지만, 참가가 저조하면 0제출로 남는 경우도 많기 때문에 회원들의 동기 부여 상태를 고려하며 배분해야 합니다.

그 외로 고려한 점은 난이도순 정렬이었습니다. 이 때는 solved.ac의 도움을 많이 받았습니다. 그리고 일부 문제들을 분반별로 공유하여 이 정도 수준의 문제를 풀 수 있다 및 이 정도 문제들도 풀어볼만 하다는 점을 시사하고 싶었습니다. 단점도 있었는데, 상위 분반만 푼 회원들이 많아지면 스코어보드가 좀 난잡해졌습니다.

BOJ 17632 : 수학은 체육과목 입니다 2 (초급반 1번)

분류 : 조건문, 반복문

수의 규칙이 8을 주기로 가진다는 것을 알 수 있으므로, 8로 나눈 나머지에 따라 1, 2, 3, 4, 5, 4, 3, 2, 1을 출력하면 됩니다. 조건문이나 배열을 사용하면 해결할 수 있습니다. 시간 복잡도는 $O(1)$입니다 ($O(n)$으로 해결하여도 됩니다).

BOJ 3009 : 네 번째 점 (초급반 2번)

분류 : 조건문, 반복문

축에 평행한 직사각형을 만들어야 하므로 각 좌표값은 2가지 값만을 가질 수 있습니다. 점이 총 세 개이므로, 마지막 네 번째 점의 x좌표와 y좌표는 1번만 등장했을 것입니다. 그러므로 한 번만 나타난 x좌표와 y좌표의 값을 출력하면 됩니다. 좌표의 범위가 작으므로 등장 횟수를 세어도 되며 (시간 복잡도 $O(\max x_i + \max y_i)$, 조건문으로 해결할 수도 있습니다 (시간 복잡도 $O(1)$).

BOJ 1402 : 아무래도이문제는A번난이도인것같다 (초급반 3번)

분류 : 수학

$N = 1 \times N$이므로, $N$을 $N+1$로 변환할 수 있습니다. 또, $N = (-1) \times (-1) \times N$이므로, $N$을 $N-2$로 변환할 수 있습니다. 종합하면 $N$을 $N+1$ 또는 $N-1$로 변환할 수 있습니다. 그러므로 임의의 정수에서 임의의 정수로 변환할 수 있습니다. 답은 언제나 yes입니다. 시간 복잡도는 $O(T)$입니다.

BOJ 11332 : 시간초과 (초급반 4번)

분류 : 문자열

문자열로 시간 복잡도를 입력받은 다음 연산 횟수를 얼추 계산해야 하는 문제입니다. $N \leq 10^6$의 조건을 충실하게 지키면서 $2^N$이나 $N!$ 의 값을 계산할 수는 없다는 점에 유의해야 합니다 ($13!$은 62억 정도이며, $2^{30}$은 10억을 살짝 넘습니다). 계산값이 $L = 10$일 때도 최대 10억이므로, 계산하다가 10억을 넘어가면 더 이상 계산할 필요 없이 TLE!를 출력해야 합니다. 복잡도가 문자열 형태로 들어오기 때문에, 기초적인 파싱 또한 필요한 문제입니다.

BOJ 2346 : 풍선 터뜨리기 (초급반 5번)

분류 : 자료구조, 수학, 덱

‘구현’ 내지는 ‘시뮬레이션’ 문제입니다. 0번 풍선을 N번 풍선으로, N+1번 풍선을 1번 풍선으로 고려해주면서 1번 풍선부터 N번 풍선만 고려하도록 할 수 있고, 왼쪽 또는 오른쪽으로 움직인 다음에 풍선을 마크해주면 됩니다. 이러면 $O(N^2 \lg N)$¹의 시간 복잡도를 가지지만, 크기 1000 정도의 배열을 참조하는 것이기 때문에 충분히 시간 안에 돕니다. 실행 시간을 조금 줄이려면 다음과 같은 테크닉을 사용할 수 있습니다.

• % 연산자 대신 조건문으로 1번 / N번일 때만 예외처리 (나눗셈은 덧셈/뺄셈/곱셈에 비해 무거운 연산입니다)
• 남아있는 풍선의 개수보다 많이 이동해야 할 때, 나눗셈을 통해 여러 바퀴 도는 과정을 생략
• deque 자료구조 사용

BOJ 9095 : 1, 2, 3 더하기 (초급반 6번, 중급반 1번)

분류 : 동적 계획법

동적 계획법이 무언지 기억나시나요? 한 문제를 여러 개의 문제로 나누어 생각하는 것입니다. 이 문제의 경우 $f(n)$을 ‘‘정수 $n$을 1,2,3의 합으로 나타내는 방법의 수”라고 정의하면 다음과 같은 점화식을 세울 수 있습니다.

$ n = 1$일 때는 [1], $n=2$일 때는 [1,1], [2], $n=3$일 때는 [1,1,1], [2,1], [1,2], [3]으로 점화식의 기저 조건을 제공합니다. 마지막 점화식은 합이 $n$이 되게 하는 마지막 수가 1, 2, 3일 수밖에 없고, 각 경우가 중복될 수 없으므로 다음과 같이 나타납니다.

이런 문제는 점화식을 통해 이전 값을 참조해가면서 계산할 수도 있고, 점화식의 재귀적인 구조를 통해 재귀적으로 구할 수도 있습니다. 재귀적으로 구할 때, 각 상태(예를 들어 $f(5)$)를 계산한 후 저장해놓으면 이후에 $f(5)$가 필요할 때 다시 재귀적으로 계산하지 않고 바로 값을 반환할 수 있습니다. 이런 과정을 memoization이라고 합니다.

이 문제는 범위도 작고 점화식도 단순한 편이라 이러한 고찰이 필요없을 수도 있지만 다양한 방법을 알고 있는 건 중요합니다.

memoization이란 과정을 통해 각 상태의 값을 저장해놓아 상태의 중복 호출을 방지할 수 있습니다. 이점화식을 이용해 풀 수 있습니다. dp[1] = 1, dp[2] = 2, dp[3] = 4의 초깃값을 통해 dp[i] = dp[i-1] + dp[i-2] + dp[i-3]을 계속 구해나갈 수 있습니다.

BOJ 1783 : 병든 나이트 (초급반 7번)

분류 : 조건문

조금 까다로운 조건문 문제입니다. 우선 필요한 접근이 2개가 있는데, ‘나이트는 계속 오른쪽으로 움직인다’와 ‘체스판의 세로 길이가 3 이상인 경우는 3인 것처럼 가정해도 된다’입니다. 두 번째 가정의 경우, 올라가는 동작을 취했다면 다음에 내려오는 동작을 취할 수 있기 때문에 성립합니다. 이를 통해 세로 길이에 대한 분석을 해야 합니다.

• $ n = 1 $ 이면 움직일 수가 없습니다. 답은 $0$입니다.
• $ n = 2 $ 이면 위아래로 1칸씩만 움직이는 행동만 할 수 있습니다. 그러나 이동 횟수가 4번 이상일 때는 위아래로 2칸씩 움직이는 행동 또한 필요하므로 최대 3번까지만 할 수 있습니다. 답은 $\min(\frac{m-1}{2}, 3)$입니다.
• $n \geq 3$ 이면 가로 길이가 충분하다는 전제하에 모든 행동을 전부 할 수 있습니다.
  • 모든 행동을 할 수 있는 최소의 가로 길이는 $ m = 7$입니다. 이 때는 위아래로 1칸씩 움직이는 행동을 1번씩 하고 그 이후로는 위아래도 2칸씩 움직여야 최대한 많이 움직일 수 있으므로, 답이 $m - 3$이 됩니다.
  • 그 외의 경우면 $n = 2$일 때와 비슷하게 답이 최대 3입니다. 최대 3번이므로 위아래로 2칸, 오른쪽으로 1칸씩 움직이면 됩니다. 그러므로 답이 $\min(m-1, 3)$이 됩니다.

케이스 분석은 쉬운 문제에서도, 어려운 문제에서도 늘 나옵니다. 꼼꼼하게 모든 경우를 고려하는 좋은 습관을 기르셔야 난맞왜틀로부터 해방될 수 있습니다. 그러한 연습을 하라고 넣은 문제입니다.

BOJ 16112 : 5차 전직 (초급반 8번, 중급반 2번)

분류 : 정렬, (기초) 수학

정렬을 쓰라고 넣은 문제지만, 아주 중요한 수학적 정리 하나를 알아야 하는 문제입니다. 문제를 해석하면 첫 번째로 해결한 퀘스트에 대한 경험치는 받을 수 없고, 두 번째로 해결한 퀘스트의 경험치는 그대로, 세 번째 퀘스트는 2배의 경험치를 받을 수 있으며, …, $k+1$번째 퀘스트부터는 $k$배의 경험치를 받을 수 있습니다.

수학적으로 이 문제를 표현해보자면 음이 아닌 정수로 이루어진 길이가 같은 두 수열 ${a_i} = {\min(0, k), \min(1, k), \min(2, k), \cdots, \min(n-1, k)}$과 ${b_i} = {b_1, b_2, b_3, \cdots, b_k, \cdots, b_{n-1}, b_n}$가 주어질 때 ${b_i}$를 어떻게 배열해야 $\sum_i a_ib_i$가 최대가 되는지입니다. 어쩌면 이 문제를 보고 큰건 큰것끼리 곱하면 되지 않을까라는 그리디 알고리즘을 생각하셨을 수도 있겠습니다. 맞습니다. 정렬해서 작은 건 작은 것끼리, 큰 건 큰 것끼리 곱해주어야 최대가 나옵니다.

이를 서술하는 부등식이 재배열 부등식(Rearrangement Inequality)입니다. 재배열 부등식은, $x_1 \leq \cdots \leq x_n$이고 $y_1 \leq \cdots \leq y_n$을 만족하는 임의의 실수 $x_1, \cdots, x_n, y_1, \cdots, y_n$에 대해

이 성립한다는 부등식입니다. 이 때 ${\sigma(1), \cdots, \sigma(n)}$은 ${1,\cdots,n}$의 임의의 순열입니다.

그러므로 이 문제는 경험치를 오름차순으로 정렬하고, $i$번째 경험치부터 $\min(i-1, k)$를 곱한 다음 전부 합하면 됩니다.

이 부등식은 정규 교육과정에는 없는 것으로 알고 있지만 PS나 IMO 등의 분야에서는 근본적이면서도 강력합니다. PS를 한다면 반드시 알아두어야 할 부등식입니다.

BOJ 1699 : 제곱수의 합 (초급반 9번)

분류 : 동적 계획법, 탐색

기초적인 동적 계획법 / BFS 문제입니다. 두 풀이의 방향이 비슷하지만 DP로 풀자면 각 수가 최소 몇 개의 제곱수를 필요로 하는지는 정해져있으므로 해당 값에 대해 동적 계획법을 적용하여, 그 수 이하의 제곱수를 뺀 수에 대해 조사하면 됩니다. 비슷한 방향으로 BFS를 돌릴 수도 있습니다. $n$ 이하 제곱수는 대략 $ \sqrt{n}$개 있으므로 시간 복잡도는 대략 $O(n^{1.5})$이 됩니다.

여담으로, 임의의 자연수는 4개의 정수의 제곱의 합으로 표현할 수 있습니다(Lagrange’s four-square theorem). 즉 이 문제의 임의의 입력에 대해 답은 4를 넘지 않습니다.

BOJ 10166 : 관중석 (중급반 3번)

분류 : 수학

최대공약수를 이용해야 하는 문제입니다. 이 문제에선 $ 1 \leq i \leq n$이고 $ 0 \leq j < i$를 만족하는 순서쌍 $(i, j)$ 중 $\gcd(i, j) = 1$을 만족하는 쌍의 개수를 구해야 합니다 ($\gcd$는 최대공약수를 의미합니다). 그럼 최대공약수를 어떻게 구해야 할까요? 역시 정규 교육과정에는 나오지 않지만 기초정수론의 단골인 유클리드 호제법(Euclidean algorithm)이 널리 알려져 있습니다. 유클리드 호제법은 다음과 같습니다.

def euclidean(a, b): # a, b >= 0, a + b != 0
	while b > 0:
        a, b = b, a % b
    return a + b

이러한 알고리즘이 성립하는 이유는 $a$를 $b$로 나눈 나머지를 $r$이라 할 때, $\gcd(a, b) = \gcd(b, r)$이기 때문입니다 (증명은 기초적인 정수론을 요구합니다). 나누는 수가 0이 될 때까지 이 과정을 반복하고, 나누는 횟수는 두 수 중 작은 수의 십진법 표기의 길이의 5배를 넘지 않습니다 (log scale입니다). 위 알고리즘은 양의 정수 $x$에 대해 $\gcd(x, 0) = x$이기 때문에 입력에 0이 들어오는 경우까지 깔끔하게 처리되는 것을 알 수 있습니다. 이를 구현하면 복잡도 $O(n^2 \lg n)$에 문제를 해결할 수 있습니다.

BOJ 1620 : 나는야 포켓몬 마스터 이다솜 (초급반 10번, 중급반 4번, 고급반 1번)

분류 : 해시맵(자료구조)

지문이 좀 필요없이 길긴 한데, 문제의 핵심만 집자면 숫자와 문자열 간의 일대일 대응을 구현해야 합니다. 이런 문제를 해결하는 대표적인 자료구조가 해시맵(hashmap)입니다. C++의 경우, std::map이, Python의 경우 dict, Java의 경우 HashMap에 구현되어 있습니다. 사용법도 간단합니다.

#include <iostream> // std::cout
#include <cstdio>   // printf
#include <map>      // std::map
#include <string>   // std::string
// std::max<key_type, value_type> identifier;
std::map<int, std::string> m1;
std::map<std::string, int> m2;
int main()
{
    m1[25] = "Pikachu";
    printf("%s\n", m1[25].c_str());      // Pikachu

    m1[-1] = "Missingno";
    std::cout << m1[-1] << '\n';         // Missingno
    
    m2["Gyarados"] = 130;
    std::cout << m2["Gyarados"] << '\n'; // 130
}

해당 코드에 나와있진 않지만 C++의 std::map은 데이터를 정렬하여 저장합니다. 때문에 이분 탐색 등을 진행할 수 있습니다. $n$개의 원소가 들어가 있는 std::map의 원소 참조의 시간복잡도는 $O(\lg n)$이지만 해시 함수 등을 사용하기 때문에 다른 $ O(\lg n)$ 복잡도 컨테이너 및 함수 (예시 : std::priority_queue, std::set, std::vector에 사용하는 std::lower_bound) 에 비해 상당히 느립니다. 적재적소에 쓰되 남용하지는 맙시다.

BOJ 1027 : 고층 건물 (초급반 11번, 중급반 5번)

분류 : 기하, 그리디

약간의 기하와 그리디를 접목하여 풀 수 있습니다. 구현 방식은 다양할 수 있지만 직관적인 방법 하나를 소개하고자 합니다.

• 기본적으로 자신보다 오른쪽에 있는 건물만 고려합니다. $i$번째 건물을 현재 보고 있다고 합시다.
• 자신보다 오른쪽에 있는 건물들을 순차적으로($i+1, i+2, \cdots, n$) 순회하며, (현재 건물 - 오른쪽에 있는 건물)의 기울기의 최댓값을 구해나갑니다. 만약 지금 보고 있는 건물과의 기울기가 최대 기울기를 갱신한다면, 이 건물을 볼 수 있습니다.
  • 이 때, 두 건물은 서로 볼 수 있으므로 각자 개수에 +1을 해줍니다.
• 이 과정을 모든 건물에 대해 반복합니다.

기울기 비교는 분수로 진행하는 게 제일 바람직하지만, double형 변수를 사용해도 통과가 됩니다. 여담이지만, 실수형에서 == 연산을 직접 수행하면 안 된다는 점을 명심하세요. 실수 오차는 필연적으로 생깁니다. https://0.30000000000000004.com/ 를 보세요.

BOJ 4256 : 트리 (초급반 12번, 중급반 6번)

분류 : 트리, 탐색

전위/중위/후위탐색에 대한 개념과, 분할 정복 사용을 묻는 문제입니다.

전위 탐색에서 첫 번째 수는 현재 트리의 루트입니다. 이 정점은 당연히 중위 탐색에서도 나타납니다. 그럼 중위 탐색 기준으로, 왼쪽은 왼쪽 자식에 있는 정점일 것이고, 오른쪽은 오른쪽 자식에 있는 정점일 것입니다. 같은 트리에서 탐색하는 것이기 때문에 왼쪽 자식 / 오른쪽 자식의 크기가 일정하므로, 구간을 나누어 분할정복으로 진행할 수 있습니다.

시간 복잡도는 테스트 케이스 당 $O(n^2)$입니다. 각 정점이 중위 순회에 몇 번째로 나타나는지를 인덱싱을 통해 미리 저장해 놓는다면 $O(n)$에도 할 수 있습니다.

BOJ 15897 : 잘못 구현한 에라토스테네스의 체 (초급반 13번, 중급반 7번)

분류 : 수학

수학 문제입니다. 요약하자면 $\sum_{k=1}^n \lfloor\frac{n}{k}\rfloor$을 구하는 것입니다. 시간복잡도 $O(n)$에 구할 수 있겠지만, $ n \leq 10^9$로 다 구하는 방법으로는 구할 수 없습니다. 효율적인 풀이를 위해서는 자연수 $x$에 대해 $\lfloor\frac{n}{x}\rfloor$를 생각해보는 것이 좋습니다. 1*1 격자를 채운다고 생각하면, $ y = x $ 기준으로 대칭임을 알 수 있습니다.

단도직입적으로 들어가봅시다. $ r = \lfloor\sqrt{n}\rfloor$이라고 하면, 답은 $2\cdot \sum_{k=1}^r \lfloor\frac{n}{k}\rfloor - r^2$가 됩니다. 1부터 $r$까지 해당 값을 구한 다음에 대칭시켜 반대쪽에 넣으면 모든 칸이 다 한 번씩 채워지고, $r^2$개의 칸만 두 번 채워지기 때문입니다. 그러므로 시간복잡도 $O(\sqrt{n})$에 문제를 해결할 수 있습니다.

BOJ 2437 : 저울 (초급반 14번, 중급반 8번)

분류 : 그리디

얼핏 보면 이 문제는 NP-complete로 알려진 subset sum 문제와 비슷해보이지만 다릅니다. 하지만 약간의 그리디를 접목해 해결할 수 있습니다. 현재까지 만들 수 있는 무게가 연속되어야 한다는 성질에 집중합시다.

우선 정렬을 하여 가장 작은 추부터 고려해보도록 하겠습니다. 현재까지 무게가 $0$ 이상 $x$ 이하의 정수 무게 추들을 전부 잴 수 있다고 생각해봅시다. 초기 상태에서는 $x = 0$입니다. 직관적으로, 첫 추의 무게가 $2$ 이상이면 무게 1을 잴 수 없습니다. 이를 조금 일반화해서 생각하면, $x$까지 잴 수 있는 상태에서 다음 추의 무게가 $x+2$ 이상이면 표현할 수 없는 무게가 존재합니다. 예를 들어 3까지 잴 수 있는 상황에서 5가 들어오면 만들 수 있는 무게는 0, 1, 2, 3, 5, 6, 7, 8로, 중간에 4가 빠지게 됩니다. 여기서 추의 무게가 6으로 들면 5도 표현할 수 없게 됩니다. 만약 $x$나 $x+1$이 다음 추의 무게라면, $x$에 그 값을 더해주면 됩니다.

이러한 성질을 고려하면, 정렬 후 반복문을 통해 $x+1 < a_i$이면 바로 반복문을 벗어나며, 아니면 $x := x + a_i$를 하면 됩니다. 정답은 정의에 따라 $x+1$이 됩니다.

BOJ 12869 : 뮤탈리스크 (초급반 15번)

분류 : 탐색

완전탐색으로 풀릴지는 잘 모르겠습니다. 하지만 완전탐색을 조금 응용하면 BFS로 풀 수 있습니다. 각 뮤탈리스크의 체력 $(x_1, x_2, x_3)$을 정점으로 생각합시다. 입력으로 들어오지 않은 뮤탈리스크에 대한 체력은 0으로 가정해도 무방합니다. 이 정점에서 공격 방식에 따라 최대 6개의 정점으로 이동할 수 있으며, 모든 $x$값이 감소하게 됩니다. 그래프에서 루프가 없음이 자명하고 상태가 $61^3 = 226981$개 밖에 있지 않으므로, BFS나 DP를 통해 문제를 해결할 수 있습니다.

BOJ 1022 : 소용돌이 예쁘게 출력하기 (중급반 9번)

분류 : 구현

구현 문제입니다. 문제는 크게 2개의 부분으로 구성되어 있습니다.

• 각 칸의 수 구하기
• 공백으로 패딩하기

각 칸의 수를 구하는 과정 또한 접근법이 2개가 있습니다.

• 시뮬레이션으로 직접 구하기. 제일 큰 수는 $(5000, 5000)$에 있는 수로 100020001입니다. 소용돌이의 방향에 따라 칸을 이동하고, 조사하고자 하는 칸이면 값을 저장해나가면 됩니다.
• 각 칸의 값을 $O(1)$에 구하는 방법이 있습니다. 구조를 잘 생각해보면 $[1,1]$, $[2,9]$, $[10,25]$, $[26, 49]$ 의 꼴로 연속된 수들이 한 정사각형에 위치해 있으며, 수가 커질수록 더 큰 정사각형에 속한다는 것을 알 수 있습니다. 어떤 수가 몇 번째 정사각형에 속하는지는 $\max(\lvert x \rvert, \lvert y \rvert)$로 알 수 있으며, 이제 어느 쪽 변에 있느냐를 조건문으로 따져서 수를 구할 수 있습니다.

출력도 문제입니다. 가장 큰 수의 길이를 구해서 각 수를 그 기준에 맞춰야 하는 건 알겠는데, 어떻게 해야 할까요?

• 각 수를 십진법으로 표현했을 때의 길이는 나누어보며 구할 수 있습니다. 남는 길이만큼 공백을 출력하면 됩니다.
• printf("%*n", a[i][j], len);은 a[i][j]를 길이 len에 맞추어 우측 정렬을 해줍니다. 남는 공간은 space로 채워줍니다. format string 안에 있는 *값에 len이 들어갑니다.
• #include <iomanip>을 한 후, std::cout << std::setw(len) << a[i][j];을 하면 위와 같은 기능을 수행합니다.

BOJ 17398 : 통신망 분할 (중급반 10번, 고급반 3번)

분류 : 서로소 집합

학기 중에 강의했던 서로소 집합(Disjoint-set)을 이용하는 문제입니다. 그래프를 분리하는 과정을 일반적으로 병합하는 과정보다 훨씬 어렵기 때문에, 문제를 역순으로 접근해볼 수 있습니다.그럼 각 쿼리에 따라 간선을 연결할 때, 분리되어 있던 두 컴포넌트를 연결하면 크기의 곱을 출력하면 됩니다. 이는 서로소 집합으로 해결할 수 있습니다.

BOJ 1701 : cubeditor (중급반 11번, 고급반 2번)

분류 : 문자열 (KMP, SA)

예습 문제로, KMP 알고리즘 또는 SA(접미사 배열)을 사용해야 합니다. 두 가지 접근법을 모두 설명하도록 하겠습니다.

• KMP로 접근하기: 정답이 되는 길이 $x$짜리 문자열 중 한 번은 $i$번째에서 시작하고, 한 번은 $j$번째에서 끝난다고 가정합시다 ($j > i + x$). 그럼 원본 문자열이 $S$라고 할 때 $S[i:]$($i$번째 문자부터 시작하는 $S$의 부분문자열)에 대해서 KMP를 사용하면 fail의 값이 $x$가 되는 지점이 존재합니다. 그러므로 $S$의 모든 접미사에 대해 fail 배열을 계산하고, 각 경우의 최댓값의 최대를 취하면 답이 됩니다. 시간복잡도는 $O(|S|^2)$입니다. KMP 알고리즘에 대한 설명은 koosaga님의 글을 읽어보시길 바랍니다.
• SA로 접근하기: 모든 부분문자열은 어느 접미사의 접두사입니다. 그러므로 접미사들을 정렬하고(이를 구하는 것이 SA, 즉 접미사 배열입니다), 인접한 접미사들이 얼마나 공통된 문자열을 가지고 있는지를(LCP, longest common prefix) 구하면 정답이 됩니다. 일반적으로 PS에서 SA는 $O(N \lg N)$에, LCP는 SA 구축 후 $O(N)$에 구합니다(plzrun님의 설명 블로그). 이 문제에서는 직접 정렬을 통해 $O(N^2 \lg N)$ 에 SA를 만들고, LCP를 매번 비교하는 $O(N^2)$에 구해도 시간 내에 통과될 수 있을 것 같습니다.

아직 중급반이 KMP를 배우지는 않았지만, 구현 난이도가 간단한 편이고 알아두면 유용하기에 넣었습니다.

BOJ 17396 : 백도어 (중급반 12번)

분류 : 다익스트라 알고리즘

예습 문제로, 다익스트라 알고리즘을 이용해야 합니다. (jason9319님의 설명 블로그) 간선이나 정점을 무시해야 하는 파트도 있긴 하지만, 이 문제의 가장 어려운 파트는 (시간복잡도나 로직 상으로) 올바른 다익스트라 알고리즘을 구현하는 것입니다. 혹시 본인이 구현하는 다익스트라 알고리즘이 여기에 해당하지는 않는지, djm03178님의 포스팅를 보시면서 확인해보시기 바랍니다.

다익스트라 알고리즘은 정말 널리 쓰이는 알고리즘입니다. 아직 중급반에서 가르치지는 않았지만 그만큼 중요하기에 모의고사에 추가하였습니다.

별개로 이 문제에서 SPFA는 저격하지 않았습니다.

BOJ 1033 : 칵테일 (중급반 13번)

분류 : 수학, 그래프

분수꼴로 저장해야 하는 문제입니다다. 한 재료의 질량을 1로 고정하고 DFS 등을 통해 나머지 재료의 상대적인 질량을 계산할 수 있습니다. 이후 분모를 전부 곱해주고 분자들의 최대공약수만큼 나누어주면 됩니다. 정답이 부호 있는 32비트 정수형의 범위를 넘어갈 수 있다는 점도 고려해야 합니다.

BOJ 12767 : Ceiling Function (중급반 14번)

분류 : 트리, 구현, 재귀

무려 ICPC World Finals 문제입니다 (해당 대회에서는 가장 쉬운 문제였습니다). 문제를 해결하는 다양한 방법이 있지만, 가장 직관적이고 상대적으로 간단한 방법은 직접 Binary Search Tree를 구현하여 트리의 구조가 같은지 재귀적으로 확인하는 것입니다.

BOJ 10548 : BOB (고급반 4번)

분류 : 스택

$n \times 1$일 때를 생각해봅시다. 이 경우에는 현재까지 몇 개의 수가 동일하게 나왔는지를 계속 세면서 더해주다가 다른 수가 나오면 초기화를 하면 됩니다. 한 줄을 더 추가해도 이렇게 할 수 있을까요?

한 줄일 때 답을 구하는 과정은, $(x, 1)$가 우하단인 직사각형의 개수를 $1 \leq x \leq n$일 때 순차적으로 세나가는 과정과 동일합니다. 여러 줄로 확장하는 과정에서 스택의 개념이 추가됩니다. 이전 줄에도 동일한 수가 있었는지 봐야 하기 때문입니다.

$len[x]$는 지금 보고 있는 $y$번째 열에서 $x$번째 행에 $a[x][y]$와 같은 수가 오른쪽부터 몇 개 연속해서 있는지입니다. 이 값은 $(x, y)$ 칸을 볼 때마다 $a[x-1][y] $과 $a[x][y]$가 같으면 1이 더해지며, 다르면 1로 초기화됩니다. 별도로, 이전에 같은 수들이 있는 길이를 저장하는 스택이 필요합니다. 때문에 이 스택은 현재 보고 있는 칸을 우하단 꼭짓점으로 하는 직사각형의 개수를 들고 있습니다. 그렇기에 이 스택은 top에 가장 큰 수가 들어가야 합니다. 만약 새로 추가할 수가 top보다 작다면, top에 해당하는 열의 몇몇 칸들은 후보가 되지 못합니다. 때문에 그 차이만큼 빼주어야 하고 스택에서도 빼야 합니다. 아예 다른 수가 들어오면 스택을 초기화해야 합니다.

BOJ 16287 : Parcel (중급반 15번, 고급반 5번)

분류 : 동적 계획법

복잡도를 두 번 줄여야 하는 동적 계획법 문제입니다. 풀이는 koosaga님의 블로그의 F번 파트에 간결하게 설명되어 있습니다. 기본적으로는 Meet-in-the-middle의 방식으로, 처음 2개와 마지막 2개를 따로 고려하는 방법입니다. 전 이 문제를 대회 때 이상한 방법으로 풀었는데 시간초과가 나지 않고 통과했던 기억이 납니다.

BOJ 1413 : 박스 안의 열쇠 (고급반 6번)

분류 : 조합론

어떤 상자부터 폭탄을 사용해 여는지는 중요하지 않기 때문에, 임의로 선택된 상자가 크기 몇의 사이클에 속해있는지를 전부 고려해야 합니다.

$g(x, y)$를 $x$개의 원소들이 $y$개의 사이클로 이루어져있는 경우의 수라고 할 때, $g(x, y) = \sum_{i=1}^{x} (i-1)! \dbinom{x-1}{i-1} g(x-i, y-1)$로 쓸 수 있습니다. 사이클의 크기가 $i$라고 하면, $x-1$개의 원소 중 $i-1$개의 순열을 고려하는 것이 첫 두 항입니다. 초기값은 $t \neq 0$일 때 $g(t, 0) = g(0, t) = 0 $, $g(0,0) = 1$입니다. 그럼 답은 $\frac{1}{n!}\sum_{i=1}^{k} g(n, i)$이 됩니다.

$g(x, y)$는 제 1종 스털링 수라고도 불립니다.

BOJ 15898 : 피아의 아틀리에 -신비한 대회의 연금술사- (고급반 7번)

분류 : 구현

구현 문제입니다. 정해도 9중 루프입니다. 뭐라 설명하기가 어렵네요. 어떻게 구현해야할지 디자인하는 것도 중요합니다 (예시 : 완전탐색을 어떻게 구현할 것인지, 배열 회전은 어떻게 할 것인지).

BOJ 15267 : Justified Jungle (고급반 8번)

분류 : 수학, DFS

한 간선을 제거하면 나뉘는 두 컴포넌트의 크기에 집중합시다. 정점의 개수가 $n$개 있는 트리를 정점이 $k$개로만 이루어져있는 서로 다른 컴포넌트들로 나눌 수 있다고 가정해봅시다. 그럼 이 때 잘리는 간선들이 존재할 것이고, 이들은 컴포넌트의 크기가 $k$의 배수가 되게 분할할 것입니다. 이렇게 분할이 되어 나오는 컴포넌트들은 총 $2(n/k-1)$ 개 존재할 것입니다.

약간의 관찰을 통해 문제에서 요구하는 조건과 이 조건이 서로 필요충분조건이라는 것을 보일 수 있습니다. 때문에 DFS 등을 통해 간선 분할 시 생성되는 컴포넌트의 개수를 센 후, $n$의 약수에 대해 세면서 테스트하면 됩니다. 이러면 총 시간복잡도 $O(n \lg n)$에 문제를 해결할 수 있습니다.

BOJ 2647 : 검은점과 하얀점 연결 (고급반 9번)

분류 : 동적 계획법

매칭이 되는 구간의 길이는 짝수일 수밖에 없고, 같은 구간에서 높이가 더 높으면서 길이가 더 짧을 수는 없습니다. 때문에 각 구간의 최적해 및 그 때의 높이와 구간의 맨 왼쪽 점과 매칭된 점을 저장하면서 갱신을 해나갈 수 있습니다. 또 이미 매칭된 점은 사용되지 않기 때문에 구간을 더 작은 구간 2개로 나눌 수 있습니다.

BOJ 10782 : Hacker (고급반 10번)

분류 : 자료구조, 그리디

$n$개의 컴퓨터가 있고 처음에 $i$번째 컴퓨터를 해킹한다고 합시다. 해킹할 수 있는 컴퓨터는 연속된 $\lceil\frac{n}{2}\rceil$개의 컴퓨터이며, 범위는 $[i-\lceil\frac{n}{2}\rceil+1, i]$부터 $[i, i+\lceil\frac{n}{2}\rceil-1]$ 이 됩니다. 이 때 상대편은, 이 구간 중 최소의 자료를 가지고 있는 구간을 가져가게 행동할 수 있습니다. 즉, 해당 구간 중 최솟값을 가져가게 됩니다. 이 값들의 최댓값이 정답이 됩니다.

그러므로 구간합을 미리 계산해놓은 다음, BST 등의 자료구조에 해당하는 $\lceil\frac{n}{2}\rceil$개의 구간을 넣어둔 다음, 삽입 및 삭제를 해가면서 최소값의 최댓값을 구하면 됩니다. 시간 복잡도는 $O(n \lg n)$입니다.

BOJ 2912 : 백설공주와 난쟁이 (고급반 11번)

분류 : 세그먼트 트리

특이한 값을 저장해야 하는 세그먼트 트리 문제입니다. 우선 어떤 구간을 잡았을 때, 절반이 넘는 모자의 색상은 0개 또는 1개입니다. 여기에서 재밌는 성질을 하나 간파할 수 있습니다. 어떤 구간에 절반이 넘는 모자의 색상이 있다고 가정합시다. 그럼 그 구간을 나누는 임의의 분할을 생각했을 때, 최소한 한 구간에는 해당 색상이 절반이 넘게 있습니다 (그렇지 않다면 모순이 됨을 알 수 있습니다). 그렇기 때문에, 세그먼트 트리로 구간을 관리하며 ‘절반이 넘는 모자의 색상’을 관리하면 됩니다. 만약 그런 모자가 없으면 0을 넣으면 됩니다.

구간의 길이가 1일 때는 모자의 색상은 입력 그대로입니다. 그보다 클 때는 자식 노드에 있는 모자 색상들만 고려하면 됩니다. 앞서 말한 성질에 의해, 두 자식 노드에서 과반을 차지하지 못했는데 전체에서 과반을 차지할 수 없기 때문입니다. 한 구간에 특정 색깔의 모자가 몇 개 있는지는 따로 배열을 만들어서 lower bound 등을 통해 계산할 수 있습니다.

전처리는 이렇게 $O(n \lg n)$에 할 수 있습니다. 쿼리가 들어오면 각 구간에 해당하는 세그먼트 트리들 구간들이 담고 있는 모자 색에 대해 조사해보면 됩니다. 왜냐하면 분할을 했을 때 한 구간에서라도 절반이 넘는 모자의 색상만이 후보가 될 수 있기 때문입니다. 임의의 구간은 세그먼트 트리의 $O(\lg n)$개의 노드에 대응되며, 쿼리로 주어진 구간에 해당 모자 색상의 개수를 구하는 작업은 역시 lower bound를 이용하여 $O(\lg n)$에 해결할 수 있습니다. 그러므로 쿼리당 시간복잡도 $O(\lg^2 n)$에 문제를 해결할 수 있습니다.

BOJ 3350 : Candy Machine (고급반 12번)

분류 : 그리디

좌표변환 $(x, y) \mapsto (x+y, y-x)$을 하면 시계방향으로 45도 돌아갑니다. 이렇게 생각하면, 모든 경로는 $x$와 $y$가 감소하지 않는 방향으로 갑니다. 이런 문제에 대한 이론적인 서술을 하는 정리가 Dilworth’s Theorem이며, 알고리즘은 다음과 같습니다.

• 각 경로들을 담고 있는 집합 $S$와, 점들이 $x$값에 대해 오름차순으로 정렬되어 있는 ($x$좌표가 같을 경우 $y$좌표로 오름차순) 집합 $P$를 생각합시다.
  • 여기서 경로란, 인접한 두 점의 $x$좌표와 $y$좌표가 감소하지 않는 점들의 순열입니다.
• $P$의 각 점 $p_{i}$에 대해
  • $S$에 있는 어느 경로에도 이어붙일 수 없으면 $p_{i}$를 $S$에 넣습니다.
  • $S$에 있는 경로에도 이어붙일 수 있으면, 그 중 $y$좌표가 가장 큰 경로에 이어붙입니다.

BST나 priority queue 등의 자료구조를 사용하면 해당 문제를 $O(n \lg n)$에 해결할 수 있습니다.

BOJ 16685 : XOR 포커 (고급반 13번)

분류 : 선형대수

XOR Maximization은 가우스 소거법을 통해 그리디하게 할 수 있음이 널리 알려져 있습니다(koosaga님의 블로그). 하지만 여기서는 수를 짝수개 골라야 한다는 조건이 추가되어 있습니다. 놀랍게도, 수열 $(a_1, a_2, \cdots, a_n)$을 $(b_1, b_2 , \cdots, b_n) = (a_1 \oplus a_1, a_1 \oplus a_2, \cdots, a_1 \oplus a_n)$으로 바꾼 다음, XOR Maximization을 하면 답이 나옵니다. 이 이유는 다음과 같습니다.

• 정답이 $a_1$을 포함할 경우 : $(a_{i_1}, a_{i_2}, \cdots, a_{i_{2k}})$이 최대이고, $i_1 = 1$일 때, $ \begin{align} \ &a_{i_1} \oplus a_{i_2} \oplus \cdots \oplus a_{i_{2k}}
  =\ & (a_{i_1} \oplus a_{i_1}) \oplus (a_{i_2} \oplus a_{i_1}) \oplus \cdots \oplus (a_{i_{2k}} \oplus a_{i_1})
  =\ & b_{i_1} \oplus b_{i_2} \oplus \cdots \oplus b_{i_{2k}} \end{align} $ 이 성립하기에 답이 나옵니다.

• 정답이 $a_1$을 포함하지 않는 경우에도 비슷하게 정답이 됩니다.

변환한 수열에서 수를 선택하는 것은 기존 수열에서 수를 선택하는 것과 대응이 되기 때문에 변환된 수열에서의 정답이 기존 수열에서의 정답이 됨을 알 수 있습니다.

BOJ 11014 : 컨닝 2 (고급반 14번)

분류 : 이분 매칭

자리 $(x, y)$를 선택하면($(1,1)$이 좌상단, $(n, m)$이 우하단) 다음 여섯 자리를 선택할 수 없습니다.

• $(x-1, y-1)$, $(x, y-1)$, $(x+1, y-1)$, $(x-1, y+1)$, $(x, y+1)$, $(x+1, y+1)$

이미 점유된 좌석은 고려하지 않고 남은 좌석끼리만 서로 선택되면 안 되는 쌍을 간선으로 연결하면, 이 문제는 그래프에서 최대 독립 집합의 크기를 구하는 문제로 바뀝니다. 게다가 현재 생성된 그래프는 (열 번호의 홀짝성으로 구분되는) 이분그래프입니다.

Kőnig’s theorem에 따라 이분 그래프에서 최소 정점 덮개의 크기와 최대 매칭의 크기는 같으며, 임의의 그래프에서 최소 정점 덮개의 크기와 최대 독립 집합의 크기는 정점의 개수와 같습니다. 그러므로 이분 그래프에서의 최대 매칭을 구하면 정답을 바로 구할 수 있으며, 이분 매칭을 시간 복잡도 $O(VE)$에 구현하는 것은 널리 알려져 있으며, Dinic’s Algorithm을 쓰면 시간 복잡도 $O(\sqrt{V}E)$에 돌아갑니다 (Hopcroft-Karp Algorithm).

BOJ 16737 : Python Classes (고급반 15번)

분류 : 파싱, 동적 계획법

파싱을 통해 클래스의 상속관계를 의미하는 그래프를 만들 수 있습니다. 사이클이 있을 경우 정의가 불가능하므로 -1을 처리한다고 하면 포레스트가 생성됩니다.

각 클래스 선언문이 $i$번째로 나타난다고 할 때, 이 클래스의 정의가 필요한 클래스는 이보다 밑에 있거나 위에 있습니다. 밑에 있으면 그 상태와 $i$번째로 끌어올린 상태를 고려하면 되며, 위에 있으면 해당 클래스를 어차피 $i$번째 밑으로 끌어내려야 하므로 $i$번째에 놓았다고 가정하고 조사하면 됩니다.

결론

다행히 적지 않은 분들이 풀어주셔서 이 모의고사가 묻히는 일은 일어나지 않았습니다. 다만 HLD, PST 등의 고급 알고리즘 및 자료구조 문제 위주로 구성했던 졸업반 대회는 완전히 잊혀져서 아쉽긴 했습니다. 보통 2학기가 들어서며 동아리 참가 인원이 급격하게 감소하는데 이번 년도에는 덜 그러기를 바랍니다. 난이도는 몇몇 문제의 위치 빼고는 괜찮았다고 생각하는데, 다른 분들이 보기에는 어떨지 잘 모르겠습니다.

학기 중에 이렇게 큰 규모로 2주간 모의고사를 여는 일은 별로 없을 거고, 이 정도로 방대한 서술을 해가며 풀이를 쓸 것 같지도 않습니다. PS에 발을 막 담그고 있는 사람들에게 좋은 지침이 되었으면 합니다. Happy coding!