동학 개발 운동

문제 출처 : www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 해석 : 입력된 숫자를 1, 2, 3으로만 나타낼 수 있는 경우의 수를 구하는 문제이다. 문제 풀이 : DP 문제로 dp[i] = dp[i-3]+dp[i-2]+dp[i-1] 이라는 점화식을 통해서 문제를 풀 수 있다. 이와 같은 점화식이 답이 되는 이유는 다음과 같다. 1일때 -> 1 2일때 -> 1+1, 2 3일때 -> 1+1+1, 1+2, 2+1, 3 4일때는 1+3, 2+2, 3+1 이라는 경우를 생각할 수 있다. 풀이 코드 T = int(input()) for test_case in..

문제 출처 : www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 문제 해석 : 토마토가 익는 것은 주변에 익은 토마토에 의해서 이루어진다. 따라서 모든 토마토가 익을 때 까지 걸리는 시간을 출력하는 문제이다. 문제 풀이 : 전형적인 BFS 문제이지만 3차원이기 때문에 인덱싱을 조심해서 풀면 풀 수 있다. 풀이 코드 from collections import deque def BFS(): while Q: x,y,z = Q.popleft()..

문제 출처 : www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제 해석 : 토마토가 익는 것은 익은 토마토로 부터 전파된다. 최소 몇일이 되어야 모든 토마토가 익을 수 있을까? 에 대한 문제이다. 문제 풀이 : BFS를 통해서 문제를 풀 수 있다. 시간 초과에 유의하면서 차근차근 문제를 풀어 나가면 맞을 수 있다. 풀이 코드 from collections import deque import sys input = sys.stdin.readli..

문제 출처 :www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net 문제 해석 : x,y로 이루어진 달력은 M, N보다 크면 그 나머지 값을 가지게 되는데 1부터 시작하게 된다. 문제 풀이 : 시간 복잡도를 해결하기 위해서는 수학적 계산을 통해서 문제를 풀어야한다. X를 만족하는 M을 for 문을 통해서 반복적으로 위로 연산 하면서 찾으면 해결 할 수 있다. 풀이 코드 T = int(input()) for test_case in range(T): M,N,x,y = ma..

문제 출처 : www.acmicpc.net/problem/5525 5525번: IOIOI 첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다. (1 ≤ N ≤ 1,000,000, 2N+1 ≤ M ≤ 1,000,000) www.acmicpc.net 문제 해석 : 주어진 문자열에 특정 문자열이 몇번 반복되는지 검사하는 문제이다. 문제 풀이 : 단순하게 이중 반복문을 통해서 문제를 풀었을 때 시간 초과가 났다. 따라서 반복문을 한번만 돌면서 이를 충족시켜야한다. 풀이 코드 import sys input = sys.stdin.readline N = int(input().rstrip()) M = int(input().rstrip()) S = input().rstrip() a..

문제 출처 : www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 문제 해석 : 입력으로 주어지는 R or D 명령에 따라 배열을 수정하는 문제이다. 문제 풀이 : 입력되는 문자열을 잘 처리하여 처리하면 되는 문제이다. 풀이 코드 T = int(input()) for test_case in range(T): C = input() N = int(input()) arr = input().rstrip()[1:-1].split(",") if N == 0: arr = [] l, r, re = 0, 0, True for com ..

문제 출처 : www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제 해석 : 붙어있는 집끼리 같은 단지로 취급하여 몇개의 단지가 있는지 단지 번호 몇개의 집이 있는지 출력하는 문제이다. 문제 풀이 : BFS를 통해서 간단하게 문제를 풀이할 수 있다. 가능한 다른 풀이 : DFS도 이용가능하지만 BFS가 더 적당할 것 같다. 풀이 코드 from collections import deque def BFS(a, b, count): global visited Q = ..

문제 출처 : www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 문제 해석 : 색종이를 계속해서 쪼개어 같은 색만 남을 때까지 자르는 행위를 하고 한 가지 색상으로만 된 색종이의 갯수를 출력하는 문제이다. 문제 풀이 : 전형적인 분할정복 문제로 아래의 풀이는 실제 배열을 잘라서 파라미터로 넘기고 이를 저장하는 방식으로 문제를 풀었다. 4 분할을 진행하기 때문에 2중 for문을 2번씩 도는 형식으로 진행된다. 가능한 다른 풀이 : 파라..

문제 출처 : www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 문제 해석 : 1번 컴퓨터로 부터 바이러스가 퍼진다. 이때 네트워크상에 연결된 모든 컴퓨터가 감연되는데 이 수를 구하는 문제이다. 문제 풀이 : 다양한 방법으로 문제를 풀이할 수 있지만 자신의 부모를 찾는 연산을 통해서 부모 노드가 1인 모든 노드를 찾으면 되기 때문에 부모를 찾는 방법을 사용했다. 다만 입력의 순서 때문에 오류가 발생할 수 있기 때문에 2번의 union 연산을 진행했다. 가능한 다른 ..

문제 출처 : www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 해석 : 계단에 적힌 수들을 합하면서 올라간다. 이때 한번에 한 개씩 3개 이상의 계단을 오르지 못하고 2계단을 한번에 이동할 수 있다. 수의 최대값을 구하는 문제이다. 문제 풀이 : 전형적인 DP 문제로 점화식을 도출 할 수 있다. 한번에 3개의 계단을 연속적으로 이동하지 못하기 때문에 1. 이전계단과 자신의 계단 + 3칸 전 최대값 2. 두개 이전의 계단의 최대값 + 자신의 계단 중 가장 큰 값을 구..