본문 바로가기

유니온파인드4

BOJ G4 1043 거짓말 JAVA 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 문제 읽기 문제를 읽어보면 결국 사람은 두 분류로 나뉘게 된다. 지민이의 (진실을 아는 사람 + 알게 될 사람 / 전혀 모를 사람) 이 두 분류만 확실하게 구분하면 거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티의 최대 개수를 구할 수 있을 것이다. 진실을 아는 쪽이 하나라도 포함되어 있는 파티에서는 거짓말을 치지 못할 것이고, 그 외에 전혀 모를 사람에게는 거짓말을 칠 수 있을 것이다. 이러한 부분을 봤을 때, 유니온 파인드를 쓰면 빠르게 해결할 수 있.. 2024. 1. 15.
BOJ G4 1976 여행 가자 JAVA 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 문제 읽기 유니온 파인드를 모른 채로 이 문제를 처음 봤다면 인접 리스트 만들어서 DFS로 그래프 탐색을 했을지도 모른다.. 하지만 지금은 유니온 파인드를 알기 때문에, 훨씬 단순하게 생각할 수 있었다. 유니온 파인드의 개념이 궁금하면 다음 글을 참고하고 오면 좋다. 분리 집합, Disjoint Set : Union-Find 분리 집합, Disjoint Set 💡 분리 집합, Disjoint Set = 서로소 집합 분리 집합이란 이미 존재하는 집합 U에 대해, .. 2024. 1. 13.
BOJ G5 1717 집합의 표현 JAVA 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 문제 읽기 이전이었으면 이게 뭐지.. 하면서 끙끙댔을 테지만, 어제 유니온 파인드를 공부했기 때문인지, 읽자마자 이건 그냥 유니온 파인드라는 생각이 들었다. 유니온 파인드에 대해 개념을 알고 싶으면 우선 이 포스팅을 먼저 보고 오길 추천한다. 분리 집합, Disjoint Set : Union-Find 분리 집합, Disjoint Set 💡 분리 집합, Disjoint Set = 서로소 집합 분리 집합이란 이미 존재하는 집합 .. 2024. 1. 13.
분리 집합, Disjoint Set : Union-Find 분리 집합, Disjoint Set 💡 분리 집합, Disjoint Set = 서로소 집합 분리 집합이란 이미 존재하는 집합 U에 대해, 겹치는 부분이 발생하지 않도록 모든 원소들을 포함하여 분리한 부분 집합을 말한다. 즉, 전체 집합 U에 대해, U의 분리 집합 A, B는 다음과 같은 조건을 만족 한다. A, B는 U의 부분 집합이다. A, B는 공통 원소를 가지지 않는다. A, B의 합집합이 곧 전체 집합 U이다. (= A, B에 속하지 않는 U의 원소가 없어야 한다) 분리 집합의 활용 이런 분리 집합은 다음과 같은 경우에 적용된다. 가상의 프로그램에서 이러한 규칙이 있다고 하자. “A와 B가 친구 관계이고, 내가 A와 친구를 맺으면, 자동으로 나와 B는 친구 관계가 된다” 그리고 다음 사진은 이 프.. 2024. 1. 12.

티스토리툴바