동학 개발 운동

문제 출처 : www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 문제 해석 : 숨바꼭질을 하는데 이동 가능한 경우는 X-1, X+1, X*2이다. 이때 가장 빠르게 K로 이동할 수 있는 경우의 수와 그 시간을 구하는 문제이다. 문제 풀이 : BFS를 통해서 모든 경우를 조사하면서 횟수를 검사하면 풀 수 있다. 풀이 코드 from collections import deque def search(N): visited = [[-..

문제 출처 : www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 문제 해석 : N개의 수 중에서 M개의 수를 골라 수열을 구성하는 문제이다. 문제 풀이 : permutation을 이용하면 쉽게 풀 수 있다. 단 sorting을 오름차순으로 한번해야 답을 구할 수 있다. 풀이 코드 import sys from itertools import permutations input = sys.stdin.readline N, M = map(int, input()...

문제 출처 : www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 문제 해석 : 출발점에서 목적지까지 가는 경로와 비용이 주어 졌을때 최소 비용과 거치는 정점수, 정점을 출력하는 문제이다. 문제 풀이 : 다익스트라 알고리즘을 통해서 최소비용을 구하고, 중간에 경로를 기록하면 된다. 풀이 코드 def dijkstra(s): distance = [INF] * (N+1) distance_path = [[] for _ in range(N..

문제 출처 : www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 해석 : 1번을 루트로 하는 트리가 있다. 이때 순서에 상관없이 노드의 연결 관계가 주어질 때 각 노드의 부모를 구하여 출력하라 문제 풀이 : 모든 트리를 입력 받으면서 트리를 구성하고 1번 루트 부터 차례로 밑으로 내려가면서 부모를 체크해 주면 된다. 풀이 코드 import sys input = sys.stdin.readline N = int(input()) parent = [0] * (N+1) visited = [0] * (N+1) tree = {} ..

문제 출처 : www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제 해석 : 주어진 x1,y1 ~ x2,y2 사이에 존재하는 수의 합을 구하는 문제이다. 문제 풀이 : 일반적으로 합을 하나 하나씩 더해서 구했을 경우 시간 초과가 나기 때문에 DP를 통해서 문제를 풀어줘야한다. x,y 까지의 합을 구한 테이블을 이용해서 매 결과를 +,- 연산을 이용해서 구하면 풀 수 있다. 풀이 코드 import sys input =..

문제 출처 : www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 해석 : LCS는 공통된 가장 긴 공통 문자열을 찾는 알고리즘이다. 이 문제에서는 실제 LCS 문자열을 출력하는 대신 길이를 구하면 된다. 문제 풀이 : DP를 활용해서 가능한 경우를 모두 메모하면서 계산한다. 풀이 코드 S1 = list(input()) S2 = list(input()) S1_length = len(S1) S2_length = l..

문제 출처 : www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 해석 : 행렬 제곱을 수행하는 문제이다. 행렬 A와 제곱하는 횟수 B가 주어지면 행렬의 곱을 B번 반복하면 된다. 문제 풀이 : 100,000,000,000까지 제곱을 수행하기 때문에 일반적인 행렬의 제곱으로는 (N^3)의 곱셈 * 100,000,000,000을 수행하면 시간 초과나 난다. 따라서 A^16 같은 경우 A^2^2^2^2으로 연산해야한다. 이렇게 되면 밑이 2인 로그만큼으로 연산 횟수가 줄기 ..

문제 출처 : www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 문제 해석 : 폭발 문자열과 일치하는 문자열을 제거하고 나머지를 이어 붙인다. 이때 다시 폭발 문자열이 생성될 수 있으며 이 또한 같은 방식으로 제거를 반복한다. 마지막까지 수행했을 때 길이가 0이라면 FRULA를 출력하고 아니라면 그 문자열을 출력하는 문제이다. 문제 풀이 : 파이썬에서 제공하는 replace를 사용하면 시간초과가 나온다. 따라서 인덱스와 스택을 활용하여 직접 제거..

문제 출처 : www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 해석 : 1~N 까지의 수 중에서 중복을 허용하면서 M개의 수를 고를 수 있는 모든 경우를 출력하는 문제이다. 단 비내림차순 이여야 한다. 문제 풀이 : 재귀적으로 모든 경우를 체크하면서 배열을 만들고 M개가 되었을 때 출력한다. 풀이 코드 def make_answer(count, arr): if count > M: for element in arr: print(element, end=" ..

문제 출처 : www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 해석 : 1~N의 수 중 중복없이 오름차순으로 M개의 수를 선택하는 경우를 모두 보이는 문제이다. 문제 풀이 : Python itertools - combinations에서 제공하는 것과 동일한 기능이기에 이를 활용한다. 가능한 다른 풀이 : 원리를 이용해서 직접 구현 할 수 있다. 이때는 for문을 통해서 오름차순인지 확인하고 중복된지를 확인하면서 만들면 된다. 풀이 코드 from ite..