https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net from collections import deque MAX_NUM = 100_001 # 위치값의 범위 0 ~ 100,000 N, K = map(int, input().split()) visited = [False] * MAX_NUM # 방문 여부 기록 sec_list = [0] * MAX_NUM # 각 좌표에 도달할 때의 시간 기록 def bfs(): # bfs로 한칸..
알고리즘 🤔
https://www.acmicpc.net/problem/11724 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 from collections import deque import sys sys.setrecursionlimit(10 ** 7) # 재귀 호출 제한 올리기 input = sys.stdin.readline # 많은 입력을 받아 시간 초과가 나므로 이렇게 입력 받기. n, m = map(int, input().split()) # 정점과 간..
https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net from collections import deque N, M = map(int, input().split()) # N 행 M 열 입력 받기 adj = [list(map(int, input())) for _ in range(N)] # 미로 행렬 저장 visited = [[False] * M for _ in range(N)] # 미로 방문 행렬 저장 q = deque() # bfs용 큐 dx = [0, 0, -1, 1] dy = ..
https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net # 파이썬에서는 재귀 최대 한도의 디폴트가 1000이기 때문에 더 늘려주려면 다음의 코드가 필요 import sys sys.setrecursionlimit(10 ** 7) n, k = map(int, input().split()) MOD = 10007 cache = [[0] * 1001 for _ in range(1001)] # N, K는 1부터 1000까지 이므로 이중 배열 생성 # 이항계수 nCk를 bino(n, k) 라 하면, # bino(n, k) = bino..
https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net n = int(input()) cache = [-1] * 91 # n이 최대 90이므로, 0~90까지 91개의 공간 필요. cache[0] = 0 # 피보나치 수의 F0은 0 cache[1] = 1 # 피보나치 수의 F1은 1 def fi_bottomup(n): # Tabulation, 순서 중요 for i in range(2, n + 1): # 0, 1은 미리..
https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net from bisect import bisect_left, bisect_right n = int(input()) cards = list(map(int, input().split())) cards.sort() # 이진탐색 전에 정렬은 필수. m = int(input()) ans = [] query = list(map(int, input().split())) for q i..
https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net n = int(input()) li = list(map(int, input().split())) m = int(input()) minn = 0 maxx = max(li) mid = (maxx + minn) // 2 ans = 0 def is_possible(mid): # 상한선을 mid로 한 각 지방의 예산합이 총 예산 이하인지 체크하는 함수. return sum(min(mid, r) for..
https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net from itertools import permutations li = [ int(input()) for _ in range(9) ] # 9명의 난쟁이를 입력받아 리스트로 만드는 리스트 컴프리헨션 # 순열(permutations) 을 사용하여, 9요소의 리스트 중 7개를 뽑는 경우의 수 중에서, for item in permutations(li, 7): if sum(item) == 100: # 합이 100..
https://www.acmicpc.net/problem/1302 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net import sys input = sys.stdin.readline n = int(input()) map = dict() # map 자료구조 for _ in range(n): str = input().rstrip('\n') if str in map: # 맵에 입력받은 키가 있다면 +1 map[str] += 1 else: # 없다면 0으로 초기화 map[str] = 0 # list.sort(..
