Coding Test

바둑이승차(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..

최단거리(다익스트라) vs 최소 신장 트리(크루스칼)

정리 다익스트라 크루스칼 용도 일대다 정점 간의 최소 거리 파악 최소 신장 트리(MST) 파악 중심 정점(Node) 간선(Edge) 모든 정점 방문 X O 구현 방법 우선 순위 큐 + dist[점화식] 우선 순위 큐 + Union-Find 시작점 출발점이 정해져 있는 경우 간선 가중치가 작은 것부터 큐에 넣는 시점 dist가 갱신 될 때 그 점에서 출발하는 간선을 큐에 넣음 모든 정점을 우선순위 큐에 넣고 시작 끝 점과 점 사이의 최단 거리를 찾고 나면 더이상 탐색하지 않음 최소신장 트리가 만들어 질 때까지 탐색 최소 임의의 두 점 간의 최소 거리를 구할 때 사용 최소 비용으로 모든 점을 다 이을 때 사용 임의의 두 점 간의거리 최소 보장 X 최단거리 알고리즘 그래프 최단거리 알고리즘 정리 및 비교 (다..

[11403] 경로 찾기 (플로이드-워셜)

11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 분석 최단거리를 구하는 문제가 아니기 때문에 플로이드-워셜 알고리즘에서 업데이트 부분 수정 S와 E가 모든 중간 경로(K) 중 1개라도 연결되어 있다면 S와 E는 연결 노드로 저장 풀이 """ 모든 정점 (i,j) i에서 j로 가는 경로가 있는지 없는지 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력 """ import sys # 인접행렬 크기 n = int(input()) # 인접행렬 d = array = [[sys.maxsize for j in range(n)] f..