PostgreSQL 16에서 복합·커버링·고유·필터링 인덱스를 직접 만들어 실행 계획과 실행 시간을 비교한 기록

문제 & 링크 https://www.acmicpc.net/problem/18223 풀이 어떤 변도 음수 가중치를 갖지 않고, 1번 노드에서 V번 노드까지의 최단 경로를 구하기 위해 다익스트라 알고리즘을 사용한다. 인접리스트 형태로 양방향 그래프를 저장한다. 1번 노드에서 다익스트라를 수...

문제 & 링크 https://www.acmicpc.net/problem/14226 풀이 걸리는 시간의 최솟값을 구하기 위해서 BFS를 사용한다. 화면에 있는 이모티콘의 개수, 클립보드에 있는 이모티콘의 개수가 BFS의 큐에 저장이 되어야 하며, 시간을 구하기 위해 시간도 저장해준다. 문...

문제 & 링크 https://www.acmicpc.net/problem/1167 풀이 임의의 한 노드에서 DFS(깊이 우선 탐색)를 수행하여 가장 먼 노드를 찾는다. 해당 노드(가장 먼 노드)를 시작점으로 다시 한 번 DFS를 수행해 도달할 수 있는 가장 먼 노드를 찾는다. 이때의 거리...

문제 & 링크 https://www.acmicpc.net/problem/1937 풀이 모든 점에서 시작하여 가능한 모든 이동 경로를 완전 탐색하는 것은 시간 초과가 발생한다. 따라서 dp와 메모이제이션을 사용해야 한다. 각 점에는 해당 점에서 시작했을 때의 최대 이동 칸 수를 저장한다. 이를 위해 2차원...

문제 & 링크 https://www.acmicpc.net/problem/1744 풀이 합이 최대가 되도록 하려면 큰 수는 큰 수와 묶여서 곱해져야 한다. 음수의 경우 무조건 음수 or 0이랑 묶여서 곱했을 때, 0보다 큰 정수를 만들어야 한다. 1번과 2번을 바탕으로 음수와 0은 오름차...

문제 & 링크 https://www.acmicpc.net/problem/3673 풀이 수열의 원소를 입력받을 때, 해당 원소까지의 합을 d로 나눈 나머지를 저장한다. 합을 그대로 저장할 경우 sum이 너무 커지기에 비효율적이다. d로 나눈 나머지가 나온 개수를 추가로 저장한다. 같은 값...

문제 & 링크 https://www.acmicpc.net/problem/1450 풀이 bruteforce로 생각하면 N이 최대 30이기에 O(2^30)의 시간 복잡도를 가진다. 시간 복잡도를 줄이기 위해 두 그룹으로 나눈다. 각 그룹에 대해 나올 수 있는 모든 값을 벡터(l_v, r_v...

문제 & 링크 https://www.acmicpc.net/problem/1766 풀이 선행 문제가 존재하는 문제의 경우 선행 문제 다음으로 풀이되어야 하기에, 위상 정렬 문제이다. 가장 쉬운 문제, 즉 문제 번호가 낮은 문제가 우선적으로 풀려야 한다. 입력을 받을 때 인접 리스트의 형태...

문제 & 링크 https://www.acmicpc.net/problem/1422 풀이 K개의 수를 적어도 한 번씩 사용해야 하기에, 모든 수를 이어 붙여서 가장 큰 수를 구하는 문제와 유사하다. N > K일 경우 숫자를 중복으로 사용하여 추가할 수 있는데, 자릿수와 값을 생각하면 무조건 K개의 수 ...