본문 바로가기

[Algorithm] 허수에서 실수까지/Gold430

[C++] 백준 2133번: 타일 채우기 (DP) https://www.acmicpc.net/problem/2133문제 이해하기 문제의 요구사항은 다음과 같습니다.3 x N 크기의 벽을 2 x 1, 1 x 2 크기의 타일로 채우는 경우의 수를 구하여라.시간복잡도 어림하기브루트 포스 알고리즘 만약, 2 x N의 벽을 채운다고 하면 시간복잡도는 O(2^N)이 될 것입니다. 현재 위치에 대해 설치 가능한 타일이 2개이기 때문입니다. 하지만 이 문제는 벽의 높이가 2가 아닌 3이므로 더 많은 경우의 수를 가질 것입니다. 따라서 N의 최댓값이 30인 이번 문제에서는 제한 시간 내에 문제를 해결하기 어렵습니다.  DP 알고리즘 벽의 크기가 3 x N으로 배열에 상태 값을 담을 수 있고, 현재 벽까지의 상태를 구하기 위해 이전 벽 상태를 이용할 수 있습니다. DP .. 2024. 6. 18.
[C++] 백준 1504번: 특정한 최단 경로 (다익스트라) https://www.acmicpc.net/problem/1504문제 이해하기 문제의 요구사항은 다음과 같습니다.1번 정점에서 N번 정점까지 이동할 때, 어떤 정점 u, v를 지나는 최단 경로를 구하여라.시간복잡도 어림하기다익스트라 알고리즘 한 정점에서 다른 모든 정점까지의 최단거리를 구해야하는 문제이므로 다익스트라 알고리즘을 사용할 수 있습니다. 다익스트라 알고리즘은 구현 방식에 따라 시간 복잡도가 달라지지만, 가장 빠른 알고리즘의 경우 우선순위 큐를 사용하는 방법으로 O(ElogV)의 시간복잡도를 가집니다.  문제에서 E의 최댓값은 200,000이고, V의 최댓값은 800입니다. 따라서 다익스트라 알고리즘의 시간복잡도는 200000log800으로 약 2백만 정도되는 값입니다. 따라서 제한 시간 내에 .. 2024. 6. 17.
[C++] 백준 16234번: 인구 이동 (구현) https://www.acmicpc.net/problem/16234문제 이해하기 문제의 요구사항은 다음과 같습니다.주어진 규칙에 따라 인구 이동을 진행할 때, 인구 이동이 며칠 동안 이루어지는지 구하여라.  문제에서 주어진 규칙은1. 인접한 두 나라의 인구차이가 L이상 R이하라면 두 나라는 국경선을 연다.2. 위의 조건을 만족하는 모든 나라의 국경선이 열렸다면 인구 이동을 시작한다.3. 국경선이 열린 나라들의 모임을 연합이라고 하고 인구 이동을 마치면 각 나라의 인구수는 (연합의 인구 수) / (연합의 수)가 된다.4. 연합을 해체하고, 모든 국경선을 닫는다.입니다.시간복잡도 어림하기 미리 시간복잡도를 어림하는 것이 큰 의미가 없는 구현 문제이므로 생략하도록 하겠습니다.알고리즘 설계하기 인구이동은 주어진.. 2024. 6. 14.
[C++] 백준 14499번: 주사위 굴리기 (구현) https://www.acmicpc.net/problem/14499문제 이해하기 문제의 요구사항은 다음과 같습니다.규칙에 따라 주사위를 굴릴 때, 주사위가 이동할 때마다 주사위 윗면에 쓰인 수를 구하여라.  주사위를 굴리는 규칙은1. 주사위는 동, 서, 북, 남 방향으로 굴릴 수 있다. 각각 1, 2, 3, 4에 대응된다.2. 현재 위치를 기준으로 이동할 수 없는 방향일 때는 이후 과정을 생략하고 다음 명령을 수행한다.3. 주사위를 굴리고 이동한 칸의 값이 0이면, 주사위 바닥에 쓰인 숫자가 칸에 복사된다.4. 주사위를 굴리고 이동한 칸의 값이 0이 아니면, 칸의 수가 주사위 바닥에 복사된다. 이때, 칸의 값은 0으로 초기화된다. 으로 정리할 수 있습니다.시간복잡도 어림하기 시간복잡도를 미리 어림하는 것.. 2024. 6. 13.
[C++] 백준 2110번: 공유기 설치 (이분 탐색) https://www.acmicpc.net/problem/2110문제 이해하기 문제의 요구사항은 다음과 같습니다.C개의 공유기를 설치할 때, 인접한 두 공유기 사이의 최대 거리를 구하여라.시간복잡도 어림하기브루트 포스 알고리즘 브루트 포스 알고리즘을 통해 가능한 모든 경우의 수를 구하기 위해서는 n개중 c개를 뽑는 조합 알고리즘이 필요합니다. 하지만 n의 최댓값은 200,000이고 c의 최댓값은 n이므로 경우의 수가 너무 많습니다. 따라서 브루트 포스 알고리즘은 적절하지 않습니다. DP 알고리즘 dp배열에 각 상태(공유기 설치 위치)를 담기 애매하고, 현재 상태를 구하기 위해 이전 상태를 사용하기 어려우므로 DP 알고리즘 역시 적절하지 않습니다. 이분탐색 알고리즘 주어진 배열을 정렬할 수 있고, 설치할 .. 2024. 6. 12.
[C++] 1806번: 부분합 (두 포인터) https://www.acmicpc.net/problem/1806문제 이해하기 문제의 요구사항은 다음과 같습니다.어떤 수열이 주어질 때, 해당 수열에서 연속한 수들의 합이 S 이상이 되는 것 중, 가장 짧은 길이를 구하여라.시간복잡도 어림하기브루트 포스 알고리즘 브루트 포스 알고리즘을 통해 문제를 해결하기 위해서는 연속합을 구할 시작 지점과 끝지점이 필요하고, 이를 모든 경우의 수에 대응시켜 구해야합니다. 이는 O(n^2)의 시간복잡도가 필요하고 문제에서 n의 최댓값은 100,000 이므로 10,000,000,000 의 시간복잡도가 걸립니다. 이는 제한 시간내에 문제를 해결하기 어려운 수치이므로 다른 알고리즘을 사용해야합니다. DP 알고리즘 DP 알고리즘 역시 가능한 모든 연속합을 구해 문제를 해결해야하.. 2024. 6. 11.

티스토리툴바