mhy908의 PS 블로그 mhy908의 PS 블로그

1. Teleporters 각각의 텔레포터를 정점이라 두고, 적당히 간선을 연결하여 그래프를 형성할 것이다. 편의를 위해 각각의 텔레포터를 텔레포터로 들어가는 정점과, 텔레포터에서 나오는 정점의 2개로 분리하도록 하자. 즉 한 쌍의 텔레포터는 4개의 정점으로 표현된다. 또한 시작점과 끝점에도 정점을 각각 하나씩 만들어 주자. 이제 유향 간선으로 정점들을 이어줄 것인데, 각 정점을 2개로 분할하였기 때문에 각 정점의 indegree와 outdegree는 둘다 1이다. 시작점과 끝점은 각각 outdegree와 indegree가 1이다. 이러한 방법으로 이어준 그래프의 컴포넌트들의 모양을 관찰해보자. (1) 각각의 컴포넌트는 단순 사이클이거나 직선이다. pf) 시작점에서 끝점으로 항상 갈 수 있다는 문제의 조..

1. Type Printer 겨울학교에서 문자열 셋을 돌때 나왔던 문제. 간단히 주어진 문자들로 Trie를 구성한다음 트리 순회를 그리디하게 진행하면 된다. 각 노드별로 서브트리에 있는 노드중 가장 깊은 원소의 깊이(=서브트리의 높이)를 전처리한 뒤 그 값이 작은 자식노드쪽부터 재귀함수를 호출하면 된다. 시간복잡도는 Trie의 노드 개수로 O(NS)이다. (S는 각 문자열의 길이) 2. Fish 물고기의 뱃속에서 나올 수 있는 보석의 쌍의 개수를 구하는 문제이다. 이 문제에서 중요한 것은 중복되지 않게 이러한 쌍들을 잘 세주는 것인데, 그러기 위해 몇가지의 관찰을 하자. (1) 각 보석 종류에 대해 가장 길이가 긴 물고기에 대해서만 쌍을 세줘도 된다. pf) 조금만 생각해도 자명한 사실이다. 그보다 짧은..