스택의 대표적인 문제이다. vector를 활용해서 풀 수도 있으나, 여러가지 측면때문에 stack 헤더를 활용하여 문제를 접근할 수 있다. 사용할 수 있는 연산은 총 5개이다. 1. push 데이터를 stack에 집어넣는다. 2.pop 맨 위의 데이터를 지운다. 3.size 스택의 크기를 반환한다. 4.empty 비어있는지 확인한다. 5.top 맨 위의 데이터를 반환한다. 단, Stack에서 주의해야할 지점은 pop과 top 연산을 할 때 반드시 stack의 크기가 0이 아닌지를 확인해야 한다. 만약, 크기가 0인데 pop시키거나 top연산을 하게 되면 컴파일 에러가 뜨게 된다. 해당하는 방법으로 코드를 구현하면 다음과 같다. 다만, 이 코드에서는 pop과 top연산을 할 때 그 상황에서의 stack의 ..

이 문제는 전형적인 DP문제이다. 다만, 0과 1을 호출하는 갯수를 계산을 하라는 점에서 살짝은 낯설게 느껴질 수 있으나 본질적으로 두 수를 더하는 과정에서 0과 1을 더하는 양상을 각각 구분해서 저장해주는 방식으로 이용해주면 된다는 것을 쉽게 알 수 있다. 이 과정에서 가장 처리가 쉬운 방법이 구조체를 이용하는 것이다. 추가적으로 피보나치의 경우에는, 같은 계산을 매우 반복해서 해야하는 상황이 등장하게 되므로 DP를 이용하여 이미 존재하는 숫자의 경우에는 계산을 하지 않고 바로 return만 시켜주면 된다. 해당하는 방식으로 코드를 구현하면 다음과 같다. #include #include #include #include #include using namespace std; typedef struct{ i..

문제는 되게 쉬운 편이고, 시키는 대로 계산하기만 하면 되는데 Large의 경우에는 매우 숫자가 기하급수적으로 커지므로 pow함수를 이용하여 한번에 계산하기 보다는 그때그때 나머지를 연산하여 최대한 숫자를 줄이면서 계산해야 한다. 이 점만 유의하면 매우 쉬운 문제이다. 위의 내용을 바탕으로 코드를 구현하면 다음과 같다. #include #include #include #include #include #include using namespace std; typedef long long ll; int main(void){ int n; cin >> n; string data; cin >> data; int r = 31; int M = 1234567891; ll hash = 0; for(int i = 0; i ..

수학에서 학습한 공식을 활용하면 된다. 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..

이 문제에 대해서는 접근하는 방법이 여러가지가 있다. 1. 이분탐색으로 접근하는 방법 숫자가 상당히 큰 것을 보고, 이분탐색을 활용하여 시간을 줄여서 숫자카드에 존재하는 숫자를 탐색해주면 된다고 파악하면 된다. 이 문제의 경우에는, 이분탐색을 정확하게 접근해야 하는데, 결과적으로 나오는 index의 값이 upper_bound와 lower_bound로 나뉜다. 이분탐색으로 접근하기 위해서는, 데이터가 연속적으로 이어져있어야 하기때문에 반드시 sorting을 하고 나서 진행해야 한다. 일반적으로 중복되는 수가 없는 경우 중간값이 compare하는 값보다 작을 때는, start부터 mid값까지의 값은 compare하는 값보다 무조건 작을 수 밖에 없으므로 판단해야하는 범위는 (mid + 1, end)로 이동하..