반응형 C++4 [C++] Sqrt Decomposition 알고리즘 Sqrt Decomposition 알고리즘은 연속된 어떤 배열을 구간 별로 합을 bucket에 저장하여 효과적으로 구간합을 구할 수 있는 알고리즘이다. 주로 어디서 부터 어디까지 합을 구해야하는 문제에서 요긴하게 쓸 수 있다. 시간복잡도는 O( √n)으로, 보다 빠른 방법은 Segment tree 알고리즘이 있지만, Sqrt Decomposition이 상대적으로 구현하기 쉽고 Segment tree로 풀 수 없는 문제도 풀 수 있으니 꼭 알아두자. 예제로 백준 2042번: 구간 합 구하기를 풀어보자.#include #include #define MAX 1'000'001using namespace std;typedef long long ll;ll N, M, K;ll Numbers[MAX];ll Bucket.. 2024. 6. 28. [C++] Union-Find 알고리즘 Union-Find 알고리즘은 중복되지 않은 원소들로 이루어진 집합들을 표현할 때 사용하는 알고리즘이다.아래와 같이 간단하게 구현할 수 있는 자료구조로, 코딩테스트에서는 중복되지 않는 id를 가지는 집들이 있을 때, 거리별로 마을이 만들어진다던가 하는 문제에서 활용하기 좋다.#include using namespace std;int parents[11];void init() { for (int i = 1; i 출력값은 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 1 2 1 1 1 3 4 5 6 7 1 2 1으로, 1번 노드와 10번 노드, 10번 노드와 8번 노드, 2번 노드와 9번 노드가 합쳐졌을 때 각각 부모노드는 1번, 2번으로 잘 합쳐진 것을 확인할 수 있다.최종적으로.. 2024. 6. 24. [C++] 다익스트라 알고리즘 다익스트라 알고리즘은 음의 가중치가 없는 그래프의 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘이다. 음의 가중치가 있는 그래프의 경우 벨만 포드 알고리즘을 사용하여야 한다.우선순위 큐를 이용하여 다음과 같이 간단하게 구현할 수 있다.#include #include #include #define MAX 100#define INF 987654321using namespace std;vector > nodes[MAX];int dist[MAX];priority_queue > pq;void Dijkstra(int start) { dist[start] = 0; pq.push({0, start}); while(!pq.empty()) { int len = -pq.top()... 2024. 6. 16. [C++] pair의 속도 최근에 SWEA 문제를 차근차근 풀어보고 있는데,생각지도 못한곳에서 시간초과로 인해 몇시간을 헤맸어서 이에 대해 적어본다. 문제는 5650. [모의 SW 역량테스트] 핀볼 게임 에서 발생했었고, 코드는 이 문제에 대한 솔루션이다. SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 문제 자체는 굉장히 직관적이고 이해하는데 어렵지 않다.정말 문제 그대로 반복문으로 구현하기만 하면 된다.#include #include #include #define MAX 150using namespace std;int N, ans;/* up left down right */int dr[4] = {-1, 0, 1, 0};int dc[4].. 2024. 6. 2. 이전 1 다음 반응형
