동학 개발 운동

문제 출처 : www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 문제 해석 : N개의 보석과 K개의 가방이 있다 이때 가방에는 1개의 보석만 넣을 수 있고 무게 제한이 있다. 또한 보석에는 무게와 가치가 매겨져 있다. 가장 높은 가치의 보석을 훔치는 경우의 가치의 합을 구하라 문제 풀이 : 정렬과 heapq를 활용해서 풀 수 있다. 배낭을 오름차순으로 정렬하고 보석은 무게를 기준으로 오름차순으로 정렬..

문제 출처 : 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/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 문제 해석 : 원하는 건물을 지을 수 있을 때까지 얼마나 시간이 걸리는지 구하는 문제이다. 문제 풀이 : 위상 정렬과 DP를 활용해서 문제를 풀이 할 수 있다. - 진입 차수를 이용해서 위상 정렬로 차례로 건물을 건설한다. - 진입 차수가 0이 되어 추가될때 DP 테이블에 현재 자신의 테이블과 이전과 지금을 합한것을 비교하여 큰 것을 저장한다. 풀이 코드 from collections imp..

문제 출처 : www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제 해석 : 두 팀으로 나누어서 능력치 차이를 최소로 하게 팀을 구성하는 문제이다. 문제 풀이 : 처음에는 itertools의 permutations를 이용해서 풀려고 했지만 메모리초과가 나와서 직접 팀을 구성하고 이를 계산해서 풀었다. 풀이에 필요한 기능은 1. 팀을 구성하는 함수 2. 팀의 능력치 차이를 계산하는 함수 가 있으며 이를 활용해서 바로 풀어 낼 수 있다. 풀이 코드 def cal_diff(team1,..

문제 출처 : www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 문제 해석 : 로봇 청소기가 특정한 조건을 만족하면서 청소를 진행한다. 이때 청소가 완료된 횟수를 출력하는 문제이다. 문제 풀이 : 주어진 문제의 조건을 하나씩 차근차근 따져가면서 풀면 해결할 수 있다. 풀이 코드 from collections import deque dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] def solution(): global arr result ..

문제 출처 : www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 문제 해석 : 공기청정기는 여러 규칙에 따라서 움직인다. 이를 수행했을 때 T초 후의 총 먼지의 양을 구하라 문제 풀이 : 주어진 요구사항을 차근차근 하나씩 확인해 가면서 구현하면 풀 수 있다. 풀이 코드 dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] def check_all(): temp = 0 for i in range(R): temp += sum(arr[i]) retu..

문제 출처 : www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 문제 해석 : A에서 B로 만드는데 2가지 방법을 사용할 수 있다. 1. 수를 2배로 만든다. 2. 수의 끝에 1을 붙인다. 이때 최소 횟수로 B를 만드는 것에 +1 한 수를 반환해라, 만들 수 없다면 -1을 반환해라. 문제 풀이 : BFS로 가능한 모든 경우의 수를 체크하면 되는 문제이다. 풀이 코드 from collections import deque def find_answer(A): visited = [] Q = deque() Q.append([0,A]) visited.append(A) while Q: count,..

문제 출처 : www.acmicpc.net/problem/15666 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 해석 : N개의 자연수 중에서 M개를 선택하여 수열을 생성한다. 이때 N에는 중복된 수가 들어 있을 수 있으며 수열은 서로 중복되서는 안되고, 수열 속에서 같은 수가 중복 되어도 된다. 문제 풀이 : 재귀적으로 답을 만들어가고 이미 출력된 적이 있다면 이를 제외 해주면 된다. 풀이 코드 def make_answer(start, count, arr2): global candidate if ..

문제 출처 : www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 해석 : N개의 수 중에서 M개를 고르는데 중복 없이 결과를 출력해야한다. 이때 N은 중복된 수가 들어있다. 문제 풀이 : permutations과 set을 활용해서 문제를 풀 수 있다. 풀이 코드 from itertools import permutations N, M = map(int, input().split()) num_list = list(map(int, input().split()..

문제 출처 : www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 문제 해석 : N개의 수 중에서 M개의 수를 고른다. 이때 자기 자신도 고를 수 있지만 중복은 없다. 또한 비내림차순이다. 문제 풀이 : 재귀적으로 풀어가면서 시작 index를 주면 된다. 풀이 코드 def make_answer(start, count, arr2): if count >= M: for element in arr2: print(element, end = " ") print()..