CodeAngie

문제 10000 이하의 자연수로 이루어진 n 길이의 수열에서 부분합이 s 이상이 되는 것 중 최소 길이를 구하는 문제이다. 풀이 이 문제는 1차원 배열의 부분합을 구하여 크기를 비교하고 최소 길이를 구하면 된다. 누적합을 구하면서 해당 위치 이전까지의 부분합 중 s 이상인 경우, 최소 길이를 업데이트한다. 예를 들어 4번째 칸까지 누적합을 구했을 때, s 가 7이라면 최소 길이는 3이 된다. 알고리즘 누적합을 담을 dp list를 n+1 길이로 생성한다. 최소 길이를 담을 ans 변수를 생성한다. for 문을 n 번 돌면서 누적합을 계산한다. 최소 길이에 맞춰 부분합을 계산하고 만약 부분합이 s 보다 작다면 이후에도 더 작을 것임으로 중단해준다. 만약 s보다 크다면 최소 길이를 줄일 수 있다는 의미임으로..

문제 그래프의 정점을 두 집합으로 분할할 때, 인접한 정점끼리 서로 다른 집합에 포함되는 그래프를 이분 그래프라고 한다. 주어진 그래프가 이분 그래프인지 판별하는 문제이다. 풀이 이분 그래프인지 확인하기 위해서 정점들을 두 가지 색으로 칠할 때, 인접한 정점끼리 서로 다른 색으로 칠할 수 있는지를 확인하면 된다. 즉, 인접한 정점이 같은 색이라면 이분 그래프가 아닌 것이다. 예를 들어 a를 노란색(1)으로 칠한다면, a와 연결된 b,c,d를 초록색(2)으로 칠하는 것이다. 그 다음 b,c,d에 연결된 인접한 정점들을 다시 노란색(1)로 칠하다가 이미 다른 색으로 칠해진 정점을 만났을 때, b,c,d와 같은 초록색(2)이 칠해져 있다면 이분 그래프가 아니라고 판별할 수 있다. 반대로 모든 정점들을 방문해도..

문제 상자의 크기가 입력된 배열이 주어졌을 때, 앞에서부터 작은 상자를 뒤의 큰 상자에 넣는다면 최대 몇 개의 상자를 겹칠 수 있는지 개수를 묻는 문제이다. 풀이 왼쪽의 작은 상자를 오른쪽의 큰 상자에 넣는다는 것은 오른쪽으로 이동하면서 오름차순으로 증가하는 상자를 골라야 한다고 말할 수 있다. 즉, 상자배열 내에서 가장 긴 증가하는 부분 수열 (LIS) 을 구한다면, 겹칠 수 있는 최대 상자의 개수를 알 수 있다. 알고리즘 겹치는 상자의 개수를 담는 dp 를 1로 초기화한다. 상자의 크기가 담긴 box 배열을 순회한다. 해당 상자의 이전에 있는 상자들과 비교하면서 담을 수 있는 상자라면, 이전 상자에 담기는 상자의 개수(dp[j])에 1을 더한 값과 현재 dp[i]에 담긴 값을 비교하여 더 큰 값을 d..

문제 주어진 하체 둘레 공식을 참고하여 새로 산 바지를 입었을 때, 둘레가 커서 흘러내리지 않으면서 바닥에 끌리지 않는 바지의 개수를 구하는 문제이다. 문제 조건 하체 둘레 공식 : $f(x) = max(a(x-b)^2 + c, d)$ 바지는 하체 둘레가 가장 큰 위치보다 높거나 같은 곳에서만 걸린다. 풀이 바지의 하체 둘레가 가장 큰 위치는 $f(x) = max(a(x-b)^2 + c, d)$ 공식에 따라 바닥으로부터 $b$의 위치를 의미한다. 바지는 하체 둘레가 가장 큰 위치보다 높거나 같은 곳에서만 걸리기 때문에, 바닥으로부터 길이가 $b$보다 작은 경우는 바지가 짧은 것임을 알 수 있다. 즉, 바지의 길이는 $b$ 길이보다 같거나 커야 한다. 바지의 길이가 $v$일 경우, 바지의 ..

문제 1번에서 N번까지 나열되어 있는 집들의 색을 RGB 중 한 가지 색으로 칠할 때, 맨 첫 번째 집과 맨 마지막 집의 색이 겹치지 않으면서 앞뒤로 위치한 이웃집끼리의 색도 겹치지 않게 칠하는데 드는 비용의 최솟값을 구하는 문제이다. 이웃집과 색이 겹치는 경우는 최소비용이 들더라도 불가능하다. 예를 들어 R-G-G 나 R-G-B-R 등으로 칠할 수 없다. 풀이 기존 RGB거리 문제와의 차이는 맨 첫 번째 집과 맨 마지막 집의 색깔 관계도 살펴봐야 한다는 점이다. 최소비용을 도출하는 점화식은 RGB거리 문제와 동일하다. dp[i]["빨강"] = min(dp[i-1]["초록"], dp[i-1]["파랑"]) + RGB[i]["빨강"] dp[i]["초록"] = min(dp[i-1]["빨강"], dp[i-1][..

문제 1번에서 N번까지 직선으로 나열되어 있는 집들의 색을 앞뒤로 위치한 이웃집과 겹치지 않게 RGB 중 한 가지 색으로 칠할 때 드는 비용의 최솟값을 구하는 문제이다. 이웃집과 색이 겹치는 경우는 최소비용이 들더라도 불가능하다. 예를 들어 R-R-G 나 R-G-B-B 등으로 칠할 수 없다. 풀이 서로 겹치지 않게 색칠하려면, 현재 위치(i)에서 초록색을 선택했을 경우 이전 위치(i-1)에는 빨간색이나 파란색을 선택해야 한다. i번째 집을 초록색으로 칠한다면 i까지의 최소 비용은 i-1번째 집이 빨간색과 파란색일 경우 중 더 작은 비용을 가진 색의 비용과 i번째 집의 초록색 비용을 더한 값이 된다. 모든 위치에서 앞집과 다른 색으로 최소비용을 계산해줌으로써 색이 겹치지 않게 집을 칠하는 비용의 최솟값을 ..

문제 N*N 크기의 게임판이 있을 때, (0, 0)에서 (N-1, N-1)까지 규칙(조건)에 맞게 이동할 수 있는 경로의 수를 구하는 문제이다. 문제 조건 각 칸에는 한 번에 이동 가능한 거리가 쓰임 반드시 오른쪽 혹은 아래쪽으로 이동 풀이 문제의 조건을 주의해야 한다. (오른쪽과 아래쪽으로만 한 번에 직선 이동 가능) 오른쪽과 아래쪽으로만 이동 가능하기 때문에 왼쪽 위의 경로의 수를 먼저 구하고 해당 경로의 수를 활용하여 다음 위치의 경로의 수를 구할 수 있다. 즉, DP를 활용할 수 있다. 위의 그림은 의 예시의 풀이 과정을 시각화한 것이다. 각 칸을 방문하면서 게임판의 범위 내에서 이동 가능한 거리라면, DP에 저장되어 있는 현재 위치까지 도달하는데 가능한 경로의 수..