PROGRAMMING/알고리즘
-
(백준 9012번 스택) 라이님 블로그 대회 알고리즘 따라잡기 15) StackPROGRAMMING/알고리즘 2024. 5. 22. 21:59
백준 9012번https://www.acmicpc.net/problem/9012 '('의 쌍은 ')'임을 기억해주자!1. '('가 들어오면 stack에 넣는다2. ')'가 들어오면 stack에 '('가 있는지 확인한다- 있으면 '('을 pop해준다- 없으면 "NO"3. 1, 2번을 반복한다. 모두 반복한 후 stack이 empty가 아니면 "NO"#include #include #include using namespace std;int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; while (N--) { stack st; string s; cin >> s; bool flag = t..
-
(백준 10828번 스택) 라이님 블로그 대회 알고리즘 따라잡기 15) StackPROGRAMMING/알고리즘 2024. 5. 21. 20:07
https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220781557098&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList 스택(Stack) (수정 2019-05-14)또다른 기본 자료구조 중 하나인 스택(stack)입니다. 스택은 LIFO(Last In First Out) 자료구조인...blog.naver.com 스택 공부를 안하고 지나간 것 같아 해보았다!요즘 하고 있는 알고리즘들이 너무 어려워서 그런가.. 스택! 지난번에 읽었을 때보다 이해가 잘 된다!! 풀었다고 하기도 민망한 10828번https://www.acmicpc.net/problem/108..
-
(백준 2293번 동전 1) 라이님 블로그 대회 알고리즘 따라잡기 14) 투 포인터, 슬라이딩 윈도우PROGRAMMING/알고리즘 2024. 5. 21. 15:22
슬라이딩 윈도우로 풀어본 문제! 아이디어는 매우 단순한데, 푸는데는 시간이 조금 걸렸다^___^ 백준 2293번 https://www.acmicpc.net/problem/2293#define _CRT_SECURE_NO_WARNINGS#include #include using namespace std;int pos[10001];int main() { int n, k; scanf("%d %d", &n, &k); memset(pos, 0, sizeof(pos)); for (int i = 0; i k) continue; pos[temp]++; for (int j = 1; j = temp) pos[j] += pos[j - temp]; } } printf("%d", pos[k]);} https://www.a..
-
(백준 1484번 다이어트) 라이님 블로그 대회 알고리즘 따라잡기 14) 투 포인터, 슬라이딩 윈도우PROGRAMMING/알고리즘 2024. 5. 20. 08:09
오늘은 백준 1484번 다이어트 문제를 풀어보았다. 처음에 푼 방법부터 발전시켜서 시간과 메모리를 아주 많이 단축했다!! 백준 1484번https://www.acmicpc.net/problem/1484 첫번째 풀이더보기#define _CRT_SECURE_NO_WARNINGS#include #include using namespace std;constexpr int MAX = 10000000;// int 범위 +- 2*10^9// long long 범위 +- 9 * 10^18int main() { int N; scanf("%d", &N); vector v; v.resize(MAX+1); for (int i = 0; i weight; int s = 1, e = 1; long long diff = 0; w..
-
(백준 1644번 소수의 연속합) 라이님 블로그 대회 알고리즘 따라잡기 14) 투 포인터, 슬라이딩 윈도우PROGRAMMING/알고리즘 2024. 5. 19. 22:47
https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220795165570&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList 투 포인터(Two Pointers Algorithm), 슬라이딩 윈도우(Sliding Window) (수정: 2019-09-09)조금 성향이 비슷하다고 생각하는 기법 2개를 함께 쓰려 합니다. 첫 번째로 소개해드릴 기법은 투 포인터(t...blog.naver.comDP2를 이해하다가 두통이 와서 나름 익숙한 투포인터와 슬라이딩 윈도우 파트를 먼저 보았다. 늘 그렇듯 설명은 라이님 블로그를 참고하면 된다! 이 문제는 다 풀고 메모리 사용..
-
라이님 블로그 대회 알고리즘 따라잡기 13) DP2 이해하기PROGRAMMING/알고리즘 2024. 5. 15. 12:09
https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220793134705&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList 동적 계획법 2(Dynamic Programming 2) (수정: 2016-08-22) DP가 돌아왔습니다. 이번에 제가 쓰려는 글은 이런 겁니다. DP를 사용해서 최솟값이나 최...blog.naver.com ※ 이번 포스팅에 모든 내용은 위 블로그에 있습니다! 정확한 내용을 위해 위 포스팅을 참고하세욥🪄 여기 나오는 내용이 어려워서 ㅠㅡㅠ 나를 위해 정리해보려고 한다! 1. 백준 1149번 RGB거리https://www.ac..
-
(백준 12837번 가계부(Hard) C++) 라이님 블로그 대회 알고리즘 따라잡기 12) SegmentTree 4PROGRAMMING/알고리즘 2024. 5. 14. 15:17
이제 진짜 익숙해지고 있다!!!! 가자 Segment Tree! 백준 12837번https://www.acmicpc.net/problem/12837#include #include using namespace std;struct segTree { int n, start; vector v; segTree(int n) : n(n) { start = 1; while (start 0; i--) { v[i] = v[i * 2] + v[i * 2 + 1]; } } void add(int a, long long b) { a += start; while (a > 0) { v[a] += b; a /= 2; } } long long sum(int a, int b) { return sum(a, b, 1..
-
(백준 2357번 최솟값과 최댓값 C++) 라이님 블로그 대회 알고리즘 따라잡기 12) SegmentTree 3PROGRAMMING/알고리즘 2024. 5. 14. 14:31
세그먼트 트리랑 친해지는 중🌚 백준 2537번https://www.acmicpc.net/problem/2357#include #include #include using namespace std;constexpr int MAX = 1000000001;constexpr int MIN = -1;pair pairsum(pair p1, pair p2) { int first = min(p1.first, p2.first); int second = max(p1.second, p2.second); pair p3 = { first, second }; return p3;}struct segTree { int n, start; vector> v; segTree(int n) : n(n) { start = 1; while ..