머신러닝 숄구

1~N번의 구술을 중복을 허용하여 M번 뽑는 것이므로 이진 트리의 줄기가 N 줄기로 나뉘면 된다 Level 0 에서 1,2,~N 중에 하나 뽑고, Level 1 에서 1,2,~N 중에 하나 뽑고... Level이 M에 도달하면 결과 print 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 import sys # sys.stdin=open("input", "r") input=sys.stdin.readline # 입력양이 많을 때 이 라인을 쓰면 입력 속도가 빨라진다 # s=input().rstrip() # 위의 라인을 사용하게 되면 문자열을 읽을 때 줄바꿈 기호가 들어오므로 이를 날려야한다 def DFS(level): glo..

이전 문제와 원리는 같으나 시간을 초과하는 경우가 생겨 Cut Edge 방식을 생각해봐야 한다 부분 집합의 o, x 존재 유무를 이진 트리로 표현하고 DFS(idx, sum) 의 방식으로 함수를 생성한다 시간이 초과되는 경우를 고려하여 트리의 특정 level까지 summation 한 값 + 아직 보지 않은 나머지 level의 원소의 합이 max weight value 보다 작다면 굳이 다음 level의 트리를 검사해 볼 필요가 없으므로 return을 해주는 방식 Cut Edge 방식을 사용하면 시간이 현저하게 줄어든다, 역시 알고리즘은 아주 중요해! 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 import sy..

윤성우 자료구조에서 배웠던대로 힙에 데이터를 넣고 빼는 과정은 이렇다 이것이 파이썬에서는 heapq 라이브러리로 아주 쉽게 구현이 된다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 import sys import heapq as hq # heap 불러오기 # sys.stdin = open("input", "rt") a=[] # heap을 사용하려면 빈 리스트가 있어야 한다 while True: n=int(input()) if n==-1: break elif n==0: if len(a)==0: print(-1) else: print(hq.heappop(a)) # heapq 에서 heappop은 루트 노드 값을 pop else: hq.heappush(a, n) ..

1. 딕셔너리를 이용하는 방법 참고자료 - https://datascienceschool.net/01%20python/02.11%20%ED%8C%8C%EC%9D%B4%EC%8D%AC%EC%97%90%EC%84%9C%20%EB%94%95%EC%85%94%EB%84%88%EB%A6%AC%20%EC%9E%90%EB%A3%8C%ED%98%95%20%EB%8B%A4%EB%A3%A8%EA%B8%B0.html 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 import sys # sys.stdin = open("input", "rt") str1=input() dict1=dict() str2=input() for ch in str1: dict1[ch] = dict1.get(c..

윤성우 자료구조에 나왔던 방식으로 풀어봄 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 import sys # sys.stdin = open("input", "rt") equ=input() def return_priority(ch): if ch=="*" or ch=="/": return 3 elif ch=='+' or ch=='-': return 1 else: return -1 def who_is_precede(pre, aft): if return_priority(pre) >= return_priority(aft): return 1 else: ..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 import sys sys.stdin = open("input", "rt") code=input() stack=[] piece=0 for i in range(len(code)): if code[i]=='(': # '(' 면 stack에 쌓아주고 stack.append(code[i]) else: if code[i-1]=='(': # '()' 면 레이저 발사 stack.pop() # 스택에 쌓인 막대 개수만큼 조각이 난다 piece+=len(stack) else: stack.pop() # '))' 면 막대 하나가 끝남 piece+=1 # 따라서 마지막의 1조각 더해준다 print(piece) Colored by Color ..

m 개의 숫자는 꼭 제거 해야한다는 점 명심 숫자의 순서는 유지되야 한다는 점 명심 너무 헤맸다... ㅠ흑 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 import sys # sys.stdin = open("input", "rt") n, m = map(int, input().split()) number = list(map(int, str(n))) # n이라는 int형 정수를 str으로 변환 후 각각의 letter에 대해 int를 적용해서 리스트화 한다 stack=[] for i in number: while stack and m > 0 and i > stack[-1]: # stack이 비어있지 않고 / 제거해야 할 수가 0이 아직 안됐고 / 스택의 마지막 숫자가 ..

키와 몸무게 중 적어도 하나는 다른 멤버보다 뛰어나야 한다 키를 기준으로 내림 차순으로 정렬하거나 or 몸무게를 기준으로 내림차순으로 정렬해서 sorting을 시작한다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 import sys sys.stdin = open("input", "rt") n = int(input()) personInfo = [list(map(int, input().split())) for _ in range(n)] personInfo.sort(reverse=True) cnt=0 max_weight=0 for height, weight in personInfo: if weight > max_weight: cnt+=1 max_weight=weight print(cnt) Col..

그리디 알고리즘 - 문제를 풀어나가는 과정에 있어서 이 단계에서 가장 좋은게 무엇인지 판단하고 선택 보통의 그리디 문제는 정렬 후 차례로 선택해 나가게 된다. 거의 대부분이 정렬과 동반되어 문제풀이를 한다. 여기서 중요한 것은 sort(key=) 함수를 잘 알아야 한다! 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 import sys # sys.stdin = open("input", "rt") n = int(input()) meeting = [list(map(int, input().split())) for _ in range(n)] #회의가 끝나는 시간에 맞추어 sorting을 진행한다 #key는 sort의 기준을 말하는데 여기서는 끝나는 시간을 먼저 기준으로 sort..

최소 용량의 크기를 이분 탐색으로 찾아나가자 DVD 한 장에 들어갈 수 있는 용량은 최소 9분 (가장 긴 노래의 용량)에서 최대 (1+2+3..+9=45)분이다 따라서 Left Pointer는 9분, Right Pointer는 45분에서 mid 값을 찾아서 이분 탐색을 진행한다 곡의 순서가 그대로 유지되어야 함을 인지해야 한다 사업에 낭비되는 DVD를 가급적 줄이려고 하기 때문에, M개 이하이여도 (즉, 2개, 1개) 괜찮다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 import sys # sys.stdin = open("input", "rt") n, m = map(int, input().split()) so..