동학 개발 운동

문제 출처 : www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 문제 해석 : 각 건물을 건설하기 위해서는 선행되어야 하는 건물이 있다. 이를 고려하였을 때 각 건물이 지어지는데 필요한 최소 시간을 출력하라 문제 풀이 : 위상정렬과 DP를 활용하면 풀 수 있다. 풀이 코드 from collections import defaultdict, deque N = int(input()) answer = [0] * (N+1) cost = [0] * (N+1) ..

문제 출처 : 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..

신장 트리란 ? -> 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 생성되지 않는 부분 그래프 -> 즉 모든 노드들을 연결 하면서도 사이클이 생성되지 않는 그래프를 의미한다. -> 이는 다리를 놓으면서 최소한으로 모든 섬들을 연결하는 문제로 생각할 수 있다. : 따라서 최소 신장 트리는 N개의 정점을 (N-1)개의 간선으로 연결하게 된다. MST의 구현 방법 1. Kruskal MST Algorithm - Greedy Method/Algorithm을 이용하여 그래프의 모든 정점을 최소비용으로 연결하는 알고리즘이다. - 각 사이클에서 최소 비용의 간선을 택하는데 사이클을 이루지 않도록 한다. - 간선을 선택하면서 이루어지는 알고리즘이다. - 가장 작은 비용을 가진 간선들만 선택하기 때문에 Gre..

문제 출처 : www.acmicpc.net/problem/1007 1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net 문제 해석 : N개의 좌표평면 상의 점이 주어졌을 때 N//2개의 벡터를 생성하고 이를 합한 길이의 최솟값을 구하라 문제 풀이 : v1 = (x1-x2, y1-y2)이다. v2 = (x3-x4, y3-y4) 이다. 합벡터 v3 = v1-v2 = ( (x1-x2) - (x3-x4), (y1-y2) - (y3-y4) ) 이다. 즉 임의의 v3 = ( ( x1 + x3 ) - ( x2 + x4..

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

문제 출처 : leetcode.com/problems/jewels-and-stones/ Jewels and Stones - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 해석 : 내가 총 몇개의 보석을 가졌는지 출력하는 문제이다. 문제 풀이 : 딕셔너리 자료형을 활요해서 쉽게 풀이 할 수 있다. 풀이 코드 import collections class Solution: def numJewelsInStones(self, jewels: str, stones: s..

문제 출처 : leetcode.com/problems/design-circular-queue/ Design Circular Queue - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 해석 : 원형 큐 클래스를 작성하는 문제이다. 문제 풀이 : 나머지 연산을 이용해서 두개의 인덱스를 이용해서 구현하면 된다. 풀이 코드 class MyCircularQueue: def __init__(self, k: int): self.Q = [-1] * k self.fron..

문제 출처 : leetcode.com/problems/implement-queue-using-stacks/ Implement Queue using Stacks - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 해석 : Stack을 이용해서 Queue를 구현 하는 문제이다. 문제 풀이 : 다른 기능들은 쉽게 구현 할 수 있지만 pop을 수행 할때는 순서에 유의해서 temp 배열에 저장하고 원하는 값을 꺼낸뒤에 다시 원상태로 복귀 시켜줘야 한다. 풀이 코드 c..

문제 출처 : leetcode.com/problems/implement-stack-using-queues/ Implement Stack using Queues - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 해석 : 큐를 이용해서 스택을 구현하는 문제이다. 문제 풀이 : 큐는 삽입은 뒤에서 삭제는 앞에서 하기 때문에 여기서 신경쓸 것은 Pop 연산이다. 스택은 삭제 또한 뒤에서 하기 때문에 삭제 대상 직전까지 다른 배열에 임시로 저장하고 원하는 값을 제거..