• 운영진: leejseo, ryute, jhnah917, Lawali, ahgus89, ckw1140, cheetose, ho94949, rdd6584, gs11008, junseo, wookje, junie
• 모든 출제자 및 검수자, 대회 플랫폼을 지원해주신 스타트링크, 그리고 대회에 참가하고 지금 에디토리얼을 읽고 있는 당신께 감사의 말씀을 전합니다.

solved.ac 티어 v. 코드포스 레이팅에 대한 통계를 작성해봤습니다. 표본 n = 624이고, R² = 0.60으로 유의미한 상관관계가 발견되었습니다.

레이팅 최대치로 계산했을 때에는 레이팅 1500 이하 분들의 데이터에서 왜곡이 심하게 일어나, 현재 레이팅으로 계산했습니다.

이 글에서는 정수 $N$의 소인수분해를 결정적으로 (deterministic) $O(N^{1/3})$ 시간만에 할 수 있는 리먼 소인수분해 (Lehman Factorization) 기법을 소개하고, 유도합니다. 교과서에 소개된 구현은 다음과 같습니다.

// 가장 작은 소인수를 return
int lehmanFactorization(int n)
{
    // n > 21이어야 함
    if (n <= 21) return trialDivision(n);
    // n^(1/3)까지의 수로 나눔
    // cbrt는 세제곱근을 구하는 함수
    for (int i = 2; i < ceil(cbrt(n)); i++)
    {
        if (n % i == 0) return i;
    }
    // 이 글에서 주로 설명할 부분
    for (int k = 1; k <= ceil(cbrt(n)); k++)
    {
        double fourKN = 2 * sqrt(k * n)
        for (int a = ceil(fourKN); a <= floor(fourKN + cbrt(sqrt(n)) / 4 / sqrt(k)); a++)
        {
            if (isSquare(a * a - 4 * k * n)) return gcd(a + sqrt(b), n);
        }
    }
    // 이제 n은 소수
    return n;
}

$\sqrt N$보다 작거나 같은 숫자로 정수 $N$을 나누면 $O(\sqrt N)$ 시간만에 소인수분해 할 수 있는 것은 잘 알려져 있습니다. 이 방법을 trial division이라고 부릅니다.

int trialDivision(int n)
{
    for (int i = 2; i <= sqrt(n); i++)
    {
        if (n % i == 0) return i;
    }
    return n;
}

또한, $9991$과 같은 숫자는 $9991=100^2-3^2=(100-3)\times(100+3)=97\times103$인 것을 관찰하여 쉽게 소인수분해 할 수 있습니다. 이 방법을 페르마의 소인수분해 방법이라고 부릅니다.

페르마의 소인수분해 방법으로 $N=pq$ 및 $p\ge q$를 만족하는 두 수 $p$, $q$를 찾으면, $N=\left(\frac{p+q}2\right)^2-\left(\frac{p-q}2\right)^2$가 됩니다. $\frac{p+q}2$가 정수인 것이 편리하기 때문에, $p$와 $q$의 홀짝이 같으면 좋습니다. 이것은 $N$을 $2$로 나눠지지 않을 때까지 나눠서 쉽게 달성할 수 있습니다. 그리고, 이제 $p$와 $q$가 홀수이므로 $\frac{p+q}2$가 최대이려면 $q=3$, $p=N/3$이어야 하며, 이 때 $\frac{p+q}2=\frac{N+9}6$입니다.

int fermatFactorization(int n)
{
    if (n % 2 == 0) return 2;
    for (int i = sqrt(n); i <= (N + 9) / 6; i++)
    {
        if (isSquare(i * i - N)) return gcd(i + sqrt(i * i - N), N);
    }
    return n;
}

이 방법은 최악의 경우 $N/6$회 정도의 loop를 돌 수 있기 때문에, 일반적인 수의 소인수분해 방법으로는 적절하지 않습니다.

Trial division은 작은 인수를 가진 숫자를 빠르게 소인수분해 할 수 있지만, 두 인수가 서로 비슷한 숫자의 소인수분해는 느립니다. 반대로, 페르마의 소인수분해 방법은 인수가 서로 비슷한 숫자의 소인수분해가 빠르고, 작은 인수를 가진 숫자에 대해 가장 느립니다. (for 문의 순회 방향을 바꿔도 이 사실이 변하지 않습니다. 이 사실의 증명은 연습문제로 남깁니다.)

따라서, 작은 인수에 대해 나눠본 뒤 페르마의 소인수분해 방법을 적용하는 것을 생각할 수 있습니다.

int trialFermat(int n)
{
    // M은 N에 따라 바뀔 수 있는 수. 아래에 설명합니다.
    for (int i = 2; i <= M; i++)
    {
        if (n % i == 0) return i;
    }
    for (int i = sqrt(n); i <= f(M); i++)
    {
        if (isSquare(i * i - N)) return gcd(i + sqrt(i * i - N), N);
    }
    return n;
}

여기서, $f(M)$은 $N=pq$를 만족하는 $p$와 $q$에 대해 $\frac{p+q}2$의 최대값이며, $p=M$, $q=N / M$일 때를 생각하면 $f(M)=\frac{N+M^2}{2M}$입니다.

흔히 lazy propagation을 사용하여 푸는 것으로 알려진 이 두 문제는 사실 펜윅 트리만으로 풀 수 있습니다.

다음 연산을 효율적으로 수행하는 자료구조를 만들어 봅시다. 이것으로 16975번 - 수열과 쿼리 21을 풀 수 있습니다.

1. $A_L$, $A_{L+1}$, $\cdots$, $A_R$에 각각 x씩 더한다.
2. $A_k$를 출력한다.

$B_1 = A_1$, $B_k = A_k - A_{k-1}$이라고 두면, 각각의 쿼리는 이렇게 변합니다.

1. $B_L$에 x를 더하고, R이 마지막 인덱스가 아니면 $B_{R+1}$에서 x를 뺀다.
2. $B_1 + \cdots + B_k$를 출력한다.

안녕하세요 jaehoo1입니다.

저는 BOJ에서 문제를 풀 때, 로컬(Visual Studio 2010)로 코딩을 한 다음에, 코드를 복사해 붙여넣어 푸는데요, 틀리면 가끔 실행환경 차이를 고려하지 않고 로컬에 맞춰 코딩을 해서 틀릴때가 있습니다. 그럴 때 예전에는 ideone.com이라는 온라인 컴파일러를 사용해 차이를 알아보거나 했었습니다. 근데 ideone은 컴파일을 할 때, 입력파일을 같이 컴파일 한다는 점이 있는데, 이 입력파일의 크기가 64KB로 제한이 되어있습니다. 입력 데이터 제한이 작은 문제들은 웬만한 TC들을 만들어서 넣어볼 수 있지만, 제한이 조금만 커지면 입력데이터가 64KB를 초과하는 문제들이 간혹 있습니다(사실 자주 보입니다). 이런 문제들의 경우, ideone에서 돌려볼 수 없단 점이 많이 아쉬웠습니다. 또, 제가 붙여넣은/작성한 코드들이 저장되지도 않고, 나갔다 들어오면 다시 초기화 됩니다(물론, 링크를 저장하는 방식으로 코드를 저장할 순 있습니다). 마지막으로, 실행이 즉각적이지 않고, 메모리를 좀 쓴다는 점이 있습니다.

1000번 문제를 풀 때 사용하는 코드를 기준으로 보자면,

#include <stdio.h>
int main() {
    int a, b;
    scanf("%d %d",&a,&b);
    printf("%d\n",a+b);
    return 0;
}

ideone 기준으로는 0s 4452KB, BOJ 기준으로는 0ms 1116KB 가 듭니다.

안녕하세요, Ba*rkingDog입니다. 삼성 소프트웨어 멤버십 기술 블로그에 Persistent Segment Tree 튜토리얼을 올렸는데 공유를 하면 좋을 것 같아 동일한 내용을 BOJ 게시판에도 올립니다. 제 글 이외에도 도움이 될만한 글들이 많습니다. 기술 블로그를 확인해보세요.

Persistent Segment Tree를 이해하기 위해서는 Segment Tree에 대한 이해가 선행되어야 합니다. Segment Tree를 모른다면 Persistent Segment Tree를 이해할 수 없으니 여기까지 읽으신 독자 분이면 Segment Tree를 아마 알고 계실테지만 그래도 다시 한 번 짚고 넘어가겠습니다.

예전부터 주변에서 코포 레이팅이 xx면 롤에서 어느정도 되는지, 혹은 반대로 롤 xx면 코포에서 어느정도 되는지 물어보는 사람이 꽤 있었습니다.
이 글에서는 op.gg에 있는 롤 티어 통계와 여기있는 코드포스 레이팅 통계를 이용해 어떤 티어가 어떤 색깔에 대응되는지 소개합니다.

여기에서 데이터를 수집했습니다.

이 글은 우분투 환경에서 서브라임텍스트를 사용하는 방법에 관한 글입니다.
이 글은 다음 동영상을 참고하여 쓰였습니다.


윈도우 환경에서 Sublime Text를 사용하는 방법은 아래 링크에 있습니다.
https://www.acmicpc.net/blog/view/24
이 글에서는 위의 방법을 모두 안다고 가정하겠습니다.

g++ 과 서브라임이 모두 깔려있는 Ubuntu에서 빌드 설정을 다음처럼 주면 input.txt를 입력으로 받으면서 배시창으로 실행됩니다.

{
    "cmd": ["g++", "$file", "-o", "${file_path}/${file_base_name}"],
    "file_regex": "^(..[^:]*):([0-9]+):?([0-9]+)?:? (.*)$",
    "working_dir": "${file_path}",
    "selector": "source.c, source.c++, source.cxx, source.cpp",
    "variants": 
    [ 
        { 
            "name": "Run", 
            "shell": true,
            "cmd": ["g++ -O2 -std=c++11 \"${file}\" -o \"${file_path}/${file_base_name}.out\" && gnome-terminal -e 'bash -c \"${file_path}/${file_base_name}.out < input.txt;echo;echo; echo Press ENTER to continue; read line;exit; exec bash\"'"]
        } 
    ] 
}

p.s. 알아두면 유용한 팁
숨겨놓은 메뉴를 보려면 팔레트 ( Ctrl + Shift + P ) 에서 "vmen" ( 자동으로 "View: Toggle Menu"를 검색해줍니다. )을 치고 엔터를 누르면 됩니다. ( 윈도우즈에서는 Alt키만 누르면 됩니다. )
사이드바를 토글( 있으면 없게 없으면 있게 )하려면 Ctrl 을 누른 상태에서 K, B 를 순서대로 눌러주면 됩니다.

안녕하세요, 박상수(cki86201)입니다. 지난 겨울에 열렸던 Petrozavodsk(페트로자보츠크) 프로그래밍 캠프에 다녀왔습니다.

"대학생을 위한 프로그래밍 캠프가 있으면 좋겠다"는 생각을 해 본 적 있으신가요?

우리나라에는 중,고등학생을 위한 훌륭한 캠프 정보올림피아드 계절학교가 있지만, 아쉽게도 대학생을 위한 캠프는 거의 없습니다.

얼마전 APIO 2019 대회가 진행되었다. Open Contest를 진행한 후, 풀이를 써달라는 분이 계서서 풀이를 작성하였다.

이러고 바로 풀이로 진행하면 블로그 미리보기로 스포일러가 되기 때문에, 몇가지 TMI를 추가한다. 한국은 비공식 성적으로 금메달 0개, 은메달 13개, 동메달 0개를 얻었으며, 보통 6명의 학생만 메달을 받는 것이 룰이지만 너무 많은 동점이 나와서 13명의 학생이 수상을 하는 일이 발생하였다. APIO 2008 이후 초유의 사태이지만 사실 금메달 컷이 깔끔하게 잘려서 별 상관은 없는 것 같다.

문제는 Strange Device / Bridges / Street Lamps 3 문제가 출제되었다.