효과는 굉장했다!

2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 SOLUTION import sys from collections import deque def maze_serach(x,y): dx = [1,-1,0,0] dy = [0,0,-1,1] queue = deque([[0,0]]) # 시작점 while queue: # queue가 빌 때까지 x, y = queue.popleft() # 현재 위치에서 4가지 방향으로 위치 확인 for i in range(4): nx = x + dx[i] ny =..

1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 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 : heapq.heappush(heap, x) elif x == 0: if heap == []: print(0) else: print(heap[0]) heapq.heappop..

1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 SOLUTION import sys from collections import deque def bfs(): queue = deque([N]) while queue: now = queue.popleft() # 왼쪽에서 뺴는 이유 작은 수 부터 차례대로 조사 해야함 if now == K: print(location[now]) break for value in (now-1, now+1..

1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 플로이드-와샬 SOLUTION import sys from collections import deque def bfs(realationship, start_node): num = [0] * (N+1) # 각각 노드가 몇번의 케빈 베이컨 수인지 측정을 위해 구현 queue = deque([start_node]) # deque를 이용해 시간복잡도 줄임, q.pop..

1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 알고리즘 분류 분할 정복 재귀 SOLUTION import sys N, r, c = map(int, sys.stdin.readline().split()) # r = 행, c = 열 result = 0 while True: if N = middle: if c >= middle: # 오른쪽 아래 구역 result += ((N-..

11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 SOLUTION import sys from collections import deque def bfs(node): queue = deque([node]) while queue: node = queue.popleft() for i in graph[node]: if visit_list[i] == 0: queue.append(i) vi..

11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 알고리즘 분류 그리디 알고리즘 SOLUTION import sys N, K = map(int, sys.stdin.readline().split()) coin = sorted([int(sys.stdin.readline()) for _ in range(N)], reverse=True) # 동전을 최소로 사용해야하므로 내림차순으로 정렬 print(coin) answer = 0 for i in range(N..

5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net 알고리즘 분류 문자열 SOLUTION import sys N = int(sys.stdin.readline()) M = int(sys.stdin.readline()) S = list(sys.stdin.readline()) answer = 0 cnt = 0 i = 1 while i < M - 1: if S[i-1] == "I" and S[i] == "O" and S[i+1] == "I": # IOI..

1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 알고리즘 분류 분할 정복 재귀 SOLUTION import sys def clip_paper(x, y, n): global zero, one, min_one check_num = paper[x][y] for i in range(x, x + n): for j in range(y, y + n): if paper[i][j] != check_num: # 모든 종이가 같은 수로 되어 있지 않으므로 종이를 9등분 한다 for k in range(3): for l..

1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 알고리즘 분류 수학 문자열 그리디 알고리즘 파싱 SOLUTION import sys s = sys.stdin.readline().rstrip().split('-') # -를 기준으로 나눠서 리스트화 ans = 0 # -를 기준으로 안나눠진다는 것은 + 식이므로 +를 기준으로 나눠서 더해줌 for i in s[0].split('+'): ans += int(i) for i in s[1:]: for j in i.split('+'): # +가 있다고 더해주는 것이..