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

[Python]최소공통조상 백준 13511

문제 https://www.acmicpc.net/problem/13511 앞의 문제들과 동일하게 DP를 이용해 2^k 번째 부모노드와 그 부모노드까지의 거리를 구하고 최소공통조상 노드를 구하여 각 쿼리들을 해결하면된다.u->v로 가는 비용은 u->lca까지의 거리와 v->lca까지의 거리를 구해서 더하여 구하였고u->v로 가는 경로에 존재하는 정점중 k번째 노드는 u->lca까지의 노드개수가 k보다 크다면 u의k번째 부모노드를 구하면되고그렇지 않다면 k에서 u->lca 까지의 노드 개수를 빼주고 이값을 v->lca에서 뺀 값 k2라고 했을때 v의 k2번째 부모노드를 구하면된다.논리적으로는 틀린것이 없다고 생각하였는데 구현해보니 틀렸다.예외적인 부분들을 몇몇 수정해 봤지만 계속 틀렸다. 테스트 케이스도 바..

2020. 4. 22. 21:16
알고리즘(python)/탐색

[Python]최소공통조상 백준 3176

문제 https://www.acmicpc.net/problem/3176 이 문제는 최소공통조상을 구해서 각 도시에서 최소공통조상까지 가장짧은 도로의 길이와 가장긴 도록의 길이를 구하는 문제이다.문제에서 볼 수 있듯이 모든 도시의 쌍에 그 도시를 연결하는 유일한 통로가 있다고 하였기 때문에 사이클이 없는 트리 구조이다.먼저 입력을 통해 얻은정보로 DFS를 통해 아무노드나 루트로 하는 트리 구조를 만들어준다.만들어진 트리를 바탕으로 희소테이블도 만들어준다.이때 최소값 최대값도 같이 저장시켜주는게 저번 문제와 다른 점이다.2^k번째 부모노드와 그 부모노드까지의 가장짧은 도로와 가장 긴 도로의 길이도 같이 저장해준다.이렇게 만들어진 희소테이블을 이용해 두 도시의 레벨을 맞춰주고 최소공통조상을 찾는다.이때도 가장..

2020. 4. 21. 23:17
알고리즘(python)/탐색

[Python]최소공통조상 백준 11438

문제 https://www.acmicpc.net/problem/11438 이전 문제에서 배웠던 희소테이블을 이용해 구해야한다.각 노드의 2^k번째의 부모노드를 저장한다.i의 2^k번째 부모노드는 희소테이블 DP[i][k]에 저장한다.이렇게 2^k번째의 부모노드를 구해놓고 이제 두 노드의 레벨을 맞춘 뒤 최소공통조상을 구하면 된다.레벨을 맞출때는 희소테이블과 비트연산의 and를 통해 찾아간다.레벨을 맞추고 나면 최소공통조상도 희소테이블 이용해 구한다.최소공통조상을 찾는 과정은 이분탐색과 조금 비슷하다.2^k 번째 부모노드가 같다면 2^k 번째 이하에서 최소공통조상을 찾을수있다.2^k-1번째 부모노드가 처음으로 달라지는 경우 2^(k-1) 와 2^k 사이에 최소공통조상이 있다고 볼수있다.이렇게 다시 찾아가게..

2020. 4. 20. 20:17
알고리즘(python)/탐색

[Python]최소공통조상 백준 17435

문제 https://www.acmicpc.net/problem/17435 sparsetable을 이용한 문제이다.http://www.secmem.org/blog/2019/03/27/fast-LCA-with-sparsetable/http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220793361738 두 사이트를 읽어보면 이해하기 편하다.i=시작노드k=연산횟수라고 생각했을때f^4(3)=f(f(f(f(3))))이다. 5 3 3 5 4 3 5 1 1 2 1 11 3 1000 4 5 1 문제의 예제를 살펴보자.f^2(1)=5 이다.f^4(1)=5 이다.f^4(1)=f^2(5)와 같다.이 원리를 이용하면 f^2(5)=5 이다.f^8(1)=?f^8(1)=f^4(f^4..

2020. 4. 19. 00:38
알고리즘(python)/탐색

[Python]최소공통조상 백준 3584

문제 https://www.acmicpc.net/problem/3584 최소공통조상(Lowest common ancestor)LCA(최소공통조상)은 영어 해석 그대로 최소 공통 조상을 찾는 알고리즘이고, 두 정점 u, v(혹은 a, b)에서 가장 가까운 공통 조상을 찾는 과정을 말한다.정확히 무엇을 뜻하는 지는 아래 사이트를 통해 보면 쉽게 알 수 있다.https://www.crocus.co.kr/660문제 해결은 각 노드의 부모노드들을 모두 저장한뒤 루트노드부터 차례대로 내려오며 비교하여 같지 않은 노드가 나올때까지 반복한다. 처음으로 같지않은 노드가 나왔을때 그 노드의 부모가 최소공통조상이라고 볼 수 있다. 1234567891011121314151617181920212223242526272829303..

2020. 4. 15. 00:19
알고리즘(python)/정렬

[Python]위상정렬 백준 1766

문제 https://www.acmicpc.net/problem/1766 위상정렬읠 하는것은 동일하다. 위상정렬의 특성상 따라 여러가지 출력값을 가질수 있다. 이 문제는 한가지 값만 나올수 있도록 조건이 있다.쉬운 문제를 먼저 즉 진입차수가 0일때도 순서가 있다.최소힙을 이용하여 가장 쉬운(문제 번호가 작은) 문제부터 출력 할수 있도록 해주면 된다. 1234567891011121314151617181920212223242526272829303132import sysimport heapq N,M=map(int,sys.stdin.readline().split())tree=[[] for _ in range(N+1)]inDegree=[0 for _ in range(N+1)] q=[]#문제 순서for _ in ra..

2020. 4. 14. 14:45