devbelly

문제 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; ..

문제 www.acmicpc.net/problem/13511 알고리즘 HLD 풀이 첫번째 쿼리는 두 정점 사이의 간선가중치의 합, 두번째 쿼리는 k번째 정점을 구하는 문제입니다. 트리에서는 루트정점을 제외하고는 모든 정점의 부모정점을 유일합니다. 이를 이용하면 트리의 리프노드마다 간선의 가중치를 넣을 수 있습니다. u와 v의 lca를 a라고 가정하겠습니다. k번째 정점을 구하기 위해서는 그 정점이 u와 a사이에 있는지 a와 v사이에 있는지를 일차적으로 확인해야합니다. u와 a사이의 정점의 갯수가 cnt개라고 할 때, $k\leq cnt$ 라면 u로 부터 k번 위로 올라가면 되고 a와 v사이에 k번째 정점이 존재한다면 (전체 정점의 갯수 -k+1)번 위로 올라가면 k번째 정점을 구할 수 있습니다. 코드 #i..