꾸준하게 거북이처럼

import sys def pascalSum(res): temp = [] while len(res) != 1: for i in range(len(res)-1): temp.append(res[i] + res[i+1]) res = temp.copy() temp = [] return res[0] def DFS(L): global cnt, res if L == n: result = pascalSum(res) if result == F: for i in res: print(i, end= ' ') sys.exit(0) else: for i in range(1,n+1): if i not in res[:L]: res[L] = i DFS(L+1) if __name__ == "__main__": n, F = map(int..

def DFS(L): global cnt, res if L == m: for i in res: print(i, end= ' ') print() cnt += 1 else: for i in range(1,n+1): if i not in res[:L]: res[L] = i DFS(L+1) if __name__ == "__main__": n, m = map(int,input().split()) res = [0] * m cnt = 0 DFS(0) print(cnt) # 중복순열 구하기에서 중복만 뺀 것으로, 앞에서 선택한 수는 포함하지 않아야한다. # 나의 풀이: L 즉, 현재 레벨 전까지 선택한 수들은 제외하고 선택해야하므로, res[:L] 배열에 속하지 않은 # 수를 선택해서 순열을 만들어 나가는 방식으로 구..

def DFS(L): global res, min if sum(res) > M: return count = 0 for k in res: if k != 0: count += 1 if min count: min = count return else: for i in range(n): res[L] = coins[i] DFS(L+1) if __name__ == "__main__": n = int(input()) coins = list(map(int,input().split())) coins.sort(reverse=True) M = int(input()) res = [0] * M min = 21470000 DFS(0) print(min) ..

import sys input = sys.stdin.readline def DFS(L): global cnt if L == m: for k in range(m): print(res[k], end=' ') print() cnt += 1 else: for i in range(1,n + 1): res[L] = i DFS(L+1) if __name__ == "__main__": n, m = map(int,input().split()) cnt = 0 res = [0] * m DFS(0) print(cnt) # 중복순열이기 때문에 1 ~ n 까지 m개 뽑을 때까지 계속 반복해서 재귀 호출을 해야한다. => for문 n번 반복 # 첫 시작 호출은 루트로 출발하는 것이 항상 확실하다. 여기서는 0을 출발점으로 둔다. ..

def DFS(index, sum): global max if sum > C: return if index == N: if sum > max: max = sum else: DFS(index + 1, sum + arr[index]) DFS(index + 1, sum) if __name__ == "__main__": C, N = map(int,input().split()) arr = [] max = 0 for _ in range(N): arr.append(int(input())) DFS(0,0) print(max) # 나의 풀이 # 바둑이들을 무게 C가 넘지 않게 최대한 무겁게 트럭에 싣자. # DFS를 이용해서 매개변수를 sum으로 전달해서 C를 넘으면 return, max를 전역변수로 두어서 sum이 m..

a = [] def DFS(n): if n > 3: for i in a: print(i, end=' ') print() return else: a.append(n) DFS(n+1) a.pop() DFS(n+1) # ------^나의 풀이 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) if __name__ == "__main__": n = int(input()) ch = [0] * (n + 1) dfs(1) # ------^정답 풀이 # 원소가 1 2 3인 집합의 부분집합 구하기. # 나의 풀이 : ..

a = [] def DFS(n): if n > 3: for i in a: print(i, end=' ') print() return else: a.append(n) DFS(n+1) a.pop() DFS(n+1) # ------^나의 풀이 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) if __name__ == "__main__": n = int(input()) ch = [0] * (n + 1) dfs(1) # ------^정답 풀이 # 원소가 1 2 3인 집합의 부분집합 구하기. # 나의 풀이 : ..

이전 작성한 글에서 DFS의 활용과 백트래킹을 다루었는데, 14502 백준 문제와 연관이 있다. 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 구하고자 하는 것은 바이러스가 퍼지고 난 후, 최대 안전 영역이다. 처음에는 벽 세 개를 어떻게 뽑지? 생각이 들었다. 조합을 생각할 수 있는데 여기서 DFS 활용을 적용할 수 있다. 일단 벽을 세 개 세웠을 때 모든 경우에서 바이러스가 퍼지고 난 후 면적을 모두 구하고 비교하는 방식으로 문제를 풀 수 있다. 최대 조합이 64개 중 3개 뽑는 조합으로, 10만 보다 작은 수이..

14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 백준 14502번 문제를 풀면서 필요한 개념을 정리하고자 한다. DFS ( Depth First Search : 깊이 우선 탐색 ) 의 개념 그래프 전체를 탐색하는 방법 중 하나로, 시작 노드 부터 다음 branch로 넘어가기 전에 해당 branch를 완벽하게 탐색하는 방법. DFS의 활용 주로 역량 테스트에서 사용되는 방식으로, 1. 그래프를 모두 탐색 2. 특정 조합 구하기/순열 위 그림을 보면 DFS 알고리즘을 이용해서 집합 {1, 2, 3}의 모든 조합을 구할 수 있다..