효과는 굉장했다!

21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmicpc.net 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 SOLUTION import sys from collections import deque def main(): N, M = map(int, sys.stdin.readline().split()) campus = [list(sys.stdin.readline().rstrip()) for _ in range(N)] visited = [[False] * M for _ in range(N)]..

17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 알고리즘 분류 구현 시뮬레이션 SOLUTION import sys from copy import deepcopy # 미세먼지 확산 def spread(): dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] tmp_maps = [[0]*C for _ in range(R)] tmp_maps[air_up][0], tmp_maps[air_down][0] = -1, -1 for row in range(R): for col in range(C): if h..

14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 알고리즘 분류 그래프 이론 데이크스트라 플로이드–워셜 SOLUTION Dijkstra O(NlogN) import sys import heapq INF = sys.maxsize def dijkstar(start): heap = [] distance = [INF] * (n+1) heapq.heappush(heap, (0, start)) distance[start] = 0 while heap: wei, now = heapq.heappop(heap) if distance[n..

14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 알고리즘 분류 구현 그래프 이론 브루트포스 알고리즘 그래프 탐색 너비 우선 탐색 SOLUTION import sys from collections import deque def check_safe(copy_map): # 0인 지역을 탐색해서 카운트 해준다 cnt = 0 for i in range(N): for j in range(M): if copy_map[i][j] == 0: cnt += 1 ans.append(cnt) def build_wall(cnt): if cnt ==..

import sys import math mod = int(1e9+7) def Divide_and_Conquer(num, exp): if exp == 1: # 기댓값이 1 이면 return num if exp % 2 == 0: half = Divide_and_Conquer(num, exp//2) return half * half % mod else: return num * Divide_and_Conquer(num, exp-1) % mod M = int(sys.stdin.readline()) total = 0 for _ in range(M): N, S = map(int, sys.stdin.readline().split()) gcd = math.gcd(N, S) # 최대공약수 N //= gcd S //= g..

12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 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() queue.append(N) # 시작점 location[N][0] = 0 # 가장 빠른 시간 location[N][1] = 1 # 경우의 수 while queue: now = queue.popleft() for value in (now-..

11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 알고리즘 분류 그래프 이론 플로이드–워셜 SOLUTION import sys INF = sys.maxsize n = int(sys.stdin.readline()) m = int(sys.stdin.readline()) maps = [[INF] * n for _ in range(n)] for _ in range(m): start, end, cost = map(int, sys.stdin.readline().split()) if cost < maps[start-1][en..

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