동환아 공부해야지

1. 첫 번째 풀이(success): DFS'''Condition- A-B-C-D-E 가 되는 node가 있는가?Answer- 존재하면 1, 없으면 0 출력Approach- 모든 node를 root삼아 한번씩 dfs 돌려보면 될 것 같음 - 이때 depth가 5가 된다면 끝'''from sys import stdininput = stdin.readline# 입력n,m = map(int,input().split())graph = [[] for _ in range(n)]for _ in range(m): a,b = map(int,input().split()) graph[a].append(b) graph[b].append(a)# dfsvisited = [False] * ndef dfs(no..

1. 첫 번째 풀이(success): 백트래킹'''Condition- n개중 m개 고름- 중복해서 뽑을 수 있음- 오름차순Answer- 중복값 출력x>>>> 백트래킹으로 풀자'''def dfs(cnt, seq:list, before, lst:list): global visited, answer # 조건 확인 if cnt == m and tuple(seq) not in visited: answer.append(seq[:]) visited.add(tuple(seq)) return # 탐색 for i in range(before, n): num = lst[i] seq.append(num) dfs(cnt+1, ..

'''- 부등호를 만족하는 최대, 최소를 출력- 사용되는 숫자는 유니크해야함- 백트래킹으로하자'''def compare(before, cur, sign): return beforecurdef dfs(depth, s): global max_v, min_v, visited # 제일 처음 depth가 k+1이 되었을 때 -> 0부터 오름차순이므로 min이 됨 # 제일 마지막으로 depth가 k+1이 되었을 때 -> max가 됨 if depth == k+1: if len(min_v) == 0: min_v = s else: max_v = s return # 0부터 오름차순으로 탐색 for i in r..

난이도: 골드4분류: 그래프 이론, 그래프 탐색, 트리, 깊이 우선 탐색 key pointleaf node - leaf node는 불가능. leaf가 하나인 경우도 존재하고, parent - child의 거리가 더 먼 경우도 충분히 존재한다트리의 지름 안에 모든 다른 점들이 위치해있다. 따라서 어떤 점에서 탐색하든 상관없이 가장 멀리있는 정점을 고른다면, 그 점은 트리 지름 노드 중 하나이다그리고 트리 지름 노드에서 가장 먼 정점은, 또 다른 트리 지름 노드가 된다 fst approach (x)우선순위 큐를 사용cost가 높은 순서대로 차례대로 꺼냈을 때, 가장 먼저 나오는 두 개의 leaf node를 연결한 비용이 트리의 지름이다>>> fail, cost가 가장 높더라도 정답이 아닌 경우가 충분히 존재..

알고리즘 분류 : 그래프 이론, 트리 시간 복잡도 : . Try_1) Success queue를 사용하여 접근해보았다 ''' Condition - TL = 1s (약 2000만) - ML = 256mb (약 64*10만) - 2

알고리즘 분류 : 백트래킹, 브루트포스시간 복잡도 : O(N^N)'''Condition - TL : 1s (약 2000만) - ML : 256mb (약 64*10만) - 1