1. 문제 정보 BOJ 12844 - XOR Platinum 3 2. 풀이 이 문제는 전형적인 세그먼트 트리(Segment Tree)와 레이지 프로파게이션(Lazy Propagation) 구현에 XOR 개념을 살짝 얹은 문제입니다. 세그먼트 트리와 레이지 프로파게이션의 원리를 이해하고 있고, XOR의 성질을 알고 있다면 어렵지 않게 풀 수 있는 문제입니다. 이 문제에서 활용하는 XOR의 기본 성질은 다음과 같습니다. 1. 같은 수를 XOR하면 0이다. 2. 어떤 수 X와 0을 XOR 하면 X이다. 어려운 XOR 개념이 사용되는 것이 아니고, XOR을 배우면 가장 처음 배우는 성질을 활용하는 문제입니다. 다른 레이지 프로파게이션 문제와 다른 점은 레이지 프로파게이션 배열을 업데이트 할 때 XOR의 성질을..

안녕하세요, 이번 게시물에서는 트리에서의 다이나믹 프로그래밍 특정 유형을 풀이하는 방법을 다뤄보려고 해요. 이 게시물에서 다루는 풀이를 적용하기 위해서는 문제 상황이 아래와 같아야 해요. 1. n개의 정점과 n - 1개의 간선으로 이루어진 트리이어야 한다. 2. n2개의 모든 정점의 쌍인 (i, j)에 대하여 두 개의 정점 (i, j) 최단 거리의 총합을 O(n)에 구해야 한다. (최단 거리는 꼭 가중치의 합이 아니어도 된다. 가중치의 곱이 될 수도 있다.) 위 조건을 만족시키는 문제 네 개 정도에 적용해보았는데, 모두 적용할 수 있었어요. BOJ 1289 - 트리의 가중치 Platinum 3 BOJ 20188 - 등산 마니아 Platinum 5 BOJ 7812 - 중앙 트리 Platinum 5 BOJ ..

1. 문제 정보 BOJ 1693 - 트리 색칠하기 Platinum 2 2. 풀이 쉬운 듯 어려운 듯한 문제였습니다. 반례를 못 찾았다면 못 풀었을 것 같습니다. 그래도 예시가 친절해서 삽질을 안 할 수 있었던 문제였습니다. [접근 1] 무조건 두 가지 색깔로 칠하는 게 최적의 해 아닐까? 아래는 문제에서 주어진 트리를 시각화 한 그림입니다. 매우 다행히도 제 첫 번째 접근이 틀렸음을 예시가 말해주고 있어서 바로 다른 풀이로 틀 수 있었습니다. 1과 2로 모든 정점을 색칠한다면 차수에 따라 색깔이 칠해지게 되고, 루트 정점에 1이 칠해지는 경우와 2가 칠해지는 경우 두 가지 밖에 없습니다. 위 그림에서 두 가지 경우를 모두 볼 수 있는데, 둘 다 최적의 해가 아님을 쉽게 파악할 수 있습니다. 주어진 예시에..

1. 문제 정보 BOJ 1725 - 히스토그램 Platinum 5 BOJ 6549 - 히스토그램에서 가장 큰 직사각형 Platinum 5 2. 풀이 이 문제는 스택 알고리즘의 어려운 예제급 문제입니다. 그만큼 매우 유명하고 잘 알려져 있는데요. 하지만 스택을 이용한 풀이는 효율적이긴 하나 직관적으로 이해하기 어렵습니다. 저도 이 문제를 풀 때 스택보다 재귀를 이용해 풀었으며, 풀이도 더 이해가 잘 되고 직관적입니다. k번째 막대를 살펴보고 있다고 할 때, 이 막대를 기준으로 생각해 볼 수 있는 경우는 아래 세 가지 경우입니다. 1. k번째 막대를 포함한 히스토그램 내부의 최대 직사각형 넓이 2. k번째 막대 왼쪽 히스토그램 내부의 최대 직사각형 넓이 3. k번째 막대 오른쪽 히스토그램 내부의 최대 직사각..