728x90 반응형 알고리즘8 [백준] 분리집합(유니온-파인드) 백준 문제 풀이 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 분리 집합 알고리즘 -교집합이 존재하지 않는 두개 이상의 집합을 뜻한다. -같은 집합에 속한 원소들을 O(1)의 시간 복잡도로 확인하는 방법으로 사용된다. -따라서 같은 집합에 속한 부모 값을 기준으로 두 집합을 Union(합)-Find(찾기)를 진행한다. -대표값(부모 노드)를 찾아 이용한다. Union 연산 -합집합 연산으로 a, b 두 개.. 2023. 6. 24. [백준] 다리 놓기 - DP 문제 보러 가기 해당 문제는 백준 DP 알고리즘 분류에서 Silver 5 문제입니다. 문제 설명은 생략하고 제가 생각한 풀이를 적어보겠습니다. 참고로, 저는 C++ 언어를 사용합니다. 같이 생각해보기? 왼쪽의 다리와 오른쪽 다리를 연결합니다. 또한 다리는 각 1대1로 대응되어 건설됩니다. 이때 다리 건설은 서로 겹치지 않는다고 했으니, 무조건 1대1 대응이 확정입니다. 그렇다면 다리의 수는 항상 오른쪽 구역이 더 많은데 서로 중복되는게 없어야 한다? 즉 순서는 상관 없지만, 중복되는 것을 빼고 계속 뽑는다는 의미겠죠? 예, 조합을 의미합니다. 오른쪽 기준 내가 왼쪽 구역에서 다리를 선택하겠어! 라는 생각으로 문제를 접근해봅시다. 시작 전에 조합 공식 기억나시나요? 여기 있습니다!! 출처는 인터넷 ㅎ 피보.. 2022. 11. 12. 이전 1 2 다음 728x90 반응형
