분류 전체보기
-
(백준 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..
-
(백준 1275번 커피숍2 C++) 라이님 블로그 대회 알고리즘 따라잡기 12) SegmentTree 5카테고리 없음 2024. 5. 14. 15:37
백준 1275번https://www.acmicpc.net/problem/1275 전형적인 segment tree 문제!#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; b -= v[a]; while (a > 0) { v[a] += b; a /= 2; } } long long sum(int a, int b) { return sum(a, b, 1, 0..
-
(백준 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 ..
-
(백준 11505번 구간 곱 구하기 C++) 라이님 블로그 대회 알고리즘 따라잡기 12) SegmentTree 2PROGRAMMING/알고리즘 2024. 5. 13. 21:45
세그먼트 트리! 이제 쬐금 익숙해진 것 같다. 2042번과 매우 비슷하지만, 아직 세그먼트 트리가 익숙치 않아 푸는데 매우 매우 오래 걸렸다..^^ 2042번 풀이는 아래에...!https://jjo-mathstory.tistory.com/entry/%EB%B0%B1%EC%A4%80-2042%EB%B2%88-%EA%B5%AC%EA%B0%84-%ED%95%A9-%EA%B5%AC%ED%95%98%EA%B8%B0-C-%EB%9D%BC%EC%9D%B4%EB%8B%98-%EB%B8%94%EB%A1%9C%EA%B7%B8-%EB%8C%80%ED%9A%8C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%94%B0%EB%9D%BC%EC%9E%A1%EA%B8%B0-12-SegmentTree-1 ..
-
(백준 2042번 구간 합 구하기 C++) 라이님 블로그 대회 알고리즘 따라잡기 12) SegmentTree 1PROGRAMMING/알고리즘 2024. 5. 12. 21:13
나의 스승 라이님 블로그를 보고 오늘은 세그먼트 트리를 배워보았다. https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220791986409&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList 세그먼트 트리(Segment Tree) (수정: 2019-02-12)아마 트리 파트에서 마지막이 될 글입니다. 상당히 재미있는 자료구조입니다. 그 이름하여 세그먼트 트리(s...blog.naver.com 풀이는 라이님 깃허브에서 가져옴!!https://github.com/kks227/BOJ/blob/master/2000/2042.cpp BOJ/2000/2042.cpp ..
-
(백준 16562번 친구비 C++) 라이님 블로그 대회 알고리즘 따라잡기 12) Union Find 3PROGRAMMING/C++ 2024. 5. 9. 21:23
백준 16562번https://www.acmicpc.net/problem/16562 유니온 파인드 문제인 걸 알고봐서 아이디어를 내는 건 어렵지 않았다.연결된 그래프 중 가장 친구비가 작은 노드를 root node로 지정하고, root node들을 다 더한 값이 이준석 학생이 가진 돈보다 많으면 된다도 생각했다. 고런데,,,!! 29%에서 안되는 것이 아닌가! 그래서 찾은 문제점 1. 일단 반례부터 투척(출처) : https://www.acmicpc.net/board/view/81875반례 :5 3 2010 20 20 10 301 32 45 4답 : 20 node의 번호와 node의 value는 다르다. 1번이라고 해서 무조건 작은 친구비를 갖는게 아님!!!! 위 반례를 통해 그 부분을 수정할 수 있..