동학 개발 운동

문제 출처 : www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 문제 해석 : 홍수가 일어나고 있고, 고슴도치는 D를 향해서 물을 피해 가야합니다. 이때의 최소 시간을 구하는 문제입니다. 단 도달할 수 없을 경우 실패 문자를 출력합니다. 문제 풀이 : 간단한 BFS 알고리즘 통해서 풀 수 있습니다. 물의 이동과 고슴도치의 이동을 유심히 살펴 순서를 정의해주면서 탐색하면 됩니다. 풀이 시간 (기록용) : 30분 풀이 코드 import heapq dx = [0, 0, 1, -..

문제 출처 : www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다 www.acmicpc.net 문제 해석 : 두 배열에 있는 부분 배열의 합이 T를 만족하느 갯수를 찾는 문제이다. 문제 풀이 : 배열의 부분합을 저장한 딕셔너리 자료형을 탐색하여 갯수를 카운트하면 된다. 풀이 시간 (기록용) : 35분 12초 풀이 코드 import sys from collections import defaultdict input =..

문제 출처 : www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 문제 해석 : 마을을 두개로 분할 하려고 한다. 이때 마을 내부에 있는 길의 Cost가 최소가 되도록 마을을 분할 해야한다. 문제 풀이 : 최소 신장트리를 이용해서 마을 전체를 순회하는 도로를 구성한 다음 가장 큰 비용을 가진 길 하나를 제거하면 각자 모든 원소를 포함하는 2개의 마을 도로가 생성된다. 풀이 코드 import sys input = sys.std..

문제 출처 : www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 문제 해석 : 빙산은 물에 접한 면의 수만큼 녹는다. 이때 빙산이 2개의 덩어리로 분리 될 때 까지 걸리는 시간을 구하라. 문제 풀이 : 2개의 기능을 구현하면 풀 수 있다. 1. 빙산이 2개로 분리되었는지 검사하는 함수 2. 빙산이 1년이 지날 때마다 녹이는 함수 두 개의 함수 모두 BFS 알고리즘을 통해서 풀 수 있으며 풀이는 아래와 같다. 풀이 코드 import sys, copy fro..

문제 출처 : www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 문제 해석 : 최소 신장 트리를 구하고 그 비용의 최솟값을 출력하는 문제이다. 문제 풀이 : 크루스컬 알고리즘을 이용하여 풀이할 수 있다. 풀이 코드 def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] def ma..

문제 출처 : www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 문제 해석 : 여러 종류의 카메라를 90도씩 회전하면서 각자 다른 방향을 동시에 감시할 수 있다. 이때 사각지대가 최소가 되도록 하면 사각지대의 갯수를 구하는 문제이다. 문제 풀이 : 문제에서 요구하는 방법을 차근차근 따르면서 재귀, 스택 형식으로 코드를 작성하면 풀수 있다. 풀이 코드 dx = [-1,0,1,0] dy = [0,1,0,-1] def see(arr, i, j, dir_l..

문제 출처 : www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제 해석 : 토마토가 익는 것은 익은 토마토로 부터 전파된다. 최소 몇일이 되어야 모든 토마토가 익을 수 있을까? 에 대한 문제이다. 문제 풀이 : BFS를 통해서 문제를 풀 수 있다. 시간 초과에 유의하면서 차근차근 문제를 풀어 나가면 맞을 수 있다. 풀이 코드 from collections import deque import sys input = sys.stdin.readli..

문제 출처 : www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 문제 해석 : 듣지도, 보지도 못한 사람 이름을 출력하는 문제이다. 문제 풀이 : 두 집합에서 교집합을 찾는 문제로 파이썬의 intersection을 이용하면 풀 수 있다. 풀이 코드 import sys input = sys.stdin.readline N, M = map(int, input().split()) answer = [] hear = [] saw = [] for _ in range(N)..

문제 출처 :www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 문제 해석 : 사람들끼리 몇 다리를 거치면 알고 있는가를 구하는 문제입니다. 즉 그래프로 생각했을 때 이동할 수 있는 경로, 간선 들이 존재하는지 그리고 그 길이가 얼마인지를 계산하는 문제입니다. 문제 풀이 : 모든 사람들에 대해서 계산을 해야하므로 플로이드 - 워셜 알고리즘을 사용하면 풀 수 있습니다. 플로이드 - 워셜 알고리즘은 for k in r..

문제 출처 : www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 문제 해석 : 고장 리모컨을 가지고 최소 횟수로 원하는 채널로 이동하는 문제이다. 즉 가능한 모든 경우를 계산해서 가장 적게 버튼을 누를 수 있도록 설계해야한다. 문제 풀이 : 이 문제는 가능한 모든 경우를 고려해서 문제를 풀어야 하기 때문에 브루트포스 문제이다. 1. 만들 수 있는 모든 버튼을 만들면서 불가능한 경우를 체크한다. 2. 가능한 경우의 몇번 버튼을 눌러야하는지 계산한..