태코놀로지

첫 번째 문제에 이어서 선택한 문제는 백준 온라인 저지의 1149번 문제가 되겠다. 이웃과 서로 다른 색깔의 페인트로 집을 칠할 때, 가능한 초소의 비용을 찾는 문제다. 색은 R, G, B로 한정되어 있으며, 집의 수는 사용자의 입력으로 결정된다. 예를 들면, 아래와 같은 경우를 생각해볼 수 있다. R G B집1| 26 40 83집2| 49 60 57집3| 13 89 99 이 경우의 최소의 값은 (집1-R, 집2-B, 집3-R)로 색칠하는 방법으로 최소비용 96이 답안이 된다. 그리디 알고리즘이나 다른 방법을 통해서도 문제를 풀 수 있겠지만, Overlapping SubProblem 구조와 Optimal Substructure 특징이 두드러지는 문제이므로 다이나믹 프로그래밍을 활용하면 쉽게 해결할 수 있..

이전 게시글에서 다이나믹 프로그래밍에 대한 전반적인 정리를 진행했다. 이제부터는 정리한 내용을 바탕으로 쉬운 문제부터 조금 난이도가 있는 문제까지 다이나믹 프로그래밍 방법을 활용해서 풀어보고, 그 과정을 정리해본다. 첫 번째로 선택한 문제는 백준 온라인 저지의 1932번 문제이자, 프로젝트 오일러의 18번, 67번 문제가 되겠다. 세 문제는 동일한 문제로 삼각형의 하단을 따라 내려가면서 합이 최대가 되는 수를 찾는 문제다. 삼각형의 크기가 커짐에 따라서 경우의 수가 기하급수적으로 늘어나므로 다이나믹 프로그래밍을 통해 해결하는 것이 바람직하다. 특히 프로젝트 오일러의 67번 문제의 경우 상당히 빠른 연산을 통하더라도 산술적으로 200억년의 시간이 소요된다고 한다. 이에 반해 효율적인 다이나믹 프로그래밍을 ..

피보나치 수열과 피사노 주기(Pisano Period) 최근 백준 온라인 저지 문제를 풀고 있는데, 신기하면서도 골치아팠던 내용에 대해서 끄적거려본다. 오늘 푼 문제는 시간초과가 발생해서 다른 방법으로 풀었지만, 그 내용이 궁금해서 검색하다가 알게 되었다. 주로 피보나치 수를 구할 때는 재귀를 많이 활용하는데 퍼포먼스가 상당히 떨어진다. 이에 메모이제이션/이터레이션의 방법으로 구하는 경우가 다반사다. 이번 문제는 위 세 가지 방법으로 모두 시간초과를 당해서, 내용을 찾아보니 행렬 곱 연산을 활용하는 또하나의 방법을 알게되었다. 그리고 이 행렬 곱 연산 방법으로 해결했다. 마지막으로는 해당 문제에만 적용할 수 있었던 특이한 방법인데. 문제는 n번째 피보나치 수를 1,000,000으로 나눈 나머지를 출력하는..

최대공약수는 유클리드 호제법으로 구하는 것이 빠르다. 백준 온라인 저지 문제 중에서 간단하면서도 골치아프게 한 녀석이 있어서 기억하고자 글로 남긴다. 문제는 참 간단한 최대공약수 구하기. 그런데 시간 제한이 있기 때문에 난감했다. 정답은 나오지만 늘 '시간초과'로 인해서 정답처리가 되지 않았다. 익숙하고 무난한 문제였기에 설렁설렁 생각했는데 오산이었다. 시간을 줄이기 위해서 갖은 술수를 부렸으나 알고리즘 자체가 잘못되었고, 아마 이 문제는 딱 정해진 알고리즘으로만 풀이가 가능했으리라 생각한다. 제목에서도 언급한 것처럼 유클리드 호제법이라는 방법을 통해서 구현하여 단번에 통과되었다. 이전에 작성한 알고리즘도 틀린 것은 아니었지만, 확연히 연산 수에서부터 큰 차이가 난다. Source Code (Github..