728x90 반응형 dfs17 [백준] 5639번: 이진 검색 트리 - python https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 아이디어 순회와 같은 문제는 DFS로 풀어야겠다고 생각. 입력을 받은 다음 만약 루트, 루트보다 클 경우, 그 중간 이 3개로 분리해서 나누어 재귀함수로 돌리면 해결이 된다. 만약 전위, 중위로 하고 싶으면 print의 위치를 위, 중간 으로 변경하면 가능한 것을 확인 할 수 있다. import sys sys.setrecursionlimit(10**9) arr = [] while Tr.. 2024. 4. 12. [백준] 1991번: 트리 순회 - python https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 아이디어 인덱스 값이 문자열이기 때문에 dict 형태로 저장한다. 그 후 학교에서 배운 전위, 중위, 후위순회로 DFS로 탐색을 진행하면서 출력을 뽑아낸다. n = int(input()) tree = {} for i in range(n): root, left, right = input().split() tree[root] = [left, right] def preorder(v): if .. 2024. 4. 9. [백준] 15666번: N과 M (12) - python https://www.acmicpc.net/problem/15666 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 드디어 마지막 N과 M 시리즈. 배우는게 많은 시리즈였다. 아이디어 중복제거 -> 인덱스 반환 -> 재귀 def DFS(L, s): if L == m: for i in range(m): print(res[i], end=" ") print() else: remember = 0 for i in range(s, n): if remember != arr[i]: res[L] = arr[i] rememb.. 2024. 4. 9. [백준] 15665번: N과 M (11) - python https://www.acmicpc.net/problem/15665 15665번: N과 M (11) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 아이디어 중복을 허용하지 않고 사전 순으로 진행. 아까와 부분집합과는 다르게 뿌리를 펼치면서 상태트리 값이 중복인지만 체크하면 됨으로 remeber 변수에 arr[i]을 저장시켜 중복을 제거할 수 있도록 설계. def DFS(L): if L == m: for i in range(m): print(res[i], end=" ") print() else: remember = 0 for i in ra.. 2024. 4. 9. 이전 1 2 3 4 5 다음 728x90 반응형