이번에 풀 문제는 그래프 수정 문제이다. 위상 정렬을 활용하는 문제인데, 일단 문제를 보고 가자. - N개의 정점으로 구성된 그래프가 입력으로 주어진다. 이때 노드의 번호는 1보다 크거나 같고 N보다 작거나 같다. - 만약 노드 U에서 노드 V로 연결되는 간선이 존재한다면, 노드 V의 번호는 노드 U의 번호보다 커야 한다. - 위의 조건을 만족하도록 노드의 번호를 바꾸고, 원래의 1번 노드부터 N번 노드까지 각각 바뀐 노드의 번호를 출력해야 한다. 위의 말만 봐서는 문제에서 원하는 것이 무엇인지 정확히 감이 오지 않을 수 있다. 다음 입력값을 그림으로 나타내서 이해해 보자! n = 5 node1 : 00110 node2 : 00001 node3 : 00000 node4 : 01000 node5 : 000..
이번에 풀어볼 문제는 빙산 문제이다. 시간이 지나면서 입력으로 주어진 빙산이 녹아가는데, 빙산이 처음으로 분리되는 시간을 구하는 문제이다. 문제의 조건은 아래와 같다. 빙산이 상하좌우로 맞닿아 있는 바닷물의 칸수만큼 녹는다. 빙산이 차지하는 칸의 개수는 최대 10,000개이다. 배열의 첫 번째 행과 마지막 행, 첫 번째 열과 마지막 열에는 빙산이 존재하지 않는다. 빙산의 높이는 최대 10이다. 기본적인 탐색 문제이다. 먼저 바닷물과 맞닿아 있는 빙산들을 녹이고 나서, 아직 녹지 않은 빙산을 기준으로 탐색을 진행하여 연결된 빙산들을 모두 방문처리 해주는 방식이다. 이렇게 탐색이 한 번 진행된 이후에도 아직 방문하지 않은 빙산이 존재한다면, 빙산이 둘 이상으로 갈라지게 된 것이므로 탐색을 종료한다. 다만 이..
https://www.acmicpc.net/problem/21606 21606번: 아침 산책 1번 정점에서 시작하고 3, 4번 정점에서 끝나는 경로, 3번 정점에서 시작하고 1, 4번 정점에서 끝나는 경로, 4번 정점에서 시작하고 1, 3, 5번 정점에서 끝나는 경로, 5번 정점에서 시작하고 4번 정점 www.acmicpc.net 이번에 풀 문제는 아침 산책이라는 문제다. 이전 문제들과는 달리 서브태스크가 있고 각 태스크마다 배점이 부여되어 있는데, 이를 통해 내 풀이가 어떤 조건을 만족하지 못하는지 알 수 있다. 일단 본격적으로 풀이를 하기에 앞서 문제 요구사항을 짚고 넘어가자! 문제에서 장소를 노드로 표현하였으며, 실내인 노드는 1, 실외인 노드는 0으로 표현하였다. 문제에서 구하고자 하는 것은 실내..
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 이번 문제는 히스토그램에서 가장 큰 직사각형 문제이다. 문제에서 주어진 히스토그램에서 가장 넓이가 넓은 직사각형을 찾는 문제인데, 먼저 완전 탐색으로 푸는 방법을 생각해 보자. 이 문제를 완전 탐색으로 풀기 위해서는 어떤 한 블록을 기준으로 잡았을 때, 그 블록의 높이로 만들 수 있는 직사각형의 넓이를 찾아야 한다. 예를 들어 위의 예시에서..
