Union-Find2 [백준 1043] 거짓말 www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net union-find 써야하는데...까지만 파악한 문제 유니온 파인드쓰는 것 까지는 쉽게 캐치가 가능하나 그걸로 끝이 아니었다. 1. 같은 파티에 있는 사람을 체크 2. 파티로 연결된 사람들 체크 3. 진실을 말하면 안되는 사람들이 있는 파티 체크 이렇게 3가지가 필요한데 3가지가 동시에 진행되기는 힘들다. 따라서 1,2는 유니온 파인드를 사용하여 사람들을 연결하고 3은 파티별로 돌면서 참가자 중 진실을 말하면 안되는 사람.. 2021. 1. 30. [프로그래머스 2019 카카오 개발자 겨울 인턴십] 호텔 방 배정 programmers.co.kr/learn/courses/30/lessons/64063 코딩테스트 연습 - 호텔 방 배정 programmers.co.kr 와 너무 어렵다......... 풀이보고도 이해가 안갔다. 방 개수인 k가 작았더라면 쉽게 풀었겠지만 방 최대 수가 10^12로 배열로 선언할 수 없는 크기이다. 여기서 map을 떠올려야 했다. 그렇다면 map을 어떻게 사용해야 할까? 목적은 x보다 큰 값중 최소값을 찾는 것이다. 물론 전부 탐색해도 되지만 그러면 효율성이 매우 떨어진다. 이 때 필요한 것이 경로 단축을 위한 union find이다. 1번방을 사용한다면 1번방의 다음 방인 2번방을 1번방의 부모로 연결시켜 놓는 것이다. 이렇게 되면 1번방을 찾는 손님은 자연스레 2번방을 배정받는다. 2.. 2021. 1. 20. 이전 1 다음