개발하는 리프터 꽃게맨입니다.

1. 17404 :: RGB거리 2https://www.acmicpc.net/problem/17404  1) 풀이해당 문제는 주어진 시간이 매우 적고, 현재의 최적해가 미래의 최적해의 부분이 아닐 수 있기에다이나믹 프로그래밍 기법으로 풀어야 한다. 이전 집의 색을 고려하여현재 집의 색을 고르는 방식으로쉽게 풀이할 수 있다. 2) 주의할 점첫 번째 집의 색을 계속 기억해야 하므로2중 혹은 최대 3중 배열까지 고려해볼 수 있다. 3) 솔루션더보기#include  #define INF 900'000'000 using namespace std; int N; int arr[1001][3]; int dp[1001][3][3]; enum COLOR { R, G, B, NONE }; int Solution(int id..

1. 문제 10051https://www.acmicpc.net/problem/11051 1) 주의해야 할 점모듈러 계산에서는 나눗셈을 정의하지 않기 때문에팩토리얼을 통한 조합 계산이 문제 조건상 허용되지 않는다.그렇기에 파스칼 삼각형을 이용해서 풀어야 한다. 2) 탑-다운 풀이더보기#include  #include  #include  using namespace std; #define MAX 10'007 int N, K; vector> dp; int Combine(int n, int k) { if (dp[n][k] != -1) return dp[n][k]; if (k == 0 || n == 0 || k == n) return dp[n][k] = 1; if (k == 1) return dp[n][k] = ..

1. 개요동적 계획법 (Dynamic Programming, 이하 DP)는 메모리를 적절히 사용하여 알고리즘의 수행 시간 효율성을 비약적으로 향상시키는 방법입니다. 이미 계산된 결과를 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 하는 것이죠. 예를 들어서 '피보나치 수열' 의 예시를 봅시다.  피보나치 수열은 위와 같은 점화식으로 나타낼 수 있으며이를 가장 간단하게 구현하는 방법은 재귀를 사용하는 겁니다.  이런 식으로 말이죠. 그런데 잘 살펴보면 피보나치 수열을 재귀로 구현하면 상당히 비효율적인 코드 진행을 보입니다. 피보나치 수열 알고리즘을 재귀 함수로 표현한 경우를 상태 트리로 나타내면 위와 같습니다. 이 상태 트리를 보면 알 수 있듯이미 계산된 값을 또 계산하고 있는 것을 볼 수 있습니다...

1. 아이디어1) 음의 가중치가 존재하고, 문제 자체가 음의 사이클 또한 염두하고 있기 때문에 해당 문제는 벨만-포드 알고리즘을 사용하는 것이라고 볼 수 있습니다. 2) 즉, 1번 노드에서 출발하여 그래프에 대해서 최단 거리를 갱신한 뒤 문제의 요구에 맞게 출력을 하면 되겠습니다. 3) 음의 사이클을 분별하는 방법은벨만 포드 알고리즘의 결과 dist 배열과벨만 포드 루프를 1번 더 돌린 dist 배열이 다를경우 음의 사이클 이라고 판단할 수 있습니다.2. 주의할 점1) 가중치의 경우의 수가 int 오버플로를 발생시킬 수 있기 떄문에 long long 이나 __int64를 사용해야 합니다.2) 1번 노드에서 그 어떤 노드로 간선이 존재하지 않는 경우에는 그래프에 음의 사이클이 존재하던 말던,-1 을 N-1..

1. 다익스트라 알고리즘의 한계다익스트라 알고리즘은 최단거리를 찾는 일반적인 알고리즘입니다.그러나 그래프 간선의 가중치의 값이 음수일 경우 항상 최적해를 찾는다는 보장은 없습니다. 물론, 다익스트라 알고리즘이 음수 가중치가 존재한다고 해서 항상 최단거리를 찾지 못하는 것은 아닙니다.   먼저, 우선순위 큐를 사용하지 않는 다익스트라 알고리즘 위 그래프에서 최단거리를 찾아낼 수 없습니다.모든 간선의 가중치가 양수일 경우 방문하지 않은 vertex 중 distance 배열의 값이 최소인 노드는 자명하게 최단거리이기 때문이죠. 그러나 음의 가중치 값이 그래프에 존재할 경우미래에 더 저렴한 경로를 찾을 가능성이 존재합니다.  위와 같은 그래프에서는 우선순위 큐를 사용한 다익스트라 알고리즘으로 최단거리를 찾아낼 ..