효과는 굉장했다!

1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 SOLUTION import sys from collections import deque def dfs(graph, start_node): queue = deque([start_node]) visit = [] while queue: node = queue.pop() # 가장 깊숙이 있는 노드부터 탐색해야 하므로 if node not in visit: # ..

1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 알고리즘 분류 자료 구조 우선순위 큐 SOLUTION import sys import heapq N = int(sys.stdin.readline()) left = [] right = [] for _ in range(N): num = int(sys.stdin.readline()) if len(left) == len(right): heapq.heappush(left, (-num, num)) # 최대 힙 else: heapq.heappush(right..

11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 알고리즘 분류 자료 구조 우선순위 큐 SOLUTION import sys import heapq N = int(sys.stdin.readline()) heap = [] for _ in range(N): x = int(sys.stdin.readline()) if x == 0 : if heap: # heap이 비어있지 않다면 print(heapq.heappop(heap)[1]) # heap[1]이 -를 붙히지 않은 원래 값이므로 else: prin..

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

1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 알고리즘 분류 분할 정복 재귀 SOLUTION import sys def quad_tree(x,y,N): point = tree[x][y] for i in range(x,x+N): for j in range(y,y+N): if point != tree[i][j]: # 같은 색의 점이 아니면 분활 answer.append("(") # 분할될 때 마다 괄호 추가 quad_tree(x,y,N//2) # 2 사분면 quad_tree(x,y+N//2,N//2..

2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 알고리즘 분류 다이나믹 프로그래밍 SOLUTION import sys stair = int(sys.stdin.readline()) # 계단의 개수는 최대 300 이므로 0번째 인덱스를 고려하여 0 ~ 300 까지 301개 생성 score = [0]*301 dp = [0]*301 for i in range(1, stair+1): score[i] = int(sys.stdin.readline()) dp[1] = score[1] # 처음 1칸 올라가는 경우 dp[2] = score..

1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 알고리즘 분류 다이나믹 프로그래밍 SOLUTION import sys zero = [1,0] # 0이 출력되는 횟수 one = [0,1] # 1이 출력되는 횟수 # 피보나치는 구하려는 수의 한단계 전과 두단계 전 수의 합이므로, 0 과 1의 개수도 한단계 전과 두단계 전에서 나오는 개수를 더하면 된다 for i in range(2,41): zero.append(zero[i-1] + zero[i-2]) one.append(one[i-1] + one[i-2]) T = int(sys.stdin.readline()) for _ in range(T): N = int(..

1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 알고리즘 분류 그리디 알고리즘 정렬 SOLUTION import sys N = int(sys.stdin.readline()) meeting_time = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] meeting_time = sorted(meeting_time, key=lambda t:[t[1], t[0]]) # 빨리 끝나는 회의 순서대로 정렬 last_time = 0 cnt = 0 for i, j in meeting_time: # 회의 시작시간이 이전 회의 끝나는 시간보다 커야 배정이 가능 if i >= l..

13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 알고리즘 분류 그리디 알고리즘 SOLUTION import sys N = int(sys.stdin.readline()) road = list(map(int, sys.stdin.readline().split())) + [0] oil = list(map(int, sys.stdin.readline().split())) price = sys.maxsize total = 0 for i in range(N): # 기름 가격이 가장 싼 주유소로 계속 갱신시켜줌 ..

14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 알고리즘 분류 부르트포스 알고리즘 백트래킹 SOLUTION import sys from itertools import permutations N = int(sys.stdin.readline()) nums = list(map(int, sys.stdin.readline().split())) opeartor = list(map(int, sys.stdin.readline().split())) op_list = ["+..