정수 $a$를 $m$으로 나눈 나머지 연산의 곱셈 역원은 $a \times a^{-1} \equiv 1 \pmod m$을 만족하는 $a^{-1}$을 말합니다.

즉, $a^{-1} \equiv x \pmod m$을 만족하는 $x$를 말합니다.

역원은 $a$와 $m$이 서로소인 경우에만 존재합니다.

피보나치 수는 다음과 같이 정의되는 수열입니다.

• $F_0 = 0$
• $F_1 = 1$
• $F_n = F_{n-1} + F_{n-2}$

피보나치 수를 조금 써보면, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... 와 같습니다.

세 점 P1(x1, y1), P2(x2, y2), P3(x3, y3)가 있을 떄, 점 3개를 이은 선분은 어떤 방향성을 나타내게 될까요? 11758번 문제: CCW

가능한 경우의 수는 총 3가지가 있습니다. 반시계 방향, 시계 방향, 일직선. 시계 방향을 -1, 일직선을 0, 반시계 방향을 1이라고 했을 때, P1은 검정색, P2는 초록색, P3을 파란색으로 나타내면 아래 그림과 같습니다.

배열 A가 있고, 여기서 다음과 같은 두 연산을 수행해야하는 문제가 있습니다. 10999번 문제: 구간 합 구하기 2

1. 구간 l, r (l ≤ r)이 주어졌을 때, A[l] + A[l+1] + ... + A[r-1] + A[r]을 구해서 출력하기
2. i번째 수부터 j번째 수에 v를 더하기. A[i] += v, A[i+1] += v, ..., A[j-1] += v, A[j] += v

수행해야하는 연산은 최대 M번입니다.

가장 가까운 두 점 찾기 문제는 2차원 평면 위에 점 N개가 있을 때, 거리가 가장 가까운 두 점을 찾는 문제입니다. (2261번 문제: 가장 가까운 두 점)

N이 작은 경우에는 모든 경우를 다해보는 방식을 이용해서 구현할 수 있습니다.

#include <cstdio>
int x[100000];
int y[100000];
int dist(int x1, int y1, int x2, int y2) {
    return (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2);
}
int main() {
    int n;
    scanf("%d",&n);
    for (int i=0; i<n; i++) {
        scanf("%d %d",&x[i],&y[i]);
    }
    int ans = -1;
    for (int i=0; i<n-1; i++) {
        for (int j=i+1; j<n; j++) {
            int d = dist(x[i],y[i],x[j],y[j]);
            if (ans == -1 || ans > d) {
                ans = d;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

일기형식으로 글을 써보겠습니다.

시간은 일요일 오후 6시.

아침부터 알고리즘 강의를 10~1, 2~5시를 하고나서 저녁도 못먹고 참가하는 대회이고, 졸려 죽겠어서 참가할지 말지 고민을 엄청많이 했지만, 일단 참가를 하기로 결정했다.

알고리즘 헤더파일에서 제공하는 STL로써 범위내에서 주어진 범위내에서 원소들을 정렬합니다. 이때 정렬하는 방식(오름차순, 내림차순 등등등)은 사용자가 정의할 수 있으며, 동일한 원소에 대해서는 그 순서가 보장되지 않습니다. 이때 std::sort는 숫자 뿐만 아니라 대소 비교가 가능한 모든 원소에 대해서 정렬을 할 수 있습니다. 즉 int 뿐만 아니라 char, string 역시 정렬이 가능하고, 사용자가 정의한 객체 역시 연산자 오버로딩('<')을 정의해주면 정렬이 가능합니다. 또한 동일한 원소에 대해서 그 원소들의 상대적 순서를 보장해 주는 라이브러리도 존재합니다.

자세한 내용은 여기를 참고해 주세요.

블로그: 세그먼트 트리 (Segment Tree) 에서 풀어본 문제를 Fenwick Tree를 이용해서 풀어보겠습니다. Fenwick Tree는 Binary Indexed Tree라고도 하며, 줄여서 BIT라고 합니다.

Fenwick Tree를 구현하려면, 어떤 수 X를 이진수로 나타냈을 떄, 마지막 1의 위치를 알아야 합니다.

• 3 = 11₂
• 5 = 101₂
• 6 = 110₂
• 8 = 1000₂
• 9 = 1001₂
• 10 = 1010₂
• 11 = 1011₂
• 12 = 1100₂
• 16 = 10000₂

1000번 문제: A+B는 두 수를 더하는 문제로 온라인 저지에서 가장 쉬운 문제 중 하나입니다.

Hello World 와 다른 점은

1. 숫자를 입력 받아야 한다
2. 숫자를 어디엔가 저장해야 한다
3. 그 저장한걸 출력해야 한다