서로소 집합 먼저 중학생 때 배웠던 서로소를 떠올려보자. 어떤 두 수 A와 B가 있을 때, 두 수의 공약수가 1을 제외하고는 존재하지 않는 수를 서로소라고 부른다. 이를 고등학생 때 배운 집합의 개념을 빌려 그림으로 표현해 보자. 위의 그림은 24와 49의 약수를 벤다이어그램으로 표현한 것이다. 그림을 보면 둘의 공약수가 오직 1만 존재하는 것을 볼 수 있으며, 이런 형태의 수를 서로소라고 부른다. 이제 집합에서의 서로소가 무엇을 의미하는지 알아보자. 정수에서 서로소는 서로의 약수가 1을 제외하고 겹치지 않는 것을 의미했다. 이와 유사하게 서로소 집합은 두 집합의 원소가 겹치지 않는 것을 의미한다. 예를 들면 아래의 그림과 같은 집합을 서로소 집합이라 부를 수 있다. 위의 두 집합 A와 B를 보면, 두 ..
https://www.acmicpc.net/problem/21606 21606번: 아침 산책 1번 정점에서 시작하고 3, 4번 정점에서 끝나는 경로, 3번 정점에서 시작하고 1, 4번 정점에서 끝나는 경로, 4번 정점에서 시작하고 1, 3, 5번 정점에서 끝나는 경로, 5번 정점에서 시작하고 4번 정점 www.acmicpc.net 이번에 풀 문제는 아침 산책이라는 문제다. 이전 문제들과는 달리 서브태스크가 있고 각 태스크마다 배점이 부여되어 있는데, 이를 통해 내 풀이가 어떤 조건을 만족하지 못하는지 알 수 있다. 일단 본격적으로 풀이를 하기에 앞서 문제 요구사항을 짚고 넘어가자! 문제에서 장소를 노드로 표현하였으며, 실내인 노드는 1, 실외인 노드는 0으로 표현하였다. 문제에서 구하고자 하는 것은 실내..
그래프 탐색 알고리즘 그래프 탐색 문제는 시작 정점이 주어졌을 때, 시작 정점에서 간선을 타고 이동할 수 있는 모든 정점을 구하는 문제이다. 그래프 탐색 알고리즘에는 대표적으로 너비 우선 탐색(breadth-first-search;BFS)과 깊이 우선 탐색(depth-first-search;DFS) 방식이 있다. 깊이 우선 탐색(DFS) DFS의 경우 이름부터가 깊이 우선 탐색이기 때문에 노드의 깊이가 직접적으로 나타나지 않는 그래프보다는 트리에서 이해하기가 좋다. 만약 다음과 같은 트리의 1번 정점에서 DFS를 진행한다고 하자. 진행 과정은 아래의 그림과 같다. 먼저 현재 노드인 1번 노드를 방문 처리 한다. 이후 1번과 연결되어 있는 간선을 하나씩 조사하는데, 먼저 4번 노드와 연결된 간선을 조사한다..
https://www.acmicpc.net/problem/2261 2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 www.acmicpc.net 이번에 풀 문제는 가장 가까운 두 점이다. 2차원 평면상에 n개의 점이 주어졌을 때, 가장 가까운 두 점의 거리를 구하는 간단한 문제이다. 설명은 아주 간단하지만 풀이는 그렇지 않다! n의 범위가 최대 100,000 이기 때문에 완전 탐색으로 문제를 풀게 되면 시간 초과를 피하지 못한다... 나는 이 문제를 분할 정복 방식으로 풀었는데, 풀이가 이전에 풀었던 히스토..
https://www.acmicpc.net/problem/13334 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 이번에 풀 문제는 철로 문제이다. 문제에서 요구하는 사항은 다음과 같다. 집과 사무실을 통근하는 n명의 사람들이 있고, 각각의 사람들의 집의 좌표와 사무실의 좌표가 정보로 주어진다. 설치할 수 있는 철로의 길이 d가 주어진다. 이때 집과 사무실이 모두 철로의 경로에 포함되는 사람의 수를 최대로 하게끔 철로를 설치하는 프로그램을 작성하라. 문제 풀..
이번 문제는 원영역 문제이다. N개의 원의 중심 좌표와 원의 반지름이 주어졌을 때, N개의 원들로 나누어지는 영역의 개수를 구하는 문제이다. 처음에는 문제 조건이 너무 복잡해 보였지만, 원의 중심이 모두 일직선 위에 있고, 원들이 겹치는 경우는 없다는 제약이 있었기 때문에 생각보다 어렵지 않게 풀 수 있는 문제였다. 문제 풀이 방식은 철로 문제와 유사하니 풀어보고 오면 좋다! 이 문제 또한 $O(n^2)$의 완전 탐색으로 풀 수 있다. 물론 문제 입력값의 최대 크기가 300,000 이기 때문에 시간제한에 걸리지만... 그래도 문제의 정답을 찾기 위해 어떠한 조건을 만족해야 하는지 알아보기 위해 완전 탐색으로 푸는 경우를 생각해 보자. 먼저 원이 영역을 나누는 방식을 생각해봐야 할 것이다. 문제에서 영역이..
https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 이번 문제는 히스토그램에서 가장 큰 직사각형 문제이다. 문제에서 주어진 히스토그램에서 가장 넓이가 넓은 직사각형을 찾는 문제인데, 먼저 완전 탐색으로 푸는 방법을 생각해 보자. 이 문제를 완전 탐색으로 풀기 위해서는 어떤 한 블록을 기준으로 잡았을 때, 그 블록의 높이로 만들 수 있는 직사각형의 넓이를 찾아야 한다. 예를 들어 위의 예시에서..
