효과는 굉장했다!

1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 알고리즘 분류 다이나믹 프로그래밍 SOLUTION import sys n = int(sys.stdin.readline()) triangle = [list(map(int, sys.stdin.readline().split())) for _ in range(n)] for i in range(1,n): for j in range(len(triangle[i])): if j == 0: # 제일 왼쪽 숫자 triangle[i][j] += triangle[i-1][j] elif j == i: # 제일 오른쪽 숫자 triangle[i][j] += t..

1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 알고리즘 분류 수학 분할 정복을 이용한 거듭제곱 SOLUTION pow() 함수를 이용한 간단한 코드 print(pow(*map(int,input().split()))) 분할 정복 이용한 코드 import sys def divide_and_conquer(num, n): if n == 1: return num % C if n % 2 == 0: y = divide_and_conquer(num, n//2) return y * y % C else: y = divide_and_conquer(num, (n-1)//2) return y *..

1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 알고리즘 분류 다이나믹 프로그래밍 SOLUTION import sys N = int(sys.stdin.readline()) RGB_cost = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] for i in range(1,N): # 이전 집 색깔과 겹치지 않는 것이 Key Point RGB_cost[i][0] = min(RGB_cost[i-1][1], RGB_cost[i-1..

15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 알고리즘 분류 백트래킹 SOLUTION import sys from itertools import combinations_with_replacement N, M = map(int, sys.stdin.readline().split()) N_list = list(map(int, sys.stdin.readline().split())) N_list.sort() # 중복되는 수열 출력을 방지하기 위해 set() 이용 combi_w_list = sorted(set(lis..

15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 알고리즘 분류 백트래킹 SOLUTION import sys from itertools import permutations N, M = map(int, sys.stdin.readline().split()) N_list = list(map(int, sys.stdin.readline().split())) # 중복되는 수열 출력을 방지하기 위해 set() 이용 permu = sorted(set(list(permutations(N_list, M)))) for i in p..

11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 알고리즘 분류 그래프 이론 그래프 탐색 트리 너비 우선 탐색 깊이 우선 탐색 SOLUTION import sys from collections import deque def dfs(): # 깊이 우선 탐색 활용 queue = deque([1]) # 트리의 루트가 1번이므로 1번 노트부터 시작 while queue: # 트리에 연결된 노드들을 전부 탐색 node = queue.popleft() for i in graph[node]: if not visited[i]: # 방문하지 않은 노드일때 # queue에 다시 넣어줘서 넣어준..

11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 알고리즘 분류 다이나믹 프로그래밍 SOLUTION import sys N = int(sys.stdin.readline()) N_list = list(map(int, sys.stdin.readline().split())) dp = [1] * N # Dynamic Programming 이용 for i in range(N): for j in range(i): if N_list[i] > N_l..

16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 알고리즘 분류 구현 그래프 이론 그래프 탐색 너비 우선 탐색 시뮬레이션 SOLUTION import sys import heapq def bfs(): visited = [[False] * N for _ in range(N)] shark_size = 2 exp = 0 ans = 0 while heap: cnt, x, y = heapq.heappop(heap) # 해당 칸의 물고기를 먹을 수 있을 때 if 0 < space[x][y] < shark_size: ..

15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 알고리즘 분류 백트래킹 SOLUTION import sys from itertools import combinations_with_replacement, repeat N, M = map(int, sys.stdin.readline().split()) num_list = sorted(map(int, sys.stdin.readline().split())) combi_w_replace = list(combinations_with_replacement(num_li..

15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 알고리즘 분류 백트래킹 SOLUTION import sys from itertools import permutations N, M = map(int, sys.stdin.readline().split()) num_list = list(map(int, sys.stdin.readline().split())) permu = list(permutations(num_list, M)) #permutations()함수 이용 permu.sort() for i in per..