Solved.ac/Class 55 [BOJ] 백준 11437번: LCA www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정� www.acmicpc.net LCA는 최소 공통 조상 (Lowest Common Ancestor)로 두 노드를 잇는 가장 짧은 경로 중 깊이가 가장 얕은 노드입니다. 아래 트리에서 빨간 노드와 하늘색 노드의 LCA는 초록색 노드가 됩니다. "트리 노드의 부모 노드는 유일하므로 루트를 향해 거슬러 올라가면서 가장 처음으로 공통된 노드를 찾자!" 아이디어를 기반으로 좀 더 빠르게 위로 올라갈 수 없을까 하는 고민이 생기게 됩니다. 효율.. 2020. 9. 22. [BOJ] 백준 2467번: 용액 www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net -10억~10억 사이의 용액의 특성값이 오름차순으로 주어지며, 주어진 특성값 중 서로 다른 용액 A, B를 선택했을때 특성값의 합이 0에 가까운 조합을 출력하는 문제입니다. 예를 들어 -98 1 2 97 의 네 가지 용액이 주어진다면 -98과 97의 특성값을 같는 두 용액을 선택하는 것이 답이 됩니다. 즉 절대값이 가장 작은 조합을 고르는 문제로 생각할 수 있습니다. i번째 용액을 A로 고정시키면, 용액 .. 2020. 9. 22. [BOJ] 백준 2098번: 외판원 순회 TSP (traveling salesman problem) 로 잘 알려진 외판원 순회문제는 NP-Hard 문제로, 마을의 수 n에 대해 다항식의 형태로 복잡도가 계산될 수 없다. 그래서 N의 개수가 매우 적고, 비트마스크를 사용하여 방문한 마을을 1로 표기하여 001011 처럼 1,2,4 번째 마을을 방문했다를 표현할 수 있다. TSP는 시작점을 어느 마을로 하든 동일한 값이 나오기 때문에 시작 마을을 인덱스 0으로 편의상 둔다. if (state == (1 2020. 6. 25. [BOJ] 백준 1509번: 팰린드롬 분할 Class 5에는 대부분 DP로 구성된 것 같네요 recv(i)를 i번째 문자부터 시작했을때 가능한 최소 팰린드롬 수 DP[i]를 찾는 함수로 정하면 i = e) { return pal[s][e] = 1; } int& ret = pal[s][e]; if (~ret) return ret; ret = 0; if (str[s] == str[e]) { return ret = ispal(s + 1, e - 1); } return ret; } int recv(int node) { if (node == n) { return 0; } int& ret = dp[node]; if (~ret) return ret; ret = 2e9; for (int i = node; i < n; i++) { if (ispal(node, i.. 2020. 6. 25. 이전 1 2 다음
