Coding Test/Search
경로탐색(DFS)
[1260번] DFS, BFS 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. karla.tistory.com """ 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력 5 9 1 2 1 3 1 4 2 1 2 3 2 5 3 4 4 2 4 5 """ import sys input = sys.stdin.readline n, m = map(int, input().split()) visited=[False]*(n+1) visited[1]=True # res=list() # res.append(1) cnt=0 d =..
순열 추측하기(DFS, 파스칼 삼각형, 이항계수)
분석 이항계수 리스트 선언 풀이 """ 가장 윗줄에 1부터 N까지의 숫자, 둘째 줄부터 위의 두개를 더한 값이 저장 N: 4, 가장윗줄: 3 1 2 4 3 1 2 4 4 3 6 7 9 16 N(1~10)과 가장 밑에 있는 숫자(F)가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하기 답이 존재 하지 않는 경우는 입력으로 주어지지 않는다 """ import sys input=sys.stdin.readline n,f=map(int,input().split()) visited=[False]*(n+1) p=[0]*n # 이항계수 b=[1]*n for i in range(1,n): b[i]=b[i-1]*(n-i)//i def dfs(x, sum): global visited if x==n and sum==f: fo..
동전 교환(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)
[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)
[1920번] 수 찾기 (이진탐색)
1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net # 자연수 N(1~100,000) n = int(input()) # A[] N개의 정수 a = list(map(int, input().split())) # 자연수 M(1~100,000) m = int(input()) # M개의 수 list = list(map(int, input().split())) a.sort() for i in range(m): find = False target = list[i] start =..