피보나치 수를 구하는 여러가지 방법

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

  • $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, ... 와 같습니다.

더 읽기댓글 쓰기

점 3개의 방향성을 나타내는 CCW

세 점 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;
}

더 읽기댓글 쓰기

Sublime Text 설치부터 C++ 빌드하기

0. Sublime Text란?

더 읽기댓글 쓰기

Codeforces Round #327 Div.2 참가 후기

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

시간은 일요일 오후 6시.

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

더 읽기댓글 쓰기

STL sort 튜토리얼

1. 정의

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

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

더 읽기댓글 쓰기

펜윅 트리 (바이너리 인덱스 트리)

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

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

  • 3 = 112
  • 5 = 1012
  • 6 = 1102
  • 8 = 10002
  • 9 = 10012
  • 10 = 10102
  • 11 = 10112
  • 12 = 11002
  • 16 = 100002

더 읽기댓글 쓰기

A+B (1000번 풀기)

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

Hello World 와 다른 점은

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

더 읽기댓글 쓰기

while과 for

while

while은 반복문입니다.

if문과 비슷하게 사용할 수 있습니다. if문은 조건문이 true인 경우에 1번만 수행합니다. while은 조건문이 true인 동안 계속해서 수행하게 됩니다.

더 읽기댓글 쓰기