반응형 자료구조3 [C++] 코딩 테스트 필수 STL 정리 STL 이란 Standard Template Library의 줄임말로 여러가지 자료구조와 알고리즘 등을 데이터 타입에 의존하지 않게 미리 만들어 놓은 라이브러리를 의미한다. 여러가지 유용한 STL이 있지만 그 중에서도 필수적인 몇가지 container에 대해 정리해보겟다.Container는 특정한 type의 원소들을 저장하는 객체를 말한다.대표적으로 사용되는 container는 vector, list, set, map, unordered_set, unordered_map, queue, priority_queue가 있다.이외에도 deque이나 stack 등이 있지만 이번 포스팅에서는 위의 container에 대해서만 알아보겠다. 1. vector#include 를 통해 사용할 수 있다.Python의 li.. 2024. 11. 20. [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. 이전 1 다음 반응형
