효과는 굉장했다!

10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 알고리즘 분류 수학 분할 정복 분할 정복을 이용한 거듭제곱 선형대수학 SOLUTION import sys def mulmatrix(m1, m2): tmp = [[0] * N for _ in range(N)] # 행렬 곱 계산 for i in range(N): for j in range(N): for k in range(N): tmp[i][j] += m1[i][k] * m2[k][j] tmp[i][j] %= 1000 # 연산 속도를 높이기 위해 계속 1000으로 나눠준다 retu..

9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 알고리즘 분류 자료 구조 문자열 스택 SOLUTION import sys string = sys.stdin.readline().rstrip() explosion = list(sys.stdin.readline().rstrip()) stack = [] for i in range(len(string)): stack.append(string[i]) # 시간 단축을 위해 stack에 마지막으로 들어온 문자랑 비교를 한다 if stack[-1] == expl..

9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 알고리즘 분류 브루트포스 알고리즘 백트래킹 SOLUTION import sys def check(x): # 윗줄의 퀸의 라인과 겹치는지 확인하는 함수 for i in range(x): # 같은 열인지 or 대각선에 퀸이 위치하는지 판단 if chess[x] == chess[i] or abs(chess[x] - chess[i]) == x - i: return False return True def dfs(x): global cnt if x == N: cnt += 1 else: f..

9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 알고리즘 분류 다이나믹 프로그래밍 SOLUTION import sys str1 = list(sys.stdin.readline().rstrip()) str2 = list(sys.stdin.readline().rstrip()) lcs = [[0 for _ in range(len(str2)+1)] for _ in range(len(str1)+1)] for i in range(1, len(str1)+1): for j in r..

16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 알고리즘 분류 그래프 이론 그리디 알고리즘 그래프 탐색 너비 우선 탐색 SOLUTION # Greedy Algorithm A, B = map(int, input().split()) cnt = 1 while True: # A와 B가 같아질 때 종료 if A == B: break # a를 2로 나눈 나머지가 0이 아니고 10으로 나눈 나머지가 1이 아니거나, b가 a보다 작은 경우 elif (B % 2 != 0 and B % 10 != 1) or (B < A): cnt = -1 break else: # 10으로 나누었을 때 나머지가 1인 경우 if B % 10 == 1: B //= 10 cn..

11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 알고리즘 분류 다이나믹 프로그래밍 누적 합 SOLUTION import sys N, M = map(int, sys.stdin.readline().split()) graph = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] dp = [[0 for _ in range(N+1)] for i in range(N+1)] for i in range(N): for ..

9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 알고리즘 분류 다이나믹 프로그래밍 SOLUTION import sys T = int(sys.stdin.readline()) for _ in range(T): N = int(sys.stdin.readline()) sticker = [list(map(int, sys.stdin.readline().split())) for _ in range(2)] # 위에서 때는 경우, 아래서 때는 경우를 나눠서 구한다 for i in range(1, N): # i가 1일..

1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 알고리즘 분류 트리 재귀 SOLUTION import sys def preorder(root): # 전위 순위 if root != '.': print(root, end="") # 루트 preorder(tree[root][0]) # 왼쪽 preorder(tree[root][1]) # 오른쪽 def inorder(root): # 중위 순위 if root != '.': inorder(tree[root][0]) # 왼쪽 print(root, end="") #..

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 *..