카카오 데이터 센터 화재로 티스토리 블로그가 접속이 안돼 백준 블로그를 이용합니다.

앳코더에서는 PS에서 자주 등장하는 동적 계획법 유형들을 26가지로 정리한 Educational DP Contest를 제공하고 있습니다.

이 블로그에서는 T번 문제인 Permutation의 풀이를 더 쉽게 이해할 수 있는 피드백을 제공합니다.

수열 $\{a_n\}$, $\{b_n\}$의 컨볼루션 $c_n = \sum_{i=0}^{n} a_i b_{n-i}$를 구하는 것은 FFT를 이용하여 $\mathcal{O}(n \log {n})$에 계산할 수 있습니다.

그런데 $\{a_n\}$, $\{b_n\}$의 각 원소가 online으로 주어진다면, 즉 예를 들어 $c_{n-1}$의 값을 알아야만 $a_n$과 $b_n$을 알 수 있다면 FFT를 이용하는 방법을 그대로 사용할 수 없습니다. 이러한 경우 $\{c_n\}$을 계산하는 문제를 Online FFT라고 부릅니다. Online FFT를 사용할 수 있는 대표적인 사례로 어떤 함수 $f$가 존재해 $a_n = f \left (n, \sum_{i=0}^{n-1} a_i b_{n-1-i} \right )$ 꼴의 점화식을 가지는 수열을 계산할 수 있습니다.

EDIT (2022-10-15): Online FFT의 정식 명칭은 relaxed multiplication인 것 같습니다.

어제 열렸던 AtCoder Beginner Contest 259 후기를 써 보려 합니다.

원래 이런 거 잘 쓰지 않는 성격이긴 한데 한 번 써 보고 싶어서 써 봅니다.

1. Introduction
2. Lazy Propagation이란?
3. Point Update Range Query의 비재귀 구현
4. Range Update Range Query의 비재귀 구현
5. Segment Tree 구현 코드
6. 사용 예시
7. Segment Tree with Lazy Propagation 구현 코드
8. 사용 예시

؜

priority_queue, set는 std::sort 등과는 다르게 함수 객체만 사용할 수 있습니다.

따라서 set<int,[](int x,int y)->bool{return x<y;}> s;와 같은 구문은 실행되지 않습니다. 혹은, 함수 cmp에 대해서 set<int,cmp> s;도 실행되지 않습니다.

이를 해결하기 위해서 일반적으로 새 구조체를 작성하는데, 그럴 경우에 다양한 정렬기준에 대해서 전부 구조체를 작성해야 하므로 번거롭습니다. 하지만 다음과 같이 구현하면 별다른 구조체 없이도 제대로 동작하게 됩니다.

백준 블로그는 처음이네요! 어떤 소재를 올리는 게 좋을지 모르겠어서 일단 제 다른 블로그에 올린 글에서 소재를 빼와서 쓰려고 합니다. C++에서는 쓸 수 없고 컴파일러도 맞아야 되기 때문에 유용할지는 모르겠네요.

보통 코드를 C로 짤 때는 아래와 같이 다차원 배열을 할당받습니다.

void version1(int h, int w) {
    int **array_2d = malloc(h * sizeof(int *));
    for(int i = 0; i < h; i++)
        array_2d[i] = malloc(w * sizeof(int *));

    // ...

    for(int i = 0; i < h; i++)
        free(array_2d[i]);
    free(array_2d);
}

이 글은 usaco.org의 정보를 바탕으로 작성되었습니다.

USACO(미국 정보올림피아드, USA Computing Olympiad)가 내일부터(17일~20일) 열립니다! 온라인으로 진행되는 대회로, 누구나 참여 가능하고, 무료입니다. 백준에서는 boj.kr/usaco 를 통해 풀어볼 수 있습니다. 다만 득점 정도를 확인할 수 없기 때문에 필요하다면 usaco.org를 사용하는 것도 좋을 것 같습니다.

첫 참가자들은 브론즈 등급으로 시작합니다. 승급 점수 컷을 넘으면 다음 등급으로 승급합니다. 등급은 Bronze > Silver > Gold > Platinum 입니다. 승급 이후에는 이전 등급의 대회를 다시 응시할 필요가 없습니다. 즉, 등급의 강등이 없습니다. 또한 해가 지나도 유지됩니다.

언어는 C/C++, Java, Python을 사용할 수 있습니다. 3~4개의 문제가 출제되고, 3~5시간동안 진행됩니다. 타임 프레임 형식으로, 대회 기간 동안 아무때나 원하는 시간에 참가하면 됩니다. 따라서 종료 후에 문제에 대해 발설하면 안됩니다. 대회에서 만점을 받으면 바로 다음 등급의 대회를 참가할 수 있습니다.

⚠️ 이 글은 더 이상 업데이트가 되지 않습니다. 하지만 댓글로 추가할 내용을 제안하시면 반영하겠습니다.

• 보통 대회 검수를 위한 슬랙이나 디스코드 서버를 만들게 될 텐데, 이때 문제별로 채널을 하나씩 만들어 주세요.
• 다음 검수 시트(링크)를 활용하면 좋습니다. (추가 예정)

• UCPC 디스크립션 작성 및 포매팅 컨벤션(링크)
• BOJ 스택 문제 안내(링크)
• 조금이라도 헷갈리는 게 있으면 곧바로 코멘트를 다세요. 절대로 대충 이해하고 그냥 넘어가면 안 됩니다. 그 헷갈리는 부분이 알고보니 실제로 문제가 있는 부분일 가능성이 높습니다. 중의적인 문장이거나, 빠진 조건이 있거나, 그냥 이상하게 썼거나...
• 변수의 대소문자 사용과 포맷팅(이탤릭, LaTeX, ...)이 통일되어 있나요?
• 지문에서 든 예시가 올바른가요?
• 문제(지문이나 입출력 조건)가 수정되면 반드시 통보되어야 하고, 검수도 반드시 다시 해야 합니다. 조건을 바꿨는데 밸리데이터를 안 바꾸는 바람에 데이터가 틀릴 수도 있고, 수정된 지문이나 조건이 이상해서 또 수정되어야 할 수도 있습니다.

여러분이 방금 틀렸습니다를 받았던 문제의 코너 케이스를 고쳤다고 해봅시다.

들뜬 마음에 점검도 안하고 바로 백준에 코드를 제출해버립니다!

void AddEdge(int v1, int v2)
{
    adjacencyList[v1].push_back(v2);
    adjacencyList[v2].push_back(v1);
    // 어라? 이거 지웠어야 하는데 그냥 제출해버렸네...
    printf("[DEBUG] Add edge (%d, %d)\n", v1, v2);
}

아... 근데 깜빡하고 디버깅하면서 출력했던 문자열을 안 지우고 제출해서 또 틀렸습니다를 받아버렸습니다...

깜빡하지 않았다고 하더라도, 디버깅용 문자열을 여기저기서 출력했다면 그걸 일일히 찾아서 지우는 것도 꽤 귀찮은 일입니다.

이분 탐색은 off-by-one error가 발생하기 쉬워서 늘 헷갈립니다.

이분 탐색 문제를 풀다보면 탈출 조건으로 lo <= hi, lo < hi, lo + 1 < hi 중 어느 걸 선택해야 할 지, 정답이 lo인지 hi인지 (lo + hi) / 2인지 모르겠고, 심지어는 while문이 끝나지 않아서 시간초과를 받기도 합니다.