JINWOOJUNG

문제 접근법 DP 문제이다 직접 해보자. 문제를 요약 해 보자면 한번에 한칸 혹은 두칸을 움직일 수 없으며, 3칸 연속으로 움직일 수 없다. 즉, 출발 위치가 아닌 특정한 위치에서 한칸 움직였다면, 무조건 두칸을 움직여야 하며, 두칸 움직였다면 무조건 한칸 움직여야 한다. 이러한 규칙을 발견했으므로, 가능한 경우에수는 총 4가지로 추릴 수 있다. 시작 위치에서 1칸 움직임 +1, +2 의 순서로 움직임 +2, +1 의 순서로 움직임 시작 위치에서 2칸 움직임 +1, +2 의 순서로 움직임 +2, +1 의 순서로 움직임 하지만 이를 코드적으로 표현하기가 힘들다. 0 1 2 4 5 7 ... 0 1 3 4 6 7 ... 0 2 3 5 6 8 ... 0 2 4 5 7 8 ... 하나의 for 문으로 4가지 모..

문제 접근법 DP 문제이기에 직접 하나하나 해 보면서 규칙을 찾고자 하였다. 하지만, 색상에 따른 Cost를 기준으로 규칙을 찾기에는 각 Cost는 변경되고, 동일한 Cost에 대한 처리가 힘들어 포기하였다. Cost가 결정되는 기준은 결국 각각의 집이 칠하고자 하는 RGB색상에 의해 결정된다. 집의 색상을 결정하는 규칙은 결국 1번째 집부터 시작하여 다음집과 색상이 안겹치면 된다. 이 점에서 나올수 있는 경우의 수를 생각 해 보면, 다음 집의 색상이 R이 되기 위해선 이전에는 G,B가 되어야 한다. 다음 집의 색상이 B이 되기 위해선 이전에는 R,G가 되어야 하며, 다음 집의 색상이 G이 되기 위해선 이전에는 R,B가 되어야 한다. for (s32_I = 1; s32_I > ars32_Cost[0] >..

접근법 처음엔 피보나치 함수의 Code가 주어졌으니, 직접 재귀함수를 실행하면서 n이 1 또는 0일 때, 조건문을 걸어 개수를 계산하려고 하였으나 역시나..시간초과! 따라서 DP문제이기에 몇가지를 시도해본 결과 왼쪽이 0이 출력되는 개수, 오른쪽이 1이 출력되는 개수이다. 즉 피보나치 함수의 재귀적인 호출 처럼 각각의 출력 개수 역시 -1, -2 번째의 출력 개수의 합으로 유도할 수 있음을 알 수 있다. 하지만 0의 경우 1,2번재 부터 유효하고, 1의 경우 0,1 부터 유효하므로 두 DP 배열의 0,1,2번째 원소는 직접 입력하고, 나머지는 반복문을 돌면서 계산하면 된다. 정답 #include #include using namespace std; int32_t st_DP0[41]; int32_t st_..

접근법 직접 해 보는 것이 DP문제에서 규칙을 찾는 가장 쉬운 방법인 것 같다. 1 표현 1 2 표현 1+1 2 3 표현 1+1+1 1+2 2+1 3 1,2,3은 각각 1,2,4가지로 표현 가능하다. 4를 1,2,3의 합으로 나타내보자. 1+1+1+1 1+1+2 1+2+1 1+3 2+2 2+1+1 3+1 총 7가지인데, 처음이 1일 때 나머지 3을 나타낼 수 있는 가지수는 위에서 구한 4가지, 처음이 2일 때 나머지 2를 나타낼 수 있는 가지수는 2가지 그리고 처음이 1이면 1가지 이다. 따라서 DP[4] = DP[4-1] + DP[4-2] + DP[4-3] 으로 표현 가능하다. 이제 구현해보자. 정답 #include #include using namespace std; int32_t DP[12]; in..

접근법 점화식을 이끌어 내야 하는 중요한 문제이다. 단순히 3으로 나눠지고 2로 나눠진다고 해서 해당 값으로 나누는 연산을 진행 시 최소값을 찾을 수 없게 된다. 이러한 DP문제는 직접 규칙을 찾아보는 것이 가장 중요하다. 연산이 가능한 것을 고려하였을 때 2와 3은 1번의 연산으로 1로 만들 수 있다. 이는 1일 때는 1로 만드는데 0번의 연산이 걸리는 점을 고려하고 넘어가자. 4는 2로 나누어 떨어지기에 2로 나눈 값인 2는 1번의 연산이 더 필요하다. 또한, 1을 먼저 빼고 3으로 나누어도 동일하게 1로 만들 수 있다. 5는 2와 3 모두 나누어 떨어지지 않는다. 따라서 1을 뺀 후 4는 2가지 방법으로 총 2번의 연산을 통해 1로 만들 수 있다. 6은 2와 3으로 모두 나누어 떨어진다. 2로 나누..

접근법 Dynamic Programming의 가장 쉬운 문제이다. 직관적인 접근이 가능한데, 우리가 원하는 것은 3a+5b = Inupt을 만족하는 a,b에 대하여 a+b가 최소가 되는 경우를 찾고싶은 것이다. 또한, 만들 수 없는 조합일 때는 결과가 -1이야 하는것을 명심하면 된다. 단순히 a 혹은 b 만으로 Input을 나타낼 수 있는 경우도 고려해야 하기 때문에 2중 for 문에서 해당 조건만 고려하면 쉽게 접근 가능하다. 또한, 3a+5b = Input을 만족하는 a,b에 대해서 Result를 처음에 -1로 설정하고 -1인 경우는 그냥 a+b를 Result로, -1이 아닌 경우 기존 Result와 a+b 중 작은 값을 Result로 설정하면 된다. 정답 #include #include using ..

본 게시글은 인하대학교 유상조 교수님의 Reinforcement Learning Tutorial Seminar 수강 후정리를 위한 포스팅입니다. 모든 포스팅의 저작관은 유상조 교수님에게 있음을 사전 공지합니다. Before This Episode https://jinwoo-jung.tistory.com/16 Bellman Optimality Equation 본 게시글은 인하대학교 유상조 교수님의 Reinforcement Learning Tutorial Seminar 수강 후정리를 위한 포스팅입니다. 모든 포스팅의 저작관은 유상조 교수님에게 있음을 사전 공지합니다. Before This Episode jinwoo-jung.tistory.com $S,A,P,R,\gamma$가 주어진 MDP에서 최적의 pol..

본 게시글은 인하대학교 유상조 교수님의 Reinforcement Learning Tutorial Seminar 수강 후정리를 위한 포스팅입니다. 모든 포스팅의 저작관은 유상조 교수님에게 있음을 사전 공지합니다. Before This Episode https://jinwoo-jung.tistory.com/14 Markov Decision Process(MDP) 본 게시글은 인하대학교 유상조 교수님의 Reinforcement Learning Tutorial Seminar 수강 후정리를 위한 포스팅입니다. 모든 포스팅의 저작관은 유상조 교수님에게 있음을 사전 공지합니다. Before This Episode jinwoo-jung.tistory.com 지난 시간에 Bellman Expected Equation을 ..