Total
동전 교환(DFS)
""" 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환 해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다. 동전의 종류개수 N(1
바둑이승차(DFS)
풀이1 sum + 앞으로 판단할 바둑이 무게 합(total-tsum) < maxVal 일 때, 더 깊이 내려갈 필요 없음 다 더하는 경우에도 (앞으로 판단 할 바둑이를 다 데려가도) 현재 저장된 최댓갑 maxVal보다 작기때문 import sys input=sys.stdin.readline # 트럭허용무게, 바둑이 수 c,n=map(int, input().split()) # 바둑이 무게 arr=[0]*n for i in range(n): arr[i]=int(input()) # 바둑이 총무게 total=sum(arr) maxVal=0 def dfs(idx, sum, tsum): global maxVal # sum: 데려가는 바둑이 총 무게 # tsum: 데려갈지 판단해본 바둑이 총 무게 if sum+ (t..
중복순열 구하기(DFS)
분석 풀이 import sys input=sys.stdin.readline n,m=map(int, input().split()) res=[0]*n total=0 def dfs(x): global total if x==m: for j in range(m): print(res[j], end=' ') total+=1 print() else: for i in range(1,n+1): res[x]=i dfs(x+1) dfs(0) print(total)
합이 같은 부분집합(DFS)
분석 풀이 """ N개의 원소로 구성된 자연수 집합 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} """ import sys input=sys.stdin.readline n=int(input()) list = list(map(int, input().split())) total=sum(list) def dfs(idx, sum): if sum>(total-sum)//2: # sum이 홀수인 경우가 있기 때문에 > 체크 return if idx==n: if sum==(total-sum): print("yes") sys.exit(0) # 종료 else: dfs(idx+1, sum+li..
부분집합 구하기(DFS)
분석 풀이 """ 1부터 자연수 N(1~10) 부분집합을 모두 출력 """ import sys input=sys.stdin.readline n=int(input()) def dfs(v): if v==n+1: for i in range(1,n+1): if ch[i]==1: print(i, end='') print() else: ch[v]=1 dfs(v+1) ch[v]=0 dfs(v+1) ch=[0]*(n+1) dfs(1)
[1991] 트리 순회
1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 분석 트리 순회(전위 순회, 중위 순회, 후위 순회), DFS 1. 전위순회 뿌리(root)를 먼저 방문 #전위순회 출력 : 1 2 4 5 3 6 7 def preorder(v): if v > 7: return else: print(v, end=' ') preorder(v * 2) preorder(v * 2 + 1) preorder(1) 2. 중위 순회 왼쪽 하위 트리를 방문 후 뿌리(root)를 karla.tistory.com 풀이 import sy..
[10829] 이진수 변환(DFS)
10829번: 이진수 변환 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000,000,000,000) www.acmicpc.net 풀이 n=int(input()) def DFS(x): if x == 0: return else: DFS(x//2) print(x%2, end='') DFS(n)
트리 순회(전위 순회, 중위 순회, 후위 순회), DFS, 재귀
1. 전위순회 뿌리(root)를 먼저 방문 #전위순회 출력 : 1 2 4 5 3 6 7 def preorder(v): if v > 7: return else: print(v, end=' ') preorder(v * 2) preorder(v * 2 + 1) preorder(1) 2. 중위 순회 왼쪽 하위 트리를 방문 후 뿌리(root)를 방문 # 중위순회 출력 : 4 2 5 1 6 3 7 def inorder(v): if v > 7: return else: inorder(v * 2) print(v, end=' ') inorder(v * 2 + 1) inorder(1) 3. 후위 순회 하위 트리 모두 방문 후 뿌리(root)를 방문 #후위순회 출력 : 4 5 2 6 7 3 1 def postorder(v):..
[1414] 불우이웃돕기 (MST, 문자열)
1414번: 불우이웃돕기 첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선 www.acmicpc.net 풀이 """ N개의 컴퓨터를 모두 서로 연결, 각각의 컴퓨터는 랜선으로 연결 기부할 수 있는 랜선의 길이의 최댓값 컴퓨터의 개수 N(1~50) 랜선의 길이 a~z: 1~26, A~Z: 27~52, (i,j)=0: 랜선이 없음 """ import sys input = sys.stdin.readline from queue import PriorityQueue n=int(input()) #컴퓨터개수 total=0 # 총 랜선 길이 pq = PriorityQueu..