solved.ac 티어 v. 코드포스 레이팅

solved.ac 티어 v. 코드포스 레이팅

solved.ac 티어 v. 코드포스 레이팅에 대한 통계를 작성해봤습니다. 표본 n = 624이고, R2 = 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}$입니다.

더 읽기댓글 쓰기

펜윅 트리 200% 활용하기

흔히 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$를 출력한다.

더 읽기댓글 쓰기

온라인 컴파일러 Repl을 사용해봅시다

안녕하세요 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 가 듭니다.

더 읽기댓글 쓰기

Persistent Segment Tree 튜토리얼

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

Segment Tree

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

더 읽기댓글 쓰기

코드포스 레이팅과 롤 티어의 비교

서론

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

 

롤 티어

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

       
챌린저 : 0.01%  그랜드마스터 : 0.04%  마스터 : 0.09% 
다이아1 : 0.25%  다이아2 : 0.56%  다이아3 : 1.26%  다이아4 : 3.68% 
플레1 : 5.00%  플레2 : 6.85%  플레3 : 9.25% 플레4 : 14.85%
골드1 : 18.90%  골드2 : 25.12%  골드3 : 32.25%  골드4 : 43.69% 
실버1 : 51.12%  실버2 : 60.68%  실버3 : 69.52%  실버4 : 79.40% 
브론즈1 : 85.84%  브론즈2 : 90.66%  브론즈3 : 94.48%  브론즈4 : 97.53% 
아이언 : 100% 

더 읽기댓글 쓰기

[사용법] Ubuntu에서 SublimeText 빌드환경 만들기

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


윈도우 환경에서 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 를 순서대로 눌러주면 됩니다.

더 읽기댓글 쓰기

36th Petrozavodsk Programming Camp 참가 후기 (1)

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

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

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

더 읽기댓글 쓰기

APIO 2019 풀이

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

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

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

더 읽기댓글 쓰기

Berlekamp-Massey 알고리즘

Berlekamp-Massey 알고리즘은 특정한 DP의 점화식을 찾아주는 알고리즘이다. $10^{18}$ 번째 피보나치 수를 찾기 위해서 행렬 곱셈을 짜고, 타일 채우기 문제를 풀기 위해서 수많은 점화식과 씨름하던 옛 시간은 이젠 안녕. 이제는 백트래킹 짜고 하드코딩해서 넣으면 끝난다.

이 글은 알고리즘의 구현법, 동작 원리나 증명에 대해서 거의 설명하지 않는다. 그 이유는 내가 구현법과 동작 원리, 증명을 모르기 때문이다. 알고리즘 구현은 여기에서 복붙해서 사용하면 된다. 이론적 배경지식이 상당히 깊지만, 그 활용도가 매우 높기 때문에, 일단 이해하지 말고 작동법부터 제대로 깨우친 후, 나중에 다시 돌아와서 방법을 이해하는 것을 추천한다.

1967년 이 알고리즘을 개발한 수학자 Elwyn Berlekamp가 최근 (2019년 4월 9일) 사망했습니다. 고인의 명복을 빕니다. A final game with Elwyn Berlekamp

더 읽기댓글 쓰기