devbelly

문제 www.acmicpc.net/problem/13510 알고리즘 hld 풀이 트리에서 두 개의 쿼리를 처리해야 합니다. 첫 번째는 $i$번째 간선을 업데이트, 두 번째는 경로 사이의 최댓값을 구하는 문제입니다. 두 번째 쿼리는 이전에도 설명 드린 적이 있습니다. 트리에서 한 정점은 부모로 가는 간선이 유일하므로 간선을 정점으로 표시가 가능합니다. 두 정점과 그 사이를 잇는 엣지가 있다면 자식정점의 번호를 간선처럼 생각하면 됩니다. 간선 문제를 해결했다면 첫 번째 쿼리인 간선을 업데이트 하는 것도 자연스레 해결가능합니다. 문제에서 입력받을 때 $i$번 간선이 무슨 정점들을 나타내는지만 기록하면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i < n; ++i..

문제 www.acmicpc.net/problem/18784 알고리즘 정렬 풀이 $N$개의 좌표가 주어질 때, 3개를 골라 만들 수 있는 삼각형의 넓이의 총 합 * 2을 구하는 문제입니다. 단, 만든 삼각형은 X, Y축에 평행하는 변이 존재해야합니다. 각 축에 평행해야하는 조건을 만족하려면 한 점에서 직교해야합니다. $(x1, y1)$ 에서 직교하는 삼각형을 찾기 위해 x좌표가 $x1$인 모든 좌표들과 y좌표가 $y1$인 모든 좌표들을 구해야합니다. 각각의 집합을 A, B라고 하겠습니다. $\sum (|A_i-y1|)$을 통해 y축에 평행한 모든 길이의 합을 구할 수 있고 x축에 평행한 변도 마찬가지로 풀면 됩니다. 남은 문제는 길이의 합을 구하는 것입니다. $x1$을 공유하는 $y$좌표 $a, b, c ..

문제 www.acmicpc.net/problem/1626 알고리즘 hld, mst 풀이 MST 대신 두 번째로 작은 스패닝 트리를 구하는 문제입니다. 접근은 그리디하게 MST에서 가장 큰 간선을 제거하는 것입니다. MST를 만들 때 사용하지 않은 간선들을 검사하며 이 때 간선의 양 끝 정점을 $u, v$라고 합시다. MST를 구성했다면 $u, v$를 잇는 경로는 무조건 존재하게 됩니다. $u, v$를 연결하는 경로에서 가장 큰 간선을 제거하고 현재 사용하지 않은 간선으로 대체하며 풀어나가면 됩니다. 현재 사용하지 않은 간선의 무게와 $u, v$를 잇는 가장 큰 간선의 무게가 같은 경우가 있습니다. 이 경우는 MST가 유일하지 않은 경우입니다. 문제에서는 MST와 second MST를 다른 값으로 구분하고..

문제 www.acmicpc.net/problem/20052 알고리즘 segment tree 풀이 괄호 문자열이 주어지고 쿼리들이 주어졌을 때 부분 문자열이 올바른 괄호 문자열인지를 묻는 문제입니다. '('을 1로 생각하고 ')'을 -1로 생각했을 때, 올바른 괄호 문자열은 다음과 같은 특징을 갖고 있습니다. 1. 괄호문자열을 구성하는 문자들의 합은 0이다. 2. 문자열의 길이를 S라고 할 때, 처음부터 $i (1\leq i \leq S-1)$까지의 문자들의 합은 음수가 되어선 안된다. 1번 조건은 '('의 등장 횟수와 ')'의 등장 횟수가 일치함을 묻고 있습니다. 2번 조건은 괄호 문자들이 짝을 올바르게 구성하고 있는지를 묻고 있습니다. 만약 주어진 괄호 문자열이 ")(" 라면 총합은 0이 될지언정 올바..

문제 www.acmicpc.net/problem/2263 알고리즘 재귀 풀이 트리의 인오더, 포스트오더가 주어질 때, 프리오더를 출력하는 문제입니다. 포스트오더는 배치가 왼쪽 서브트리 포스트오더 출력 + 오른쪽 서브트리 포스트오더 출력 + 루트 입니다. 즉 맨 오른쪽 값이 루트임을 알 수 있습니다. 인오더의 배치는 왼쪽 서브트리 인오더 출력 + 루트 + 오른쪽 서브트리 인오더 출력입니다. 포스트오더에서 루트를 파악했다면 인오더에서 해당 루트의 위치를 찾아 왼쪽 서브트리와 오른쪽 서브트리를 나누어줍니다. 인오더와 포스트오더의 서브트리의 크기는 일치하므로 인오더에서 찾은 서브트리크기를 통해 포스트오더의 구간을 나누어 재귀호출하면 풀 수 있습니다. 코드 #include #define rep(i, n) for ..

문제 www.acmicpc.net/problem/2661 알고리즘 백트래킹 풀이 임의의 길이의 인접한 두 개의 부분 수열이 동일하지 않도록 길이$N$까지를 결정하여 출력하는 문제입니다. 백트래킹 문제입니다. 처음에 빈 수열에서 시작하여 수열의 원소를 하나씩 결정해나갈때마다 '좋은수열'인지 검사합니다. 이를 통해 채워나가는 수열은 '좋은수열'로 유지할수가 있습니다. 원소가 추가된 수열에서 좋은수열인지 아닌지를 검사할 때, 추가된 원소를 포함하도록 부분 수열을 구성하기만 하면 됩니다. 예를 들어 1213에서 1을 추가하면 12131이 됩니다. 우리는 첫번째 1과 두번째 2가 좋은 수열인지 검사할 필요가 없습니다. 마지막 수열 1을 포함하는 1, 31과 인접한 수열만 검사하면 됩니다. 이렇게 길이 $N$의 수..

문제 www.acmicpc.net/problem/18783 알고리즘 Sparse table 풀이 소들이 $M$ step을 $K$번 반복했을 때, 최종적인 소의 배치를 구하는 문제입니다. $M$과 $K$의 범위가 크므로 시간복잡도 $O(MK)$ 로는 해결할 수 없습니다. 대신 $K$을 비트로 표현하여 켜진 비트에 대한 다음의 상태를 관리할 수 있는 sparse table을 통해 $K$를 $logK$로 줄일 수 있습니다. 모든 배열의 $K$이후의 상태를 물어보기 때문에 sparse배열을 두개만 만들어 메모리를 절약할 수 있습니다. 코드 #include #define rep(i, n) for (int i = 0; i N >>..

문제 www.acmicpc.net/problem/14226 알고리즘 DP 풀이 $N$개의 이모티콘을 만들기 위해 사용하는 최소시간을 구하는 문제입니다. $cache[i]$ = 이모티콘 $i$개를 만들기 위해 사용하는 최소시간 $i$상태에서 갱신할 수 있는 상태는 $i$의 배수상태들 입니다. $i$를 복사한후 계속 붙여넣기를 하면 계속 $i$의 배수들에 영향을 끼칠 수 있습니다. 또한 각 $i$때마다 모든 $j(2\leq j \leq 1000)$에 대하여 하나 빼준 $j-1$의 상태도 검사해주면 $O(N^2)$에 풀 수 있습니다. 코드 #include #define rep(i, n) for (int i = 0; i N; ..