알고리즘(python)/기본 검색 결과
50 개의 검색 결과가 있습니다.
알고리즘(python)/기본

[Python]트리에서의 동적 계획법 백준 1949

문제 https://www.acmicpc.net/problem/1949 트리의 독립집합을 묻는 문제이다.트리에서의 DP문제는 독립집합을 묻는 문제가 대부분인거 같다.2213번 문제의 풀이를 그대로 가져와도 사용하여도 된다. 추적하는 부분만 빼면 풀이법은 동일하다. 123456789101112131415161718192021222324252627282930import syssys.setrecursionlimit(10**9) n=int(sys.stdin.readline())node_value=[0]+list(map(int,sys.stdin.readline().split()))Tree=[[] for _ in range(n+1)]DP=[[0,0] for _ in range(n+1)] for _ in range(..

2020. 3. 29. 15:44
알고리즘(python)/기본

[Python]트리에서의 동적 계획법 백준 2533

문제 https://www.acmicpc.net/problem/2533 가장 많은 독립집합을 찾는 문제라고도 볼 수 있을거 같다.가장 많은 독립집합을 구한 후 독립집합을 연결하는 노드가 얼리아답터라고 볼수있다.즉 가장 많은 독립집합을 만드는 경우를 찾은 후 전체 노드의 수에서 빼주면 얼리 아답터의 최소수가 된다.이전문제처럼 DFS를 사용해 가장 하단의 노드부터 차례대로 해당노드가 포함되었을때와 포함되지 않았을때 독립집합이 가장 많이 경우를 DP를 통해구하면 된다. 1234567891011121314151617181920212223242526import syssys.setrecursionlimit(10**9) N=int(sys.stdin.readline())Tree=[[] for _ in range(N+1..

2020. 3. 29. 14:01
알고리즘(python)/기본

[Python]트리에서의 동적 계획법 백준 2213

문제 https://www.acmicpc.net/problem/2213 트리에서 DP를 사용하는 문제이다.DFS 후위순회를 통해 가장 아래의 노드부터 현재노드가 포함되었을때와 그렇지 않을때의 값을 둘다 저장하면서 루트노드까지 올라가는 방식으로 구현하였다.재귀를 통해 구현하였으며 독립집합의 최대값을 구한뒤 그 값을 이용하여 추적하는 함수도 따로 구하였다.예제를 살펴보면710 30 40 10 20 20 701 22 34 34 56 26 7 먼저 루트를 1로하는 트리로 만들어 준 뒤 후위순회를 통해 노드 순서를 살펴보면 5->4->3->7->6->2->1 순으로 DP를 수행하면된다.5번노드의 DP값은 5번노드가 포함되었을때 DP[5][0]=20,5번노드가 포함되지 않았을때 DP[5][1]=0을 저장한다. 4번..

2020. 3. 29. 02:13
알고리즘(python)/기본

[Python]트리에서의 동적 계획법 백준 15681

문제 https://www.acmicpc.net/problem/15681 친절하게 사이트에 가보면 아래 풀이까지 나와있다.참고하지 않아도 될정도로 간단하긴 하지만 기본적인 부분부터 잘 설명되어 있다. 12345678910111213141516171819202122232425262728293031import syssys.setrecursionlimit(10**9) N,R,Q=map(int,sys.stdin.readline().split())Tree=[[] for _ in range(N+1)]#트리 구성node_count=[0] * (N+1)#노드 개수check=[True for _ in range(N+1)]#방문여부 for _ in range(N-1): U,V=map(int,sys.stdin.readlin..

2020. 3. 27. 23:52
알고리즘(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
알고리즘(python)/기본

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

문제 https://www.acmicpc.net/problem/9019 문제는 복잡해보이지만 읽어보면 굉장히 단순하다는것을 알수있다.큐를 이용하여 각 단계마다 D,S,L,R에 해당하는 연산의 결과를 넣어주고 B가 나올때 까지 돌리면된다.큐에 넣을때 이전연산값에 각단계의 연산값을 추가하여 넣어주었으며 중복계산을 방지하기위해 0~9999까지의 연산을 한번이라도 했으면 배열로 체크를 하여 다시 연산하지 않도록해주었다. 이전단계에서 어떤연산을 통해 왔는지만 저장하게 된다면 D연산이나 여러가지경우에서 문제가 생길거같다. 파이썬으로는 통과 하지 못하였고 pypy3를 통해 통과하였다. 123456789101112131415161718192021222324252627282930313233343536373839impor..

2020. 3. 14. 01:16