머신러닝 숄구

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

파이썬에서 제공하는 deque 자료구조를 가지고 원형 queue를 구현 해보는 문제 처음에는 파이썬에서 제공하는 deque을 이용하지 않고 포인터를 쓴다는 개념으로 접근해서 풀이했다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 import sys sys.stdin = open("input", "rt") n, k = map(int, input().split()) queue = list(range(1, n+1)) pointer=0 cnt=0 while len(queue) > 1: if pointer==len(queue): pointer=0 if cnt==k-1: queue.pop(pointer) cnt=0 continue pointer+=1 cnt+=1 p..

윤성우 자료구조에 나왔던 방식으로 풀어봄 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이 아직 안됐고 / 스택의 마지막 숫자가 ..

저녁에 피곤한 상태에서 풀다가 안풀려서 다음날 아침에 풀었더니 금방 풀렸다. 피곤해도 쉽게쉽게 풀리게끔 계속 알고리즘 공부에 정진!! 그리디 알고리즘은 현재 직면한 상태를 먼저 해결하자는 관점에서 풀면 해결점이 보이는 것 같다 핵심은 주어진 역수열이 오름 차순 수열의 역수열이라는 점, 앞에서부터 순차적으로 찾아나가면 된다는 점을 잘 알아야 한다는 것 풀이1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 import sys # sys.stdin = open("input", "rt") total_num = int(input()) cnt_ls = list(map(int, input().split())) check_ls = [0]*total_num # 숫자가 배정됐는지 아닌지에 대한..

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") n, limit = map(int, input().split()) weight = list(map(int, input().split())) weight.sort() cnt=0 while weight: # 리스트에 아무도 없으면 while문 탈출 if len(weight)==1: # 마지막 한명이 남은 경우 두번째 if절에서 limit의 이하로 되버리면, cnt+=1 # else 절에서 pop 할 때 오류가 발생하므로 한 명이 남은 경우의 조건을 따로 생성해, break # 오류를 방지해준다. if weight[0]+weight[-1] ..