전체 글 썸네일형 리스트형 BOJ)2623 음악프로그램 문제: icpc.me/2623 음악프로그램의 출연 순서의 리스트가 주어졌을 때 모든 리스트를 만족시키도록 출연 순서를 출력하는 문제이다. 만약 모든 리스트를 만족할 수 없는 경우 0을 출력하면 된다. 우리는 출연 순서가 A->B->C 라면 A->B / B->C의 방향으로 간선을 연결해 준 뒤 topology를 구해줌으로서 리스트를 구할 수 있다. 이때 모든 리스트를 만족할 수 없는 경우는 사이클이 생기는 경우로서 그래프의 사이클 여부를 체크해줌으로서 확인 가능하다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include #include #include #include #define MA.. 더보기 LCA(Lowest Common Ancestor) 1개 이상의 노드로 구성 된 사이클이 없는 그래프를 트리라고 합니다. 우리는 트리에서 정의되는 LCA(Lowest Common Ancestor)에 대해서 얘기해 보려 합니다. LCA를 직역하면 최소 공통 조상(?) 정도의 뜻으로 해석되며 두 정점에서 (자신을 포함한)조상들을 거슬러 올라갈 때 처음으로 공통되게 만나는 정점을 지칭합니다. 예를 들기 위해 다음과 같은 트리가 존재한다고 합시다. 이 트리에서 6번 정점과 10번 정점의 LCA를 구하면 다음과 같이 2번 정점이 6번 정점과 10번 정점의 LCA가 됩니다. 이번에는 7번 정점과 10번 정점의 LCA를 구해보겠습니다. 다음과 같이 1번 정점이 7번 정점과 10번 정점의 LCA가 됩니다. 자, 이제 어느정도 LCA의 정의에 대한 감이 오시나요? 마지막.. 더보기 BOJ)11438 LCA 2 문제:icpc.me/11438 이 문제는 LCA (BOJ 11437) 의 풀이도 포함한다. 루트의 번호가 1번인 N개의 정점으로 이루어진 트리가 존재할 때 두 노드의 쌍 M이 주어질 때 두 노드의 LCA를 구하는 문제이다. 여기서 LCA(Lowest Common Ancestor)란 직역하면 최소 공통 조상(?) 이다. 즉 트리의 두 노드가 주어졌을 때 서로의 조상을 거슬러올라갔을 때 가장 먼저 만나는 정점이 LCA가 된다. LCA를 구하는 방법으로 두 노드의 높이(깊이)를 맞춘후에 한칸씩 올라가며 조상이 같아질 때까지 비교하는 방법이 있다. 하지만 이방법은 한번의 쿼리를 처리할 때 O(N)의 시간복잡도를 가지므로 LCA 2문제 같이 M과 N이 10만이면 O(N*M)으로 TLE를 피하기 힘들것이다. 그래서.. 더보기 이전 1 ··· 91 92 93 94 95 96 97 ··· 118 다음
