문제 주소: https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 문제 해석 문제 풀이 이 문제가 다익스트라 문제라는 것을 알았다면, 최소 경로를 지나갈 때 목적지 후보들 중에서 G H의 경로를 지나는 경우가 최소가 되는 목적지를 구해야 한다는 것을 알 수 있다. 이 조건을 해결하기 위해서 크게 두 가지 방법을 사용할 수 있다. 정석적인 방법과 애드혹스러운 기교를 통해 문제를 해결하는 방법이 존재한다. 내가 푼 방법은 후자의 방법이지만 먼저 정..
solved.ac Class 4레벨에 속한 문제이다. 문제 주소: https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 문제 해석 문제 풀이 먼저 주어진 입력을 잘 받도록 코드를 구현해야 한다. 임의의 두 점 사이의 거리 중 가장 긴 것을 구하기 위해서는 일반적으로 모든 노드를 dfs 탐색해야 한다. 하지만 이 경우 주어진 노드의 수가 10,000개 이므로 n^2의 시간복잡도에서 통과할 수 없다. 이러한 트리의 지름을 구하는 문제는 ..
solved.ac Class 4레벨에 속한 문제이다. 문제 주소: https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 문제 해석 확산과 공기청정기를 순서대로 작동하면 된다. 확산은 미세먼지가 존재하는 위치에 상하좌우로 5를 나눈 소수점을 제거한 값만큼 확산된다. 이때 확산할 공간이 없거나 확산 위치에 공기청정기가 존재한다면 확산할 수 없다. 확산이 되는 만큼 감소된다. (확산에서 미세먼지는 항상 보존된다.) 미세먼지의 양이 5미만이라면 확산되지 ..
solved.ac Class 4레벨에 속한 문제이다. 문제 주소: https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 문제 해석 문제 풀이 입력 범위가 1000 이기 때문에, lis 알고리즘이 아니라 2차원 dp를 사용해 가장 긴 증가하는 수열을 앞에서, 뒤집어서 두 번 구해주었다. 뒤집어서 구해준 값들을 다시 뒤집어 순서를 맞춰주고, 두 dp값들의 합이 최대가 되도록 하는 값 + 1이 답이 된다. 문제 코드 def solve(n, arr): # 앞에서 부터 가장 긴..
배solved.ac Class 4레벨에 속한 문제이다. 문제 주소: https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 해석 루트가 1인 트리의 연결 상태가 주어진다. 루트를 제외한 이 트리의 각 노드의 부모를 구하는 문제이다. 문제 풀이 root인 1을 시작으로 bfs 탐색을 통해 부모 노드를 구해주었다. 문제 코드 import sys from collections import deque input = sys.stdin.readline def solve(n, adj): # bfs를 통해 root부터 탐색..
solved.ac Class 4레벨에 속한 문제이다. 문제 주소: https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제 해석 1은 집, 2는 치킨집을 나타낸다. 치킨 거리는 집으로 부터 가장 가까운 치킨집 사이의 거리이며, 모든 집으로 부터 치킨 거리의 합이 도시의 치킨 거리가 된다. m개의 치킨집만 선택해 도시에 남겨야 한다. 이때 도시의 치킨 거리가 최소가 되는 값을 구하는 문제이다. 문제 풀이 먼저 집과 치킨집의 좌표..
solved.ac Class 4레벨에 속한 문제이다. 문제 주소: https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 문제 해석 스티커를 떼어내 최대의 점수를 얻어야 한다. 이때 스티커를 떼면 상하좌우에 존재하는 스티커가 함께 떼어지고, 함께 떼어진 스티커는 점수를 획득하지 못한다. 얻을 수 있는 최대의 점수를 구하는 문제이다. 문제 풀이 dp를 이용해서 해결해 주었다. j열의 새로운 스티커를 선택할 때 j - 1열의 반대 행의 점수 j..
solved.ac Class 4레벨에 속한 문제이다. 문제 주소: https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 문제 해석 이진 트리를 구현해서 전위, 중위, 후위 순회의 결과를 출력하는 문제이다. 문제 풀이 친절하게 문제에서 전위, 중위, 후위 순회의 결과와 알고리즘을 설명해 주었다. class Node: def __init__(self, name): self.name = name self.left = None self.right..
solved.ac Class 3레벨에 속한 문제이다. 문제 주소: https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 문제 해석 주어진 문제의 설명과 같다. 문제 풀이 분할 정복 문제이다. ㅁㅁ 1 2 ㅁㅁ 3 4 위 모양과 순서를 기준으로 숫자가 차례대로 증가하기 때문에 구하려는 행과 열이 속한 영역을 분할 정복을 통해 영역의 크기가 2 * 2가 될 때 까지 찾아준다. 찾아주는 과정에서 number += 4 ** (size - 1) 만큼..
solved.ac Class 3레벨에 속한 문제이다. 문제 주소: https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 문제 해석 고장난 리모컨 버튼이 주어진다. 누를 수 있는 버튼은 +, - 버튼과 고장나지 않은 숫자 버튼이다. 해당 리모컨을 주어진 채널에 최소로 도달하는 횟수를 구하는 문제이다. 문제 풀이 이동할 수 있는 채널은 500,000 이지만 숫자를 누르고, (+, -) 버튼을 통해 이동하는 경우의 채널은 1,000,000..
