동학 개발 운동

문제 출처 : www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 해석 : RGB 거리를 구하는 문제로 각각 RGB마다 주어진 값이 있다. 이 값을 최소로 만들어야 한다. 이때 자신의 바로 앞에서 선택된 색은 고를 수 없다. 문제 풀이 : DP로 문제를 해결 할 수 있다. -> 각 3가지 경우 모두를 매번 자신의 색을 제외한 최소값으로 고르면서 진행하면 마지막에 최소를 구할 수 있다. 풀이 코드 import sys input = sys..

문제 출처 : www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 문제 해석 : 모든 수는 4개 이하의 제곱 수로 나타 낼 수 있다. 이때 주어진 N은 최소 몇개의 제곱수로 나타낼 수 있는가? 문제 풀이 : DP 문제로 풀이 할 수 있다. 자신의 수에서 그보다 작은 수의 제곱수를 뺀 것의 최소를 구하고 거기에 한개를 더해주면 된다. 가능한 다른 풀이 : 브루트포스로 가능한 모든 경우를 풀어 볼 수도 있다. 풀이 코드 N = i..

문제 출처 : www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 문제 해석 : 저장한 비밀번호를 찾아 이를 출력하는 문제이다. 문제 풀이 : 간단한 딕셔너리 활용 문제이다. 저장을 딕셔너리로 하고 사이트를 키값으로 지정해 주면 된다. 풀이 코드 import sys input = sys.stdin.readline N, M = map(int, input().split()) add = {} for _ in range(N): site, ..

문제 출처 : www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 문제 해석 : 1X2, 2X1, 2X2 타일을 사용해서 2XN의 타일을 모두 채우는 방법의 경우의 수를 구하는 문제이다. 문제 풀이 : 전형적인 DP 문제로 dp[i] = (dp[i-2]*2) + dp[i-1] 의 점화식을 사용해서 풀 수 있다. 풀이 코드 N = int(input()) dp = [0,1,3,5] for i in range(4,N+1): dp.append((dp[i-2]*2) + dp[i-1] ) print(d..

문제 출처 : www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 해석 : 2X1 짜리 타일로 2XN의 타일을 채울 수 있는 방법의 수를 구하는 문제이다. 문제 풀이 : 이 문제는 DP로 풀 수 있다. 모든 경우는 앞에 있는 경우에 한쪽 끝에 타일이 붙은 것으로 생각할 수 있다. 이는 dp[i] = dp[i-1] + dp[i-2]라는 점화식으로 만들 수 있고 이를 그대로 활용하면 문제를 풀 수 있다. 풀이 코드 N = int(input()) dp = [0,1,2] for i i..

문제 출처 : www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 문제 해석 : 주어진 조건에 따라 집합 연산을 수행하는 프로그램을 작성하는 문제이다. 문제 풀이 : 까다로운 조건이 없어 주어진 제시문대로 코드를 작성하면 풀 수 있다. -> Pypy3로 컴파일 하면 메모리 초과가 난다. 이는 pypy3가 내부적으로 더 메모리를 많이 사용하기 때문이 것 같다. 풀이 코드 import sys input = sys.stdin.readline M = int(input()) S = set() for _ i..

문제 출처 : www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 해석 : 이동 가능한지 여부를 경로를 토대로 구하는 문제이다. 몇번을 어디를 거쳐가는 지는 생각하지 않고 어떤 방식으로든 갈 수 있으면 1 없으면 0을 출력하면 된다. 문제 풀이 : 플루이드 - 워셜 알고리즘을 통해서 해결 가능하다. 플루이드 - 워셜 알고리즘은 거쳐가는 모든 경우를 고려하여 가능한지 검사 할 수 있다. 풀이 코드 import sys input = sys.stdin.readline N = int(input()) vis..

문제 출처 : www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 해석 : ATM에 줄을 서있는 모든 사람이 업무를 마치는 순간까지 걸리는 시간이 최소가 되게 하는 문제이다. 문제 풀이 : 앞에서의 대기 시간이 줄어들면 뒤의 사람의 대기시간이 줄어드는 것이 보장되기 때문에 항상 적은 숫자가 앞으로 갈 수록 시간이 적게 걸리는 것이 보장된다. -> Ai = A1 + A2 + ...... + Ai-1 + Ai 이기 때문이다. 풀이 코드 N = int(input()) P = list(map(..

문제 출처 : www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제 해석 : 최소힙을 절댓값을 기준으로 생성하고 이를 구현하는 문제이다. 문제 풀이 : 파이썬에서 기본으로 제공하는 heapq를 이용하는데 이때 push, pop에 단순한 숫자말고 [절댓값, 부호]로 삽입하고 출력을 절댓값 * 부호로 함으로 해결할 수 있다. 가능한 다른 풀이 : 직접 힙을 구현하여 풀이 할 수 있다. 풀이 코드 import heapq import sys i..

문제 출처 : www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제 해석 : 적록 색약인 사람과 아닌 사람이 보는 그림에서 구역 수의 차이를 구하는 문제이다. 문제 풀이 : 전형적인 BFS의 구역 구하기 문제에서 적색과 녹색을 구별하지 못하는 부분이 추가된 문제이다. 이 부분을 새로운 배열을 선언함으로 중복 코딩 없이 해결 할 수 있다. 풀이 코드 from collections import deque def normal(a, b, Arr): Q = d..