수학에서 학습한 공식을 활용하면 된다. nCr = n! / (n-r)!*r! 을 약분하면 r의 갯수만큼 n부터 1씩 작아지는 수들의 곱에서 r!을 나눈것으로 쉽게 구할 수 있다. 해당하는 알고리즘으로 코드를 작성하면 다음과 같다. #include #include #include #include #include using namespace std; int main(void){ int n, k; cin >> n >> k; int result_above = 1; for(int i = 0; i < k; i++){ result_above *= (n - i); } int result_down = 1; for(int i = 1; i < k + 1; i ++){ result_down *= i; } cout

방법론 자체는 11651번과 완전하게 동일하다. 다만, x가 증가하는 것이 먼저 고려되어야 한다는 것을 이용하여 compare함수만 수정해주면 된다. 해당하는 알고리즘을 활용하여 코드를 작성하면 다음과 같다. #include #include #include #include #include using namespace std; typedef struct{ int x; int y; }point; bool compare(const point value1, const point value2){ if (value1.x == value2.x){ return value1.y ..

이 문제는 x,y좌표를 제시하고 있으므로 x와 y를 저장하는 구조체를 만든뒤 sorting하면 된다. 단, 구조체를 정렬하는 방식에 대해서는 정의되어 있지 않으므로 따로 compare함수를 정의하여 처리해주어야 한다. 위의 내용을 활용하여 코드를 작성하면 다음과 같다. #include #include #include #include #include using namespace std; typedef struct{ int x; int y; }point; bool compare(const point value1, const point value2){ if (value1.y == value2.y){ return value1.x < value2.x; } else{ return value1.y < value2.y..

이 문제의 경우는 약간 독특하다. 일반적으로 오름차순으로 정렬하기 위해서는 가장 간단하게는 sort를 사용하면 되지만, 이 문제에서는 시간제한은 조금 널럴한 대신 메모리제한이 매우 제한적이다. 수가 10000으로 제한되어 있으므로 배열의 index와 숫자를 연결시켜서 저장시킨 뒤, 숫자가 들어오면 해당 배열의 값을 1 증가시키는 방식으로 메모리를 아낄 수 있음을 느끼고 문제를 접근했으면 된다. 위의 알고리즘으로 문제를 접근하면 다음과 같다. #include #include #include #include #include using namespace std; int main(void){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); in..

이분탐색 (Binary search) 이분탐색은 결과적으로 나오는 index의 값을 기준으로 upper_bound와 lower_bound로 나뉜다. 단,이분탐색으로 접근하기 위해서는, 데이터가 연속적으로 이어져있어야 하기때문에 반드시 sorting을 하고 나서 진행해야 한다. 일반적으로 중복되는 수가 없는 경우 중간값이 compare하는 값보다 작을 때는, start부터 mid값까지의 값은 compare하는 값보다 무조건 작을 수 밖에 없으므로 판단해야하는 범위는 (mid + 1, end)로 이동하게 된다. 반면에, compare하는 값보다 클 때는, mid부터 end까지의 값은 compare하는 값보다 무조건 클 수 밖에 없으므로 판단해야하는 범위는 (start, mid -1)로 이동하게 된다. 만약,..

이 문제에서 가장 중요한 지점은, 입출력이 최대 200000 까지 되므로, 빠른 입출력을 활용하여 시간을 출여야 한다. 왜 그렇게 해야하는지에 대해서는 입출력 스트림 관련해서 상당히 복잡하므로, 실력을 키우기 전까지는 그냥 받아들이고 쓰는 것으로 하자. 방법은 다음과 같다. 메인함수에 해당 내용을 최상단에 쓰면 된다. ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 단, 이 방법을 쓰는 경우에는 getchar 같은 것들을 못쓴다는 점은 유의해야 한다. 추가적으로 이 문제의 경우에는, 존재하는지 아닌지만 판단해주면 되므로 정렬 후에 이분탐색으로 판단하는 것이 쉽다. 해당하는 알고리즘으로 코드를 구현하면 다음과 같다. #include #in..

이 문제를 요약하자면 1. 데이터를 받고 2. 자기보다 작은 숫자의 갯수를 출력한다. 라고 볼 수 있다. 즉, 이 문제를 풀기 위해서는 다음의 과정을 겪어야 한다. 1. 정렬을 한다. 2. 자기보다 작은 숫자의 갯수만 카운트 하되, 서로 다른 좌표의 갯수이므로 중복되는 것은 제거한다. 이때, 정렬하는 과정에서 O(nlogn)이고, erase까지 하는데 O(nlogn)가 사용된다. 추가로 자기보다 작은 숫자의 갯수를 전부 다 고려하려면 O(n^2)인데, 이 경우에는 시간 초과가 나므로 이분탐색을 활용해서 진행을 해주면 O(nlogn)이므로 충분히 2초안에 통과할 수 있음을 확인할 수 있다. 위의 방식을 활용하여 코드를 짜주면 다음과 같다. #include #include #include #include u..

이 문제를 보고 분할정복으로 느껴야하는 이유는 다음과 같다. 전체 횟수는 각 배열을 4등분 한 것의 합으로써 구성이 되기에 결과적으로는 각 분할된 것들을 처리해주고 한번에 더해주는 방식으로 몇번째로 방문하는지를 체크해주면 된다. 단, 이 상황에서 시작점의 x좌표와 y좌표를 기록을 하면서 길이를 게속해서 고려해야하므로 재귀함수의 인자에 x좌표, y좌표, 길이가 들어가 있어야 한다. 추가적으로 4개의 조각 중에 어느 곳에 해당하는지를 찾기 위해서 문제에서 주어진 r와 c 값을 parameter로 가지면 된다. Recursion function에서 base case는 length가 2인 케이스를 기준으로 구분해 주면 된다. 해당하는 방법으로 코드를 구현하면 다음과 같다. #include #include #in..