동학 개발 운동

문제 출처 : www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 문제 해석 : 지민이는 이야기의 진실을 모르는 자리에서는 과장된 이야기를 하고 진실을 아는 사람이 있는 곳에서는 진실된 이야기를 한다. 이때 과장된 이야기를 할 수 있는 파티의 수를 구하는 문제이다. 문제 풀이 : 단순하게 진실을 아는 사람 수를 체크하면 순서관계가 얽히게 되면 정답을 도출할 수 없게 된다. 예를 들어 1번 파티 1, 2 2번 파티 2, 3 3번 파티 3, 4 4번 파티 4, 5 5번 파티 ..

문제 출처 : 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/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 문제 해석 : 좌표를 새롭게 부여하는 문제이다. 즉 자신이 몇번째 순서인지로 수를 바꾸는 것이다. 이때 중복되는 수가 있을 경우 같은 수를 가진다. 문제 풀이 : 중복을 제거하고 정렬한 다음 딕셔너리로 만들어서 해당 숫자를 매핑 해주면 된다. 따라서 파이썬에서 제공하는 set() 과 sorted(), dictionary 자료형을 활용하면 풀 수 있..

문제 출처 : 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/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 문제 해석 : 묶음을 찾는 문제이다. 즉 그래프 전체의 연결 상태가 주어졌을 때 연결 요소를 구하는 문제이다. 문제 풀이 : 모든 노드의 부모를 찾아 기록하고 그 부모의 갯수를 출력하면 이는 연결 요소를 찾는 것과 같은 작업이다. 풀이 코드 def find_parent(parent, x): if parent[x] != x: parent..

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