알고리즘
-
백준 1516번 게임 개발, 1700번 멀티탭 스케줄링 (Python)알고리즘 2023. 9. 8. 09:49
1516번 게임 개발 건물을 짓는 속도와 이전에 지어져야하는 건물들이 주어질 경우, 모든 건물을 짓는데 걸리는 시간을 구하는 문제입니다. 전형적으로 Dynamic Programming를 활용해 풀 수 있는 문제라고 생각했습니다. dp에 저장할 값은 각 번호의 건물을 짓는데 걸리는 속도로 했습니다. 우선, 이전에 지어져야하는 건물이 없는 건물의 경우 자신만 지으면 되므로 건물을 짓는데 걸리는 시간을 dp에 저장했습니다. 그 이후 건물을 짓기 전 필요한 건물이 있을 경우 해당 건물들이 지어지는 속도를 우선 확인하도록 했습니다. 건물의 번호를 i라 할 때, dp[i]에 값이 존재한다면 그 값을 반환해주었고, 값이 없다면 해당 건물을 지을 때 필요한 시간을 측정해줍니다. dp[i]의 값은 (필요한 건물들의 건설..
-
백준 2225번 합분해, 2133번 타일 채우기 (Python, DP)알고리즘 2023. 9. 7. 11:16
2225번 합분해 0~N개의 숫자 K개를 더해서 N을 만드는 경우의 수를 구하는 문제입니다. 덧셈의 순서가 바뀐 경우 다른 경우로 셉니다. 풀이 다이나믹 프로그래밍을 이용해 이전의 결과값들을 저장해서 다음에 사용할 수 있도록 했습니다. dp 배열의 행은 N을 나타내고 열은 K를 나타내도록 2차 배열로 선언했습니다. 1️⃣ N이 1인 경우 K에 상관 없이 dp[1][k]=k입니다. 1을 1개의 숫자로 만드는 방법은 1 1을 2개의 숫자로 만드는 방법은 0+1, 1+0 1을 3개의 숫자로 만드는 방법은 0+0+1, 0+1+0, 1+0+0 ... 이므로 dp[1][i]=i 입니다. 2️⃣ k가 2인 경우 N에 상관 없이 dp[n][k] = n+1 입니다. 1을 2개의 숫자로 만드는 방법은 0+1, 1+0 2를..
-
백준 2357번 최솟값과 최댓값 (Python)알고리즘 2023. 9. 6. 11:11
N개의 정수가 주어질 때, 구간 a~b 사이에 최소, 최대값을 찾는 문제입니다. 아이디어 1. 세그먼트 트리 주어진 숫자 개수 N과 구간 쌍 M개의 범위가 (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 100,000)이므로 모두 탐색하면서 찾는다면 시간 초과가 발생할 것으로 예측됐습니다. 그래서 세그먼트 트리를 활용하게 됐습니다. 세그먼트 트리는 데이터가 연속적으로 존재할 때 특정 범위의 데이터의 합을 구하는 방법입니다. 세그먼트 트리 5 3 8 11 2 9 4 14 8 6 의 연속된 데이터가 있다고 가정해보도록 하겠습니다. 이 숫자들 중 여러 개의 특정 구간의 숫자 합을 구할 때, 계속해서 반복을 통해 구하게 된다면 O(N) 시간이 걸리게 되므로, 데이터의 개수가 많아진다면 시간 초과가 발생해 불가능하..
-
백준 17472번 다리 만들기 2 (Python)알고리즘 2023. 9. 5. 10:47
섬으로 이루어진 나라가 있고 모든 섬을 다리로 연결하려고 할 때, 모든 다리의 길이의 합이 최소가 되도록 해야합니다. 다리의 길이는 최소 2여야 하고, 다리는 직선 모양으로 중간에 방향이 바뀌면 안 됩니다. 방향이 가로인 다리는 무조건 두 섬이 가로 방향으로 섬과 인접해야지만 두 섬이 연결됩니다. 방향이 세로일 경우는 무조건 두 섬이 세로 방향으로 섬과 인접해야지만 두 섬이 연결됩니다. 다리는 교차가 가능하며 총 다리의 길이를 구할 때, 겹쳐진 부분은 각 다리의 길이에 모두 포함되어야 합니다. 이번 문제는 보자마자 조금 시간이 오래 걸릴 것으로 예상되었습니다. 하지만, 각 조건이 1 ≤ N, M ≤ 10, 3 ≤ N×M ≤ 100, 2 ≤ 섬의 개수 ≤ 6 적은 숫자들로 구성된 것을 확인했고, 구현만 한..
-
백준 1781번 컵라면 (Python)알고리즘 2023. 9. 4. 11:24
N개 문제의 데드라인과 문제를 맞힐 경우 주어지는 컵라면의 개수가 있을 경우 N시간 안에 받을 수 있는 최대 컵라면 개수를 구하는 문제입니다. 아이디어 1. 컵라면의 개수로 내림차순 정렬 우선 문제를 풀었을 때 받을 수 있는 컵라면의 개수가 많은 것부터 푸는 것이 좋다고 생각했습니다. 그래서 1~N 각 초마다 문제를 풀 경우 해당 초에 얻은 컵라면의 개수를 저장할 수 있는 배열을 선언하고, 데드라인 내에 문제를 풀 수 있다면 해당 초에 컵라면의 개수를 저장하도록 했습니다. 이 후 배열 원소의 총합을 답으로 출력했습니다. ... # resolvedProblems에 해당 초에 푼 문제의 컵라면 개수를 저장 for deadline, ramen in problems: for i in range(deadline,..
-
백준 2098번 외판원 순회 (Python)알고리즘 2023. 9. 1. 12:27
1번부터 N번까지 N개의 도시가 있고 어떤 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아온느 순회 여행 경로를 찾아야합니다. i 도시에서 j 도시로 이동할 때 드는 비용이 W[i][j]이고 W[i][j] != W[j][i] 일 수 있고, W[i][j]==0 일 경우 i 도시에서 j 도시로 가는 경로는 없다고 합니다. 순회 여행 경로 중 가장 적은 비용을 들이는 경로를 구하면 됩니다. 이번 문제의 경우 주어진 시간 내에 풀지 못해 풀이를 참고하고 다시 풀이하게 되었습니다...🥺 아이디어 아이디어 1. 어떤 도시를 출발지로 할 것인지 문제에서 항상 순회할 수 있는 경우만 입력으로 주어진다고 알려주었습니다. 그러므로 어떠한 경우에도 순회는 가능합니다. 1~N의 모든 도시를 순회하고, 마지막..
-
백준 3109번 빵집 (Python)알고리즘 2023. 8. 31. 14:31
R * C 크기의 지도가 주어집니다. 첫 번째 열에서 마지막 열까지 가스관을 연결하려고 할 때, 건물이 있는 곳이나 가스관이 이미 설치된 곳에는 새로운 가스관을 설치하지 못합니다. 모든 가스관은 첫 번째 열에서 마지막 열로 이동을 하고 한 지점에서 다음 지점으로 가스관을 연결하는 방법은 오른쪽 위 대각선, 오른쪽, 오른쪽 아래 대각선 방향 3가지가 있습니다. 가스관을 설치할 수 있는 최대 개수를 구하는 문제입니다. 아이디어 1. (모든 경우의 수 탐색) 모든 경우의 수를 dfs로 재귀를 통해 가장 많은 경우의 수를 찾아보려고 했습니다. 하지만, 문제에서 주어진 조건이 (1 ≤ R ≤ 10,000, 5 ≤ C ≤ 500)으로 모든 경우의 수를 찾아보기 위해서는 최악의 경우 10,000 * 500 * 3 이..
-
백준 23290번 마법사 상어와 복제 (Python)알고리즘 2023. 8. 11. 14:13
물고기가 돌아다니고 있는 4*4 크기의 격자에 마법사 상어가 돌아다니며 마법 연습을 할 경우 마지막에 격자에 남아있는 물고기의 숫자를 구하는 문제입니다. 마법 연습의 순서는 다음과 같습니다. 1. 상어가 모든 물고기에게 복제 마법을 시전합니다. 복제 마법은 시간이 오래걸리기 때문에 5번째 순서에서 물고기 복제가 완료됩니다. 2. 모든 물고기에게는 처음에 주어진 방향이 있습니다. 이 방향대로 움직이는데, 해당 방향으로 움직일 수 없을 경우 반시계 방향으로 45도 회전한 다음 다시 이동을 시도합니다. 만약, 이동할 수 있는 칸이 없다면 이동하지 않습니다. 물고기가 이동할 수 없는 칸은 다음과 같습니다. 상어가 있는 칸 물고기의 냄새가 있는 칸 격자의 범위를 넘어가는 칸 3. 상어는 무조건 연속해서 3칸 움직..