전체 글 (168) 썸네일형 리스트형 백준 11437 LCA https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정� www.acmicpc.net LCA라는 새로운 알고리즘을 도입했다. Segtree를 이용해서 풀었는데 코드가 좀 지저분하다. LCA 알고리즘에 대한 공부를 하고, 그것을 연습하기에 좋은 문제라 생각한다. /* LCA */ #include #include #include #include #define pp pair #define MAX_NODE 50000 + 1 using namespace std; int N, max_.. 백준 2493 탑 C++ https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 �� www.acmicpc.net DP로 풀 수 있고 Stack으로도 풀 수 있다. 둘 다 어렵지 않은 풀이지만, Stack 풀이가 뇌용량을 덜 쓴다. 우선 Dp로 풀었다. 만약 탑이 6 4 5 7 3 순으로 배치되어있다면 답은 "0 1 1 0 4" 이다. 여기서 '5'를 잘 봐야하는데, 5는 일단 바로 앞의 값을 본다. '4'다. 본인보다 높이가 낮으므로 전파가 닿지않는다. 무식하게 할 경우 여기서 6을 보게 된다. 운 .. 백준 10868 최솟값 https://www.acmicpc.net/problem/10868 10868번: 최솟값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 www.acmicpc.net 세그먼트 트리를 활용하는 문제다. 문제를 읽다보면 대놓고 세그먼트 트리를 활용하라는 것 같다... /* 최솟값 */ #include #include #include #include using namespace std; void solve(); int seg_init(int s, int e, int node); int seg_find(int s, int e, in.. 이전 1 ··· 34 35 36 37 38 39 40 ··· 56 다음