본문 바로가기
반응형
[PCCP] Lv3: 섬 연결하기(42861) 해설 문제- 문제 링크: 섬 연결하기 해설- 자료구조: - 시간복잡도:  (풀이과정)1) 2) 3) 4)  코드(C언어)solution 1)더보기solution 1#includesolution 2)더보기#includesolution 3)더보기#include (C++)solution 1)- N: 노드 개수- E: costs의 길이. 간선 개수- 간선을 비용 기준으로 정렬하기 위한 시간 복잡도: O(ElogE)- costs 순회하면서 find(), union() 호출하기 위한 시간 복잡도: O(E)- 최종 시간복잡도: O(ElogE)더보기#include #include #include using namespace std;// 상호배타적 집합 정의class DisjointSet {private: vector .. 2024. 12. 24.
[PCCP] Lv1: 폰켓몬(1845) 해설 문제- 문제 링크: 폰켓몬 해설- 자료구조: - 시간복잡도:  (풀이과정)1) 2) 3) 4)  코드(C언어)solution 1)더보기#includesolution 2)더보기#includesolution 3)더보기#include (C++)solution 1)- nums를 집합으로 변환: O(N)더보기#include #include using namespace std;int solution(vector nums){ int answer = 0; // s는 nums의 중복값을 제거한 집합 unordered_set s(nums.begin(), nums.end()); // nums/2의 개수와 s의 개수 중 작은 값을 반환 answer = min(nums.size()/2, s.s.. 2024. 12. 24.
[PCCP] 자료구조 - 집합 1. 이론- 집합(set): 순서와 중복이 없는 원소를 갖는 자료구조- 집합 종류: 유한집합, 무한집합, 공집합, 상호배타적 집합- 상호배타적 집합: 교집합이 없는 집합 관계- 상호배타적 집합 활용분야: 이미지 분할, 도로네트워크 교차로, 최소신장트리의 사이클 확인, 게임개발시 물체 충돌 문제, 클러스터링 방지- 집합의 연산: 합치기, 탐색- 집합 표현: 배열을 활용한 트리 사용. 배열의 인덱스는 자신, 배열값은 부모 노드를 의미. 루트노드는 인덱스와 값이 동일- 루트 노드의 개수는 집합의 개수- Union-Find 알고리즘: union(합치기), find(탐색).- find 연산: 특정 노드의 루트 노드가 무엇인지 탐색하는 방법. 특정 노드가 같은 집합인지 확인. 재귀로 구현+) find 연산 비용은 .. 2024. 12. 14.
반응형

티스토리툴바