Total

[13023] ABCDE(친구관계 파악하기, DFS, 백트래킹, 그래프)

13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 분석 [1260번] DFS, BFS 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. karla.tistory.com 풀이 import sys input=sys.stdin.readline sys.setrecursionlimit(10000) n,m=map(int,input().split()) # 사람수, 친구관계수 list = [[] for _ in range(n+1)] for _ in..

[2023] 신기한 소수(DFS, 백트래킹)

2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 분석 자리수가 한 개인 소수 2,3,5,7부터 탐색 시작 자릿수가 두개인 현재수*10+a를 계산하여 소수인지 판단, 소수라면 재귀 함수로 자릿수를 하나 늘림 a가 짝수인 경우는 항상 2를 약수로 가지므로 가지치기로 a가 짝수인 경우 제외 자릿수를 n까지 확장했을 때 그 값이 소수라면 해당 값 출력 풀이 """ 소수 7331 : 733, 73, 7 소수 (왼쪽부터 1,2,3,4 자리 모두 소수) n(1~8)자리 숫자 중 신기한 소수 찾기 """ impo..

수들의 조합(DFS)

import sys input=sys.stdin.readline n,k=map(int,input().split()) arr=list(map(int, input().split())) m=int(input()) def dfs(x,s,sum): global cnt if x==k: if sum%m == 0: cnt += 1 else: for i in range(s,n): dfs(x+1,i+1,sum+arr[i]) cnt=0 dfs(0,0,0) print(cnt)

중복순열 구하기(itertools 라이브러리)

중복순열 구하기(DFS / itertools 라이브러리) 분석 풀이 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 karla.tistory.com """ 1부터 N까지 번호가 적힌 구슬 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열 하는 방법을 모두 출력 N(3

수들의 조합(itertools 라이브러리)

수들의 조합(DFS) import sys input=sys.stdin.readline n,k=map(int,input().split()) arr=list(map(int, input().split())) m=int(input()) def dfs(x,s,sum): global cnt if x==k: if sum%m == 0: cnt += 1 else: for i in range(s,n): dfs(x+1,i+1,sum+arr[i]) cnt=0 dfs(0,0,0) print(cnt) karla.tistory.com """ N개의 정수 K개를 뽑는 조합의 합이 임의의 정수 M의 배수인 개수 는 몇 개가 있는지 출력 5개의 숫자 2 4 5 8 12 3개를 뽑은 조합의 합이 6의 배수인 조합을 찾으면 4+8+12 2..

순열 추측하기(itertools 라이브러리)

순열 추측하기(DFS, 파스칼 삼각형, 이항계수)분석 이항계수 리스트 선언 풀이 """ 가장 윗줄에 1부터 N까지의 숫자, 둘째 줄부터 위의 두개를 더한 값이 저장 N: 4, 가장윗줄: 3 1 2 4 3 1 2 4 4 3 6 7 9 16 N(1~10)과 가장 밑에 있는 숫자(F)가 주어져 있karla.tistory.com  import itertools as itimport sysinput=sys.stdin.readlinen,f=map(int,input().split())visited=[False]*(n+1)p=[0]*n# 이항계수b=[1]*nfor i in range(1,n): b[i]=b[i-1]*(n-i)//i# 순열 구하기a=list(range(1,n+1))for tmp in it.permu..

경로탐색(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 =..

인접행렬(가중치 방향그래프)

그래프의 표현 및 비교 (간선 리스트, 인접 행렬, 인접 리스트) 간선 리스트 인접 행렬 인접 리스트 중심 간선 노드 노드 시간복잡도 - 느림 빠름 구조 [] d[시작노드][종료노드] d[시작노드] 입력 (시작노드 ,도착노드, 가중치) 가중치 (도착노드, 가중치) 알고리 karla.tistory.com """ 첫째 줄에는 정점수 n(2~20), 간선수 m m줄 연결정보와 거리비용 6 9 1 2 7 1 3 4 2 1 2 2 3 5 2 5 5 3 4 5 4 2 2 4 5 5 6 4 5 """ import sys input = sys.stdin.readline n, m = map(int, input().split()) d = [[0 for j in range(n)] for i in range(n)] for i..

조합 구하기(DFS)

분석 매개변수 s : 가지를 받는 첫번째 수(for문 시작 숫자) 풀이 """ 1~N 번호 구슬, M개 뽑는 방법의 수 출력 N(3

순열 추측하기(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..