분리 집합, 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이기 때문에(문제에서..

2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 읽기 우선 처음에 딱 읽었을 때는 완탐 아니고서는 어떻게 풀지?? 싶었다. 중복을 허용하고, 순서가 바뀐 경우를 다르게 센다고 해서 중복 순열인가? 싶었지만 질문 게시판 살짝 보니 중복 조합이라고 하는데.. 잘 모르겠더라 그래서 일단은 예제를 가지고 고등학교 확통 시간을 떠올리며 직접 경우의 수를 세어봤다. K = 2일 때는 음 그렇구나 했는데 K = 4인 걸 다 써보고 나니까 뭔가 규칙이 보였다..!! 물론 어떻게 나올 지는 모르지만, K = 4에는 K = 1인 것, K = 2인 것, K = 3인 것도 다 포함이 되어 있었다. 그래서 뭔가 DP적으로 접근한다면,, N이랑 K를 냅색..

1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 문제 읽기 처음에 봤을 때는 어제 풀었던 점프랑 뭔가 비슷하다는 느낌이 들었다. BOJ_S1_1890_점프 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수 rue-mi.tistory.com 하지만 점프의 경우에는 단순히 오른쪽, 아래쪽 방향으로만 이동이 가능했지만, 이 문제의 경우에는 상하좌우 모든 ..

1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 문제 읽기 처음에 딱 문제를 읽었을 때는 .. DP인 걸 인지하고 있었기 때문에 이중 for문을 쓰면서 채워나갈 수 있을 것이라 생각했다. 하지만 계속 읽다 보니 (0, 0)에서 시작하여 (N-1, N-1) 지점까지 DFS 또는 BFS를 써도 되지 않을까 하는 생각이 들었다. 일단 시뮬레이션을 해봤을 때 DFS가 더 맞는 것 같았지만, 문제의 조건에서도 볼 수 있듯이 판의 크기가 최대 100이다. DFS 쓰면 2^100…. 무조건 시간초과이다. 그래도..

2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 문제 읽기 우선 문제 자체는 매우 짧고 예전에 싸피 수업 때 본 듯한 문제였다. 이런 문제는 직접!! 그려봐야 규칙이 보인다. 문제 풀기 우선 3xN의 크기의 판에 2x1, 1x2 크기의 타일을 남김없이 붙여 채워야 한다. 나는 규칙을 찾기 위해 N의 범위만큼 다 그려보았다. (N : 1~30) N = 0, 1 어차피 DP 배열은 0도 있을 거니까 그냥 그렸다 N이 0, 1일 때는 내가 가진 타일로 채울 수 없었다. N = 2 N = 2일 때는 위와 같은 방식으로 채울 수 있었다. 문제에서 주어진 답처럼 3가지 경우가 나왔다. N = 3 N = 3일 때를 그려보니 확실히 ..