CodeAngie

문제 주어진 하체 둘레 공식을 참고하여 새로 산 바지를 입었을 때, 둘레가 커서 흘러내리지 않으면서 바닥에 끌리지 않는 바지의 개수를 구하는 문제이다. 문제 조건 하체 둘레 공식 : $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에 저장되어 있는 현재 위치까지 도달하는데 가능한 경로의 수..

동적프로그래밍동적 프로그래밍은 큰 문제를 작은 문제로 나누어 푸는 방법이다.분할 정복과는 다르게 작은 문제를 푸는데서 답이 같은 문제가 중복적으로 일어날 경우 사용한다.보통 점화식을 만들 수 있다.1. 동적프로그래밍의 조건큰 문제는 작은 문제로 나눌 수 있고 작은 문제가 반복해서 나타난다.같은 문제라면 계산할 때마다 같은 답이 도출된다.2. 메모이제이션 (Memoization)메모이제이션은 한번 풀었던 작은 문제를 다시 반복해서 풀지 않기 위해 메모해두고 필요할 때 답만 꺼내 보는 것이다.담아 놓는 것이기 때문에 캐싱 (caching) 이라고도 불린다.메모이제이션을 통해 먼저 구한 결과를 담아 두면, 아래 피보나치 예시에서 점선으로 표시된 노드는 먼저 먼저 계산된 값을 사용하면 되기 때문에 반복해서 계산..

문제 두 전봇대 A와 B 사이에 몇 개의 전깃줄을 제거해야 교차하는 전깃줄이 없는지 구하는 문제이다. 즉, 최소한의 제거할 수 있는 전깃줄의 개수를 도출해야 한다. 풀이 서로 전깃줄이 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구해야 한다. 예를 들어, A-1번과 B-8번이 연결된 전깃줄보다 A-3번과 B-9번이 연결된 전깃줄이 더 아래 있는 것을 알 수 있다. 이를 통해 A의 번호가 순차적으로 커질 때, 각각의 A와 연결된 B의 번호도 더 커진다면 교차하지 않는 전깃줄의 개수를 구할 수 있음을 알 수 있다. A의 정렬된 번호를 리스트의 인덱스로 두고, B의 번호를 가지고 가장 긴 증가하는 수열(LIS)을 구함으로써 교차하지 않는 전깃줄의 최대 개수(c)를 구할 수 있다...

이분 탐색이란, 오름차순으로 정렬된 배열을 반복적으로 반으로 나누어 target이 선택될 때까지 탐색하는 알고리즘이다. 1. 이분 탐색의 조건 반드시 오름차순으로 정렬된 상태에서 시작해야 한다. 2. 이분 탐색 알고리즘 시간복잡도: O(logN) 반복문과 재귀 두 가지 방법을 사용할 수 있다. 자료를 오름차순으로 정렬한다. 자료의 중간값(mid)이 찾고자 하는 값(target)인지 비교한다. mid 값이 target과 다르다면 대소관계를 비교하여 탐색 범위를 좁히고, target과 mid 값이 같을 때까지 아래 조건에 따라 2번과 3번을 반복한다. ⓐ target이 mid 값 보다 작으면 end를 mid 왼쪽 값으로 바꿔준다. (절반의 왼쪽 탐색) ⓑ target이 mid 값 보다 크면 start를 mi..