CodeAngie

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

문제 각각의 일을 끝내는 데 걸리는 시간(일)이 담겨 있는 A 배열이 주어졌을 때, 일의 순서를 바꾸어 헬스장에 갈 수 있는 경우는 YES, 갈 수 없다면 NO를 출력하는 문제이다. 문제 조건 오늘은 월요일이다. 금요일에 일을 끝내야 헬스장에 간다. 풀이 일주일은 7일이기 때문에 월요일부터 일요일을 0에서 6으로 둔다. 월요일에 일을 시작해서 금요일에 끝나려면 7로 나누었을 때 나머지가 4인 날이 있는지 확인하면 된다. 따라서 숫자의 조합에 따라 합계를 7로 나눈 나머지가 4가 되는 경우가 있는지 살핀다. 시간에 대한 연산과 나머지에 대한 연산의 결과가 같다는 것을 활용한다. ex) (15+ 9) % 7 = (1 + 2) % 7 = 3 A 배열의 요소(a)들을 모두 순회하면서 먼저 계산된 나머지와 연산을..

문제 상자의 크기가 입력된 배열이 주어졌을 때, 앞에서부터 작은 상자를 뒤의 큰 상자에 넣는다면 최대 몇 개의 상자를 겹칠 수 있는지 개수를 묻는 문제이다. 풀이 왼쪽의 작은 상자를 오른쪽의 큰 상자에 넣는다는 것은 오른쪽으로 이동하면서 오름차순으로 증가하는 상자를 골라야 한다고 말할 수 있다. 즉, 상자배열 내에서 가장 긴 증가하는 부분 수열 (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에 저장되어 있는 현재 위치까지 도달하는데 가능한 경로의 수..