머신러닝 숄구

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", "r") input=sys.stdin.readline # 입력양이 많을 때 이 라인을 쓰면 입력 속도가 빨라진다 # s=input().rstrip() # 위의 라인을 사용하게 되면 문자열을 읽을 때 줄바꿈 기호가 들어오므로 이를 날려야한다 def DFS(level, sum): global minimum if sum > target: # sum이 target 금액보다 커지면 return return if level > minimum: # CUT EDGE -> minimum level 보다 level이 더..

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

이전의 포스팅과 같이 집합의 원소가 존재하는 경우와 존재하지 않는 경우를 구분하는 이진 트리를 만들어서 응용하면 된다 서로소 집합이란 서로 겹치는 원소가 없는 집합을 말한다 {1,3,5,7}={6,10} 부분집합의 합이 같다는 것은 ex) 32 - (1+3+5+7=16) =16 (10+6) 또한 두 부분집합의 원소의 합이 같은 경우에 총 집합의 합을 2로 나눈 경우가 그 값이 된다 ex) 1+3+5+..+10=32/2=16 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") def DFS(level, sum): if sum > total//2: # 시간 복잡..

DFS 깊이 우선 탐색 알고리즘을 이용 + 스택과 재귀함수의 사용 트리 구조로 생각해서 이해하고 자식 노드 양쪽을 그 집합의 수가 존재하냐 안하느냐로 나눈다

DFS 로 이진 트리의 순회를 설명해 보면 (ex.전위 순회)

윤성우 자료구조에서 배웠던대로 힙에 데이터를 넣고 빼는 과정은 이렇다 이것이 파이썬에서는 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: ..