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_..

본 영상 처리 개념과 기법들에 대한 공부를 진행하면서 배운 내용들을 중심으로 정리한 포스팅입니다. 책은 Computer Vision: Algorithms and Applications를 기반으로 공부하였습니다. 또한, 인하대학교 박인규 교수님의 디지털 영상 처리 과목을 기반으로 제작된 포스팅입니다. Image Processing 영상 처리를 위한 Image Processing은 아래의 Step으로 구분된다. Image Digitization 연속적인 밝기 값을 픽셀 공간에서의 discrete(별개의)한 값으로 변환하는 과정 즉, 이미지를 티지털화 하는 과정이다. Sampling - spatial discretization 말 그대로 샘플링 과정이다. 특정한 픽셀공간(단위)로 구분하여, 특정 공간에 다수의..

접근법 직접 해 보는 것이 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 ..

접근법 이차원 배열(벡터)에서 index를 다루고 놀아야 하는 중요한 문제이다. 문제를 보면 삼각형 A와 B중 하나만 회전, 반전 시키면서 B와 비교하면 찾을 수 있다고 생각이 들 것이다. 따라서 가능한 경우의 수를 해당 Index의 변화를 고려하여 접근한다면 조금 수월하게 접근할 수 있다. 먼저 각 삼각형의 원소들을 받아오기 위해서 부터 이중 for문이 요구된다. 첫번째 줄엔 1개, 2번째 줄엔 2개 등 각 줄에 맞춰서 받아와야 하는 원소가 증가한다. 따라서 첫번째 for문의 index를 s32_I라 하며고 두번째 index를 s32_J라 하면 한 삼각형의 줄의 개수를 s32_Cnt로 받아온 후 s32_I는 0부터 s32_Cnt보다 작을때 까지, s32_J는 s32_I보다 같거나 작을 때 까지 반복해서..