📌 문제유형: DP https://www.acmicpc.net/problem/1003   📌 풀이  이 문제에서 포인트는 !!! 시간 제한이 0.25초 밖에 안된다는 점이다. 따라서 재귀함수로 작성하게 되면, 1시간초과에 걸리게 된다.  그 해결 방법은 동적 계획법(DP)에 있다.  즉, 메모제이션을 활용해야 한다. 메모제이션이란 앞서 계산했던 값을 저장해두어, 추후 다시 필요하게 될 때 다시 계산하는 것이 아니라 이미 계산된 값을 불러오는 것이다.  위의 문제는, n에 대한 피보나치 수열이 계산될 때 0과 1이 몇 번씩 필요로 되는가에 있다.  DP를 풀 때 1. 하나의 예제를 가지고 직접 손으로 적어보면서 실마리를 찾는다. 2. 규칙성을 찾아본다. 3. 이를 점화식으로 세워본다. (앞에서 #를 선..

https://www.acmicpc.net/problem/17219   📌 풀이 한 줄씩 공백으로 split()해서 받고, 딕셔너리 타입으로 저장해 둔다. N+2줄부터는 key 값으로 value 찾기니까 쉽다!  N, M = map(int, input().split())pwd = {}for _ in range(N): site, pw = map(str, input().split()) pwd[site] = pwfor _ in range(M): toFind = input() print(pwd[toFind])

https://www.acmicpc.net/problem/11047  풀이  동전 구하기는 그리디 알고리즘에서 유명한 문제이다.  해당 문제에서 내림차순으로 정렬해 나누기를 반복했을 때 정답이 될 수 있는 이유는 arr 값들끼리 배수의 관계에 있기 때문이다.  만약 arr = [100, 400, 500, 100] 인데, 800원을 만들 수 있는 동전의 최소 개수는 아래의 코드 기반으로 하면 4개가 된다. (500원 1개, 100원 3개) 하지만 이론 상으로는 400원 2개로 끝이 난다.  따라서, 그리디 문제를 풀 때는 1. 완전탐색을 고민해보고 2. 반례가 없는지 꼭 확인해봐야 한다.  N, K = map(int, input().split())arr = []for _ in range(N): arr..

https://www.acmicpc.net/problem/11399    풀이 앞쪽의 인출 시간이 짧아야 대기시간도 덩달아 짧아진다. 즉 arr을 오름차순으로 정렬하고, 대기시간은 앞선 인출시간의 누적 합이고 시간의 총합은 i번째 사람의 대기시간 + 인출시간이므로 누적 합을 이용하면 된다.  (이때 n번 사람에 몇 분의 인출이 필요한지 딕셔너리 d로 정의를 해두었는데, 복기해보니 큰 쓸모는 없다.)  N = int(input())d = {}arr = list(map(int, input().split()))for i in range(N): d[i+1] = arr[i]d_sorted = dict(sorted(d.items(), key=lambda x:x[1]))total = 0wait = 0for t ..

https://www.acmicpc.net/problem/1764   듣지도, 보지도 못한 이름을 찾아야 하니까 교집합을 찾으면 될 것이다.  집합 set()으로 바꿔주고,  arr1.intersection(arr2) 를 해주면 차집합이 된다.  N, M = map(int, input().split())arr1 = []arr2 = []for _ in range(N): arr1.append(input())for _ in range(M): arr2.append(input())arr1 = set(arr1); arr2 = set(arr2)ans = list(arr1.intersection(arr2))ans.sort()print(len(ans))for a in ans: print(a)

1. 유형: 스택  2. 문제  3. 풀이 ** ( 만 스택에 push 하는 걸로 간다. ** 괄호 VPS가 성립되지 않는 경우는 외우게 좋겠다. 1. )를 만났을 때 stack이 비어있는 경우; 안 빈 경우에는 pop 2. VPS를 모두 돌았는데도, stack이 안 비어있는 경우 T = int(input())for tc in range(T): stack = [] # ) 만 저장 vps = input() flag = 1 for v in vps: if v == "(": stack.append(v) elif v == ")": if stack: stack.pop() else: ..