알고리즘(python)/자료구조 검색 결과
22 개의 검색 결과가 있습니다.
알고리즘(python)/자료구조

[Python]트리 백준 5639

문제 https://www.acmicpc.net/problem/5639 이번엔 이진트리이다.루트와 모든 원소만 알고있다면 트리를 구성할수있다.전위순회의 가장 첫원소는 루트이다.트리를 구한뒤 후위순회를 통해 출력해보자.입력방식은 조금 특이하다. 예외처리를 이용해 처리하자. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051class Node: def __init__(self,item): self.val=item self.left=None self.right=None class BinaryTree: def __init__(self): self.head=Node(None) def insert(s..

2020. 3. 21. 11:21
알고리즘(python)/자료구조

[Python]트리 백준 2263

문제 https://www.acmicpc.net/problem/2263 답을 구하는 방법이 바로 떠오르지 않는다.트리를 그려보고 전위 중위 후위순회를 각각 구하고 비교해 봐야겠다.먼저 이전 문제애 사용던 코드를 활용해 각각의 전위 중위 후위순회를 구해보았다. A B CB . FC D ED . .E . .F G HG . .H . . ABFGHCDEBGFHADCEGHFBDECA 후위순회는 마지막 노드가 루트이다.중위순회는 부모노드를 기준으로 나눌수 있다.먼저 후위순회 부모노드를 구하고 중위순회를 통해 나눈것을 반복하면 트리를 구할수있다.BGFH A DCEGHFB DEC AABGFH DCE 먼저 이렇게 나누고 나면후위순회의 나누어진 그룹의 가장 오른쪽 노드들은 부모노드가 된다.다시 BC를 부모노드로 나눠보자B..

2020. 3. 17. 23:06
알고리즘(python)/자료구조

[Python]트리 백준 1991

문제 https://www.acmicpc.net/problem/1991 순회는 이전에 풀어봤던 기억이있다.그대로 구현해 주면 되는데 문자열 입력받고 출력하는거라 문자를 아스키코드로 변환해주는 ord함수를 사용하였다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344import sys N=int(sys.stdin.readline())#이진트리tree=[[] for _ in range(N+1)]for _ in range(N): s=list(map(str,sys.stdin.readline().split())) c=ord(s[0])-64 for i in range(1,3): tree[c].append(ord(s[i])-..

2020. 3. 16. 13:30
알고리즘(python)/자료구조

[Python]트리 백준 1967

문제https://www.acmicpc.net/problem/1967 이전 문제와 동일하다.루트노드가 정해져 있지만 중요하지않다.꼭 루트노드를 지나는 것은 아니기 때문에 앞문제와 마찬가지로 임의의 노드에서 DFS를 통해 최장길이를 이루는 노드를 구한뒤그노드에서 다시 DFS를 통해 가장 긴 길이를 구하면 트리의 지름이 된다.이번문제는 sys.setrecursionlimit(10**9)를 통해 재귀 최대 깊이를 설정해 주지 않으면 런타임 에러가난다. 123456789101112131415161718192021222324252627282930313233343536373839import syssys.setrecursionlimit(10**9) V=int(sys.stdin.readline()) matrix=[[]..

2020. 3. 15. 23:42
알고리즘(python)/자료구조

[Python]트리 백준 1167

문제https://www.acmicpc.net/problem/1167 트리의 지름을 구하라는 문제이다.가장 먼저 생각할수 있는 건 모든 노드에서 BFS나 DFS를 통해 모든 길이를 구하면 그 중 가장 긴 길이가 노드의 지름이 될것이다.하지만 시간복잡도가 너무크다.트리의 지름을 구하는 방법이 따로있다.노드x에서 가장 먼 노드를 y라고 했을때 y는 지름을 이루는 노드중 하나이다.증명은 이 블로그를 참고하면 이해하기 더욱 쉬울것이다.https://blog.myungwoo.kr/112 이제 구현해보자.임의의 노드x에 대해 DFS(x)에서의 최장거리를 이루는 y를 구하고 DFS(y)를 구해 최장길이를 구하면 노드의 지름을 구할수 있다. 1234567891011121314151617181920212223242526..

2020. 3. 15. 20:51
알고리즘(python)/자료구조

[Python]트리 백준 11725

문제 https://www.acmicpc.net/problem/11725 트리 구조(tree 構造, 문화어: 나무구조)란 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 간단하게는 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다.트리에서 최상위 노드를 루트 노드(root node 뿌리 노드[*])라고 한다. 또한 노드 A가 노드 B를 가리킬 때 A를 B의 부모 노드(parent node), B를 A의 자식 노드(child node)라고 한다. 자식 노드가 없는 노드를 잎 노드(leaf node 리프 노드[*])라고 한다. 잎 노드가 아닌 노드를 내부 노드(internal node)라고 한다.트리에 대한 정의부터 알아봤다.이제 문제로 들어가보자 DFS로..

2020. 3. 15. 11:32