알고리즘(python) 검색 결과
179 개의 검색 결과가 있습니다.
알고리즘(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
알고리즘(python)/기본

[Python]동적계획법과 최단거리 역추적 백준 11779

문제 https://www.acmicpc.net/problem/11779 다익스트라 알고리즘을 이용해 최소비용을 구하는문제에서 경로를 출력하는것이 추가되었다.최소힙을 통해 다익스트라를 구현하였으며 result 배열에 이전에는 최소비용만 저장하였다면 이번에는 그경로까지 저장하였다.result에 모든 경로를 저장 하는방법과 이전 노드들을 저장하여 역추적하는 방법이 있다.이번에 역시 두가지 방법 모두 구현해보았다. 1234567891011121314151617181920212223242526272829303132333435363738394041import sysimport heapq n=int(sys.stdin.readline())#정점개수m=int(sys.stdin.readline())#간선개수 G=[[] ..

2020. 3. 14. 21:07