허비의 기술블로그

그래프의 정점의 개수(N), 간선의 개수(M), 연결된 간선의 정보가 입력으로 주어진다. 이때 주어진 그래프에서 Connected Component(연결된 요소의 개수)를 구하는 문제다. 다음과 같은 그래프가 주어진다면 Connected Component의 개수는 3개이다. 시간 복잡도: O(MN) 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 풀이 과정 BFS나 DFS와 같은 그래프 탐색 방법을 활용하면 연결된 모든 노드(정점)를 방문할 수 있다..

길이 N이 주어질 때, 1이 2개 이상 연속해서 나오지 않으며, 길이가 N인 2진수의 개수를 구하는 문제다. 단 2진수는 1로 시작해야 한다. 시간 복잡도 : O(N) 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 풀이 방법 2진수의 길이가 1씩 늘어난다고 하면, 바로 직전에 만들었던 이친수에 0을 붙여서 이친수를 만들 수 있고, 전전에 만들었던 이친수에 01을 붙여 이친수를 새로 만들 수 있다. 이렇게 만들면 이친수가 중복 없이 생성된다. N 이친수 1 1 2 10 3 101,100 4 1001..

N의 크기가 주어질 때 2 * N 사이즈의 직사각형을 (2 X 1), (1 X 2), (2 X 2)의 직사각형으로 채우는 경우의 수를 구하는 문제다. 경우의 수를 10007로 나눈 나머지를 정답으로 출력한다. 시간 복잡도: O(N) 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 풀이 방법 N의 크기가 커질 때마다 채울 수 있는 경우의 수는 일정한 규칙을 가지고 증가한다. N이 1일 때부터 차례대로 확인해보자 N = 1일 때 N이 1일 때는 1X2 직사각형 한 개로 이루어진 경우밖에 없으므로 1이다. N=2일 때 N이 2일 때는 (1X2 사..

-10,000 ~ 10,000 사이의 정수 N개가 입력으로 들어오면, 숫자 입력이 차례로 들어올 때마다 중앙값을 출력하는 문제다. ex) input : 3 6 8 4 5 6 2 output : 3 3 6 4 5 5 5 입력이 짝수개가 들어왔을 때는 중간의 두 수중 작은 수를 출력한다. 시간 복잡도: O(NlogN) 풀이 방법 출력해야 하는 값은 중앙값이다. 제일 간단히 중앙값을 찾는 방법은, 입력이 들어올 때마다 들어온 입력값들을 정렬한 후에 가운데 값을 출력하는 것이지만 그러면 매 입력마다 O(NlogN)의 시간이 걸리고 총 O(N^2 * logN)의 시간이 걸려서 시간 초과가 발생한다. Heap 자료구조를 이용하면 삽입, 삭제를 O(logN) 시간에 할 수 있으며 구현 방법에 따라 MinHeap, M..

입력으로 체스판의 크기 M * M, 나이트의 시작 위치, 이동하고자 하는 위치가 주어진다. 이때 나이트가 목적지까지 가는데 걸리는 최소 이동 횟수를 구하는 문제다. 시간 복잡도: O(M^2) 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 풀이 방법 나이트가 한번 이동할 때 갈 수 있는 위치는 다음과 같다. 총 8위치로 이동할 수 있으며 그때의 x, y좌표 변화는 위의 식과 같다. (체스판의 숫자는 dx, dy배열에서의 index) 체스판의 각 위치에 대응하는 M * M 크기의 2차원 배열을 선언하고, 값으로 ..

문제 설명 N개의 도시가 일직선으로 연결돼있고, 각 도시에는 주유소가 있다. 연결된 도시의 거리 배열, 각 도시의 기름값 정보 배열이 들어올 때 최소의 비용으로 첫 번째 도시에서 마지막 도시까지 가는 비용을 구하는 문제다. (단, 기름을 실을 수 있는 양은 무한대이며, 기름값과 거리는 10억 이하의 자연수이다. 또한 도시의 개수는 최대 10만 개다.) 시간 복잡도 : O(N) 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 풀이 방법 도시를 차례로 지나가며 소모한 기름 값을 계산할 때, 각각 현재..

N개의 회의 사용시간(시작시간, 끝나는 시간)이 들어올 때 회의를 할 수 있는 가장 많은 경우의 수를 찾아서 그 값을 반환하는 문제다. N은 최대 10만이며, (시작시간, 끝나는 시간)은 INT최댓값으로 들어온다. 이때 시작시간, 끝나는 시간이 같을 수 있으며, 회의가 끝나는 시간에 다른 회의가 시작될 수 있다. (일반적 논리와는 맞지 않음에 주의한다.) 시간복잡도: O(NlogN) 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 풀이 방법 가능한 많은 회의를 만들어야 하므로, 우선 입력값을 차례대로 비교해보기 위해 들어온 (회의 시작시간, 회의 끝나는 시간)을 오름차순으로 정렬한 배열을 생성한다. 이렇게 하면 시작시간이 빠..

N * N 크기의 체스판이 있을 때, N개의 퀸을 놓을 수 있는 경우의 수를 구하는 문제다. N개의 퀸은 서로 공격할 수 없어야 한다. 시간 복잡도: O(N!) (??) (각 행마다 1개의 Queen을 놓을 수 있으며 첫 행에 놓을 수 있는 자리는 N개이고 행이 커질수록 위의 행에서 1~3개만큼 가능한 자리가 줄어든다. 이를 수식으로 어떻게 나타내야 할지 모르겠어서 최소 1개는 줄어들기 때문에 N!이라고 썼다.) 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이과정 체스판에서 Queen은 위, 아래, 대각선 이동이 가능하..

강이 위에서 아래로 흐르고 서쪽, 동쪽 땅으로 구분돼있다. 서쪽과 동쪽에는 각각 다리를 놓을 수 있는 포인트들이 N, M개 있다. (M >= N) 이때 서쪽에서 동쪽으로 다리를 놓으려고 할 때 다리를 놓을 수 있는 최대 경우의 수를 찾는 문제다. 시간 복잡도: O(MN) 풀이과정 강의 서쪽 땅 N개의 포인트에서 동쪽 땅 M개의 포인트를 연결하고자 하며, N은 M보다 작거나 같다. 이때 강의 동쪽에 연결할 M개의 포인트 중에 N개를 선택하면 서쪽에서 이어질 다리가 교차하면 안 되므로 다리를 짓는 경우가 1개 나온다. 즉 M개의 포인트에서 N개를 선택하는 경우의 수가 이 문제의 정답이다. 주의할점 조합은 수가 커질수록 결괏값이 커지므로 수의 범위를 조심해야 한다. 문제에서는 M, N의 최댓값이 30이기 때문..

두 터렛의 좌표와 목표물과 각 터렛 사이의 거리가 주어질 때, 존재 가능한 목표물의 위치 개수를 반환하는 문제이다. 즉 두 원 사이의 교차점을 의미하므로 나올 수 있는 값은 0, 1, 2, 무한대이다. 시간 복잡도: O(1) 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 풀이과정 두 원 중심 사이의 거리와, 두 원의 크기(반지름)를 비교하며 경우를 나눈다. distance => 두 중심 사이의 거리 r1 => 한 원의 크기 r2 => 다른 원의 크기 1. 두 원이 같은 경우 존재 가능한 목표물의 개수가 무한대이다. 2. 두 원이 외접하는 경우 교점이 1개이다...