Little Jay

중등교육에서 배운 nCm을 출력하는 문제이다. 하지만 여기서 n이 매우 크다면 그 수는 주체할 수 없을 만큼 커질 것이다. 문제의 예시에서의 100C6만 하더라도 1192052400이 출력된다. 따라서 이를 long long 형태가 아닌 string으로 문제를 해결해야 한다. 그리고 떠오를 수 있는 것은 Paskal의 삼각형이다. Paskal의 삼각형의 점화식은 nCm = n-1Cm-1 + n-1Cm 이다. 따라서 이를 재귀적으로 구해준다면 문제를 해결할 수 있다. #include #define endl '\n' #define ll long long using namespace std; string arr[101][101]; int n, m; string longadd(string a, string b)..

일반적으로 경제학에서 설명하는 손익분기점을 찾는 것이 아니라 이익이 발생하는 시점을 손익분기점으로 한다 처음에는 O(N)으로 풀었는데 시간초과가 떴다. 생각을 하면 이걸 O(1)로 풀 수 있다. #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); long long a, b, c; cin >> a >> b >> c; if (b >= c) { cout

비트마스킹 처음으로 비트마스킹에 대해서 다뤘던 문제이다. 처음에는 무지성으로 벡터를 이용해서 풀면 될 줄 알았지만, 백준에 달려있는 태그랑 메모리를 보니까 이거는 벡터로 풀면 안되겠다는 것을 깨달았다. 자바를 배울때 stream 연산자를 배워놔서 조금은 쉽게 공부하고 풀 수 있었다. #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); long long n; cin >> n; string s; int x, BIT = 0; for (long long i = 0; i > s; if (s == "add") { cin >> x; BIT |= (1 > x; BIT &= ~..

저번 글을 보면 내가 이분탐색(이진탐색)에 약하다는 것을 깨달았다. solved.ac 에서 binary search 태그를 검색해서 내가 풀 수 있는 문제들을 풀어보는 것을 목표로 삼았다. 클래스 점수도 빨리 올려야 되는데 언제올리냐..... 이 문제는 영어 문제이다. 간단히 핵심만 해석하자면, 이분 탐색을 할 때마다 mid 값이 바뀌게 되는데 그 값을 출력해주면 되는 문제이다. 이분 탐색은 아래의 블로그를 참조했다. 아직 알고리즘에서 걸어야 할 길이 먼거같다...... https://blockdmask.tistory.com/167 [탐색] 이진탐색 (Binary Search) 구현 방법 안녕하세요. BlockDMask 입니다. 알고리즘 코딩 사이트(백준 온라인 저지)에서 '수 찾기' 문제를 풀다가 이진..

main이 아닌 함수만 구현하는 문제 문제에서 template를 다 주었기 때문에 안에만 구현해주면 되는 간단한 문제 #include long long sum(std::vector& a) { long long answer = 0; for (int i = 0; i < a.size(); i++) { answer += a[i]; } return answer; }

이 문제는 문제 자체를 이해하는데 많이 시간이 소요되었다 결론부터 말하자면 pop()으로 나오는 숫자들이 처음의 배열과 똑같이 되는 경우를 찾고, 아닌경우는 NO를 출력하면 되는 것이다 문제를 조금 친절히 설명해주면 좋겠지만 문제를 분석하는 것도 결국 능력이기에...... #include #include #include using namespace std; int main() { stack st; int n, x; cin >> n; vector v; int max = 0; while (n--) { cin >> x; if (x > max) { for (int i = max + 1; i

stack 자료구조를 사용하면 쉽게 풀 수 있는 문제 문제를 풀다가 utility 헤더에 있는 make_pair을 처음에 이용했는데 이게 segmentation error를 발생시켰다 구글링을 해보니까 이게 허용되지 않은 메모리 영역에 접근을 시도하거나, 허용되지 않은 방법으로 메모리 영역에 접근을 시도할 경우 발생한다고 한다. 왜 발생하는지는 모르겠지만,make_pair을 사용하는 것을 포기하고 대괄호로 묶에서 push하는 방법으로 하니까 맞았다.고수님들 계시면 이게 왜 발생하는지 알려주시면 너무 감사하겠습니다...... #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.t..

처음에 시간 초과가 떠서 봤더니 ios_base::sync_with_stdio(0); cin.tie(0); 이거 두개 안해서 틀렸었다. 항상 시간 초과가 나면 킹받는다. 이분(이진)탐색 즉, Binary Search를 이용하는 문제이다 자료구조를 배우긴 했지만 Binary Search를 배우지는 않아서 algorithm 헤더에 있는 binary_search 메소드를 사용했다 이 부분 구현은 혼자 따로 해봐야 겠다 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, m, x; cin >> n; vector v; for (int i = 0; i < n; i++) {..

컴공을 전공하면 정수론을 배운다 정수론에서 가장 중요한 것은 개인적으로 모듈러 연산인 것 같다 (이거에 대해서 한 학기동안 배운 것 같다) 모듈러 연산은 나머지 연산이며 이거는 코딩할때 간단히 나머지 연산자만 사용하면 된다 이 문제를 풀때 조건을 제대로 안읽어서 m, r 값을 뭐라고 해야할지 한참 고민했었다. 문제만 제대로 읽었으면 쉽게 풀었을 것 같다 나중에 한번에 나머지 연산을 해주는 것 보다는 바로바로 숫자에 대해서 나머지 연산을 해주는 것이 좋다 안그러면 long long을 넘어가는 정수가 저장되어 에러가 날 수도 있다 #include #include using namespace std; #define r 31 #define m 1234567891 int main() { int n; cin >> ..

처음에는 무지성으로 풀다가 음수인 숫자를 못보고 잘못 풀었음을 느꼈다 음수를 받을 때 어떻게 하면 좋을지 좀 많이 고민했었는데 이분 탐색으로도 안풀려서 한시간 고민하다가 안되서 결국 구글링 C++의 algorithm에는 다양한 기능들이 있다 그 중 lower_bound, upper_bound라는 기능들이 있는데 이거를 활용하면 정말 간단하게 풀리는 문제였다 #include #include #include using namespace std; int main() { int n, m, x, y; cin >> n; vector v; for (int i = 0; i > x; v.push_back(x); } sort(v.begin(), v.end()); cin >> m; vector..