효과는 굉장했다!

1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 알고리즘 분류 그래프이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 SOLUTION import sys sys.setrecursionlimit(10000) # 파이썬에서 기본 재귀의 깊이의 제한은 1000이므로 임위로 늘려줘야 한다 def dfs(x,y): dir = [[0,1],[0,-1],[1,0],[-1,0]] # 방향설정 for diff in dir: dx = x + diff[1] # 1 -1 0 0 dy = y + diff[0] # 0 0 1 -1 if (0

11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 알고리즘 분류 다이나믹 프로그래밍 SOLUTION import sys n = int(sys.stdin.readline()) dp = [0] * 1001 # n은 최대 1000까지 이므로 1001개 생성(0번째 포함) # n == 2일때 까지는 규칙성이 보이지 않으므로 따로 생성 dp[0] = 0 dp[1] = 1 dp[2] = 3 for i in range(3, 1001): dp[i] = dp[i-1] + (dp[i-2] * 2) # n>=3 일때 다음과 같은 규칙이 성립된다 print(dp[..

11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 알고리즘 분류 다이나믹 프로그래밍 SOLUTION import sys n = int(sys.stdin.readline()) dp = [0] * 1001 # n은 최대 1000까지 이므로 1001개 생성(0번째 포함) # n == 2일때 까지는 규칙성이 보이지 않으므로 따로 생성 dp[0] = 0 dp[1] = 1 dp[2] = 2 for i in range(3, 1001): dp[i] = dp[i-1] + dp[i-2] # n>=3 일때 다음과 같은 규칙이 성립된다 print(dp[n..

11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 알고리즘 분류 누적 합 SOLUTION import sys N, M = map(int, sys.stdin.readline().split()) nums = list(map(int, sys.stdin.readline().split())) sum_list = [0] for i in range(N): sum_list.append(sum_list[-1] + nums[i]) # 미리 누적합을 구해놓음 for _ in range(M): i, j = ma..

11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 알고리즘 분류 그리디 알고리즘 정렬 SOLUTION import sys N = int(sys.stdin.readline()) p = list(map(int, sys.stdin.readline().split())) p.sort() # 시간의 합의 최솟값을 출력해야하므로 정렬 sum = 0 cnt = N for i in range(N): sum += p[i] * cnt #첫번째 사람은 총인원수 만큼 더해지고 두번째 사람은 총인원수-1 만큼 더해지는 형식 cnt -= 1 print(sum)

9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 알고리즘 분류 수학 다이나믹 프로그래밍 SOLUTION import sys dp = [1,1,1,2,2] # P(1) ~ P(5) T = int(sys.stdin.readline()) for _ in range(T): num = int(sys.stdin.readline()) if num >= 6: # num이 6 이상일 때에는 dynamic programming을 이용해 구함 for i in range(5, num): dp.append(dp[i-1] + dp[i-5]..

9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 알고리즘 분류 수학 자료 구조 해시를 사용한 집합과 맵 SOLUTION import sys from collections import Counter T = int(sys.stdin.readline()) for _ in range(T): n = int(sys.stdin.readline()) type_list = [] for _ in range(n): clothes, typ..

9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 알고리즘 분류 다이나믹 프로그래밍 SOLUTION import sys T = int(sys.stdin.readline()) model = [1, 2, 4] # 3번째 경우까지는 직접 생성 for i in range(3, 10): # n은 10까지 이므로 model.append(model[i - 3] + model[i - 2] + model[i - 1]) # 4부터 ~ n까지는 그 전, 전전, 전전전단계 경우의 수의 총합이다. # ex) model[4] = model[1] + model[2] + model[3] = 1 + 2 + 4 = 7 for _ in ran..

2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 알고리즘 분류 분할 정복 재귀 SOLUTION import sys def paper(x, y, N) : color = paper_list[x][y] for i in range(x, x+N) : for j in range(y, y+N) : if color != paper_list[i][j] : # 같은 색이 아니면 4개의 구역으로 나눔 paper(x, y, N//2) # 왼쪽 위 paper(x, y+N//2, N//2) # 오른쪽 위 p..

2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 SOLUTION import sys from collections import deque def main(): computer = {} visit = [] for i in range(int(sys.stdin.readline())): computer[i+1] = [] for j in range(int(sys.stdin.readline())): num1, num2 = map(int, sys.stdin..