백준

Solution 건물순서 X -> Y가 Input으로 주어지는데 Adjacency List에는 X <- Y의 형태로 저장 승리하기 위해 건설해야 할 건물의 번호 W를 start node로 생각 건설시간이 가장 긴 W에서 어떤 노드 E까지

Solution - MST 알고리즘(Kruskal, Prim) 중 Kruskal Algorithm을 사용 - Kruskal Algorithm 중 cycle의 여부는 Union-Find를 통해 확인 - 최적화를 통해 Find 연산의 시간복잡도를 낮춤

Solution 부분수열의 합을 구하는 모든 경우의 수를 고려해야 한다. → Backtracking time limit 발생 N개의 정수로 이루어진 수열을 N/2개의 정수로 이루어진 배열 & N-(N/2)개의 정수로 이루어진 배열로 나누어서 생각

완전 탐색으로 이 문제를 해결하려면 O(N!)의 시간이 걸려 time limit이 발생하지만 겹치는 경우의 수가 다수 발생하여 memoization 구현시 시간 제한안에 문제를 해결할 수 있다.

Solution 주어진 M개의 input으로 그래프를 만들면 DAG가 된다. Topological Sorting : 어떤 일들의 순서(줄 세우기)를 나타내는 알고리즘 Incoming Edge가 0인 Node를 queue에 push한다.

지도 전체를 탐색해야 하므로 BFS를 기본으로 사용하였다. 호출할 수 있는 BFS 함수의 시작 위치가 일정하지 않으므로 지도를 약간 변형해 일정하게 BFS(0, 0)을 호출하여 답을 구하였다.

처음엔 어떤 문자열을 팰린드롬으로 분할하여 나타낼 수 있는 집합의 경우의 수를 묻는 문제로착각하였다. 그러나 최소 몇 개의 팰린드롬으로 문자열을 표현할 수 있는 지를 묻는 문제였다.문자열이 ABACABA인 경우 답은 1이다.

조건 0에서 9가 모두 등장하는을 무시하고 길이가 N인 계단 수를 먼저 고려해보았다. DFS함수에 Memoization을 적용, 2차원 배열을 이용하여 문제를 해결할 수 있다.

남아있는 모든 전깃줄이 서로 교차하지 않는 조건은 LIS(Longest Increasing Sequence)를 찾고 나머지 전깃줄은 없애는 경우와 같다.

MST 알고리즘의 시간복잡도는O(ElogV). 모든 행성 간의 터널 연결 비용을 구하려면 O(N^2). 다른 방식의 접근 필요

N≤40000, M≤10000, 시간 제한이 1초이므로 시간복잡도는 O(MlogN)이어야 한다. 입력받은 두 노드의 공통 조상을 찾고 각 노드에서 공통 조상까지의 거리를 구하는 방식으로 이 문제를 해결할 수 있다.

분할 정복을 이용한다면 문제를 O(NlogN)안에 해결할 수 있다. 2차원 평면을 x축 중심선을 기준으로 똑같은 두 평면으로 나눠보자.

처음에는 최소 거리의 경찰차만을 선택하는 Greedy 알고리즘으로 문제를 해결할 수 있을 것으로 생각. 하지만 그리디 알고리즘으로는 거리의 합의 최솟값을 얻을 수 X. 완전탐색을 적용하돼 Dynamic Programming을 통해서 시간 내에 문제를 해결 가능