작은 지식주머니

백준 링크:https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net BFS로 풀이하였다. 보통 최단거리를 계산하는 문제는 BFS로 해야 쾌적하다고 들었다. BFS로 자리를 찾아가며 첫 자리가 S[0][0]이 1이라면 다음 자리는 2이므로 S[1][0]은 S[0][0] + 1 로 계산하였다. 복사한 예제의 수열 s를 출력해보면 순서따라 숫자가 잘 출력된것을 볼 수 있다. n,m=map(int,input().split()) s=[list(input()) for i in range(n)] ..

백준 링크:https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net deque를 이용해서 풀려고했지만 시간초과가 나서 검색후 heapq에 대한 정보를 처음 알게되었다. https://littlefoxdiary.tistory.com/3 [Python] 힙 자료구조 / 힙큐(heapq) / 파이썬에서 heapq 모듈 사용하기 힙은 특정한 규칙을 가지는 트리로, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로..

백준 링크:https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net nCm 출력문제. factorial을 사용하면 간단한 식으로 풀수있다. import math n,m=map(int,input().split()) def factorial(n,m): return math.factorial(n) // (math.factorial(m)*math.factorial(n-m)) print(factorial(n,m)) n! / (m!*(n-m)!)

백준 링크:https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net dp문제이다. 이중 for in문을 사용해서 숫자맞추기를 하면된다. n= int(input()) li = list(map(int,input().split())) dp=[1] for i in range(1,n): d = [] for j in range(i): if li[i] > li[j] : d.append(dp[j]+1) if len(d) == 0: dp.append(1) else: dp.app..

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net DP문제이다. import sys t = int(input()) for i in range(t): n = int(input()) s = [] for j in range(2): s.append(list(map(int,sys.stdin.readline().split()))) if len(s[0])

백준 링크:https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 백 트래킹문제이다. import sys m = 6 def dfs(a): if len(result) == m: for i in result: print(i,end=' ') print() for i in s: if i not in result and a < i: result.append(i) dfs(i) result.pop() while True: s = list(map(int,..

백준 링크:https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 에라토스테네스의 체를 사용하면 간단하게 풀수있다. import math def is_prime_number(n,s): arr = [True for i in range(n+1)] for i in range(2,int(math.sqrt(n)+1)): if arr[i] == True: j = 2 while i * j

백준 링크:https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 그리드, 정렬을 이용한 풀이를 했다. import sys n=int(input()) li=[list(map(int,sys.stdin.readline().split())) for i in range(n)] li.sort() cnt=0 for i in range(n): result = 1 temp = li[i][1] for j in range(i+1,n): if temp > li[j][0]: continue else: temp += (li[j][1]-li[j][0]) result += 1 if cnt < ..