1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 문제 읽기 유니온 파인드를 모른 채로 이 문제를 처음 봤다면 인접 리스트 만들어서 DFS로 그래프 탐색을 했을지도 모른다.. 하지만 지금은 유니온 파인드를 알기 때문에, 훨씬 단순하게 생각할 수 있었다. 유니온 파인드의 개념이 궁금하면 다음 글을 참고하고 오면 좋다. 분리 집합, Disjoint Set : Union-Find 분리 집합, Disjoint Set 💡 분리 집합, Disjoint Set = 서로소 집합 분리 집합이란 이미 존재하는 집합 U에 대해, ..

1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 문제 읽기 이전이었으면 이게 뭐지.. 하면서 끙끙댔을 테지만, 어제 유니온 파인드를 공부했기 때문인지, 읽자마자 이건 그냥 유니온 파인드라는 생각이 들었다. 유니온 파인드에 대해 개념을 알고 싶으면 우선 이 포스팅을 먼저 보고 오길 추천한다. 분리 집합, Disjoint Set : Union-Find 분리 집합, Disjoint Set 💡 분리 집합, Disjoint Set = 서로소 집합 분리 집합이란 이미 존재하는 집합 ..

분리 집합, Disjoint Set 💡 분리 집합, Disjoint Set = 서로소 집합 분리 집합이란 이미 존재하는 집합 U에 대해, 겹치는 부분이 발생하지 않도록 모든 원소들을 포함하여 분리한 부분 집합을 말한다. 즉, 전체 집합 U에 대해, U의 분리 집합 A, B는 다음과 같은 조건을 만족 한다. A, B는 U의 부분 집합이다. A, B는 공통 원소를 가지지 않는다. A, B의 합집합이 곧 전체 집합 U이다. (= A, B에 속하지 않는 U의 원소가 없어야 한다) 분리 집합의 활용 이런 분리 집합은 다음과 같은 경우에 적용된다. 가상의 프로그램에서 이러한 규칙이 있다고 하자. “A와 B가 친구 관계이고, 내가 A와 친구를 맺으면, 자동으로 나와 B는 친구 관계가 된다” 그리고 다음 사진은 이 프..

1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제 읽기 맨 처음에 문제를 읽자마자 트리 형태가 먼저 생각났다. 하나씩 숫자를 넣으면서 중간 값을 찾아낼 수 있지 않을까 하는 생각. 하지만 자료구조를 본 게 시간이 좀 지나서 어떤 식으로 구현해야 할 지는 감이 잘 잡히지 않았다. 그 다음 생각난 접근은 정렬이다. 하나씩 값이 들어오고, 값이 몇 개 들어왔는지 알 수 있고.. 그렇다면 삽입 정렬을 하면 되지 않을까 싶었다. 하지만 삽입 정렬의 시간복잡도는 최악의 경우 N^2이기 때문에(문제에서..