파스칼의 삼각형을 이용하면 이항계수를 쉽게 구할 수 있다. 쉽게 구한 이항계수를 통해서 11^n도 이항정리로 해결할 수 있는데 풀이는 다음과 같다

분할정복의 대표적인 예 merge : 정복, sort : 분할, 2개의 함수로 구성되어 있다 1. stable sort 중 하나로 중복 키 순서가 보장된다 2. 평균, 최악, 최고의 시간복잡도는 동일하게 O(NlgN)이다 3. 임시로 저장해야하는 배열이 있어야하므로 기존보다 2배의 메모리를 잡아먹는다 위 채점은 merge sort로 아래 채점은 heap sort이다 깃허브주소: https://github.com/surinoel/boj/blob/master/merge_sort.cpp

x, y 좌표평면에 점 3개가 있고, 넓이를 구함으로써 이어진 점들의 방향이 CW, CCW임을 알 수 있다 [참고] https://www.acmicpc.net/blog/view/27 참고문제: https://www.acmicpc.net/problem/11758 깃허브주소: https://github.com/surinoel/boj/blob/master/11758.cpp

단점 > 함수를 반복적으로 호출하면서 생기는 메모리 사용량과 오버헤드로 인해 성능이 저하된다는 점이 있다. 호출이 되면서 리턴할 주소와 내용들을 저장하고, 돌아갈 때도 이를 불러온다는 점에서 시간이 지연된다 장점 > 특정 알고리즘 구현에 대해서는 보다 표현이 자연스러울 수 있다 (가독성) - 퀵 정렬, 병합 정렬 - 팩토리얼 구하기 - 그래프 DFS

구간 합을 구할 때 사용하는 유용한 자료구조인 세그먼트 트리다. 구간 합은 데이터가 나열되어 있을 때, 특정 범위에서의 데이터 합을 말한다. 누적합을 구했다는 가정 하에 구간 합은 O(1)의 시간복잡도로 구할 수 있지만, 변경된 사항이 생긴다면 다시 O(N)의 시간복잡도로 누적합을 수정해야 한다. 하지만 세그먼트 트리를 이용하면 수정했을 때도 트리의 높이인 O(lgN)만으로 누적합을 구할 수 있다 1. 세그먼트 트리(누적합) 만들기 리프 노드를 배열 원소를 하고 루트로 올라갈수록 재귀적으로 누적합이 계산된다. 완전 이진트리로 구성하기 때문에 자식 인덱스는 2*부모 + 1, 2*부모 + 2로 구성된다 long long init(int idx, int start, int end) { if (start == ..

Red black tree 기반의 균형 이진트리로 구성되어 있다. key, value 중 key 값으로만 구성되어 있고, key의 중복은 없다. 기본 정렬은 오름차순으로 선언 시 바꿀 수 있다. 템플릿 인자 2번째에 사용자 정의 정렬 함수를 넣어줄 수 있다. 그리고 insert 함수는 pair 반환형을 가지고 있는데, bool 값을 보고 값이 중복되는지 아닌지를 확인할 수 있다 #include #include #include #include using namespace std; struct cmp { bool operator()(const int &u, const int &v) { return u > v; } }; int main(void) { set s1; s1.insert(10); s1.insert(..