참조 분류 URL 문제 구간 합 구하기 참조 라이브러리 fenwick_tree_BIT, sharifa_header.h 이 글에서 설명하는 코드 02042_구간 합 구하기 개요 시간복잡도: $ O(N + (k+m)log N) $ 공간복잡도: $ O(N) $ N, m, k는 문제에서 주어진 그대로이다. N은 원소의 수이다. 문제 풀이 이 문제는 흔히 인덱스 트리라고 부르는 자료구조를 써도 풀리지만,...

참조 분류 URL 문제 구간 합 구하기, 구간 합 구하기 3 응용 문제 나무 심기 이 글에서 설명하는 라이브러리 fenwick_tree_BIT.h 개요 시간복잡도: $ O(M log N) $ 구간 합 구하기: $ O(log N) $ 값 업데이트하기: $ O(log N) $ 공간복잡도: $ O(N) $ N은 원소의 수, M은 연산의 수이다....

주의: 이 글을 읽는 여러분이, 만약 git을 많이 써 봐서 익숙한 것이 아니라면, 반드시 손으로 직접 따라 칠 것을 권한다. 눈으로만 보면 100% 잊어버린다. 저번 글에서 작업하던 것을 이어서 한다. 저번 글에서는 git_tutorial 디렉토리를 생성하는 것까지 했었다. Local Directory 생성 이제 git_tutorial 옆에 새로운 디렉토리를 생성한다. 이름은 자유지만 필자는 git_tutorial_clone으로...

참조 분류 URL 문제 BOJ 13277: 큰 수 곱셈 참조 라이브러리 fft.h, conversion_library.h 이 글에서 설명하는 코드 13277_큰 수 곱셈 개요 시간복잡도: $ O(N) $ 공간복잡도: $ O(N) $ N은 두 수의 길이 중 max값이다. 문제 풀이 풀이 자체는 어렵지 않다. 빠른 곱셈을 위해, FFT 를 쓰면 된다. 그게 이...

참조 분류 URL 문제 스택 이 글에서 설명하는 코드 10828_스택 개요 시간복잡도: $ O(N) $ 공간복잡도: $ O(N) $ N은 명령의 수이다. 문제 풀이 이 문제는 말 그대로 스택 그 자체이다. 여기 에서 설명한 5가지 연산만 수행하면 끝이다. 구현 특히나 이 문제는 코딩의 순서를 문제에서 주어진 5가지 명령에 쓰인 그대로...