전체 글

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

https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net import heapq import sys input = sys.stdin.readline n = int(input()) pq = [] # 우선순위 힙 for _ in range(n): x = int(input()) if x == 0: # 0을 입력 받으면 # 힙이 비어있으면 0을 출력, 아니면 최소 절댓값 중에서 최솟값 출력 print(heapq.heappop(pq)[1] ..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net MOD = 1_000_000_000 # cache[n][d] = 길이가 n, 마지막 숫자가 d인 계단수 개수 cache = [[0] * 10 for _ in range(101)] # n은 1~100 이므로 101개를 만들고, d는 0~9까지니까 10개를 만든다. for d in range(1, 10): # cache[1][0] 은 0으로 시작하므로 문제 조건에 따라 0이다. cache[1][d] = 1 # 길이가 1이고 자릿수가 0이 아니면 초기값은 1이다. for N in range(2, 101): # 길이 ..

https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net from collections import deque import sys n, m = map(int, input().split()) arr = deque() # 도화지 좌표 q = deque() # bfs에 쓸 큐 draw_num = 0 # 그림 개수 max_area = 0 # 최대 그림 넓이, 그림이 하나도 없는 경우에 가장 넓은 그림의 넓이는 0 이므로 for _ in range(n): arr.ap..