개발자로 살아남기

신나는 함수 실행은 다이나믹 프로그래밍을 이용하여 구성할 수 있습니다. 계산을 위한 점화식은 이미 문제에 나와 있습니다. 이 계산식을 그대로 구현하고, 계산결과를 배열에 넣어두고 동일한 계산은 이전 계산 결과를 사용하면 됩니다.

현재자리에 1은 앞자리에 0으로 끝난 이친수이고, 현재 자리에 0은 앞자리에 0, 1로 끝난 이친수 모두가 가능하다. 따라서 현재자리의 1은 앞자리 0의 개수이고, 현재라리의 0은 앞자리 0 + 앞자리 1의 개수와 동일하다. https://www.acmicpc.net/problem/2193

하이브에서 다음과 같은 오류가 발생하면 이는 다이나믹 파티션 처리중 생성가능한 파티션 개수 이상의 파티션이 생성되어서 발생하는 것이다. 아래 오류의 내용처럼 해당 설정을 늘여주면 된다. Caused by: org.apache.hadoop.hive.ql.metadata.HiveFatalException: [Error 20004]: Fatal error occurred when node tried to create too many dynamic partitions. The maximum number of dynamic partitions is controlled by hive.exec.max.dynamic.partitions and hive.exec.max.dynamic.partitions.pernode. ..

https://www.acmicpc.net/problem/5721 DP를 이용하여 해결이 가능하다. 한행만 선택이 가능하므로 행마다 따로 선택할 수 있는 최대값을 계산하여 그 값을 이용하여 따로 최대값을 계산해 준다. 하나를 선택하면 다음을 걸러서 선택할 수 있으므로 점화식은 다음과 같다. dp[i] = Math.max(dp[i - 2] + dp[i], dp[i - 1])

1학년 문제는 DP를 이용해서 해결할 수 있습니다. 20까지의 숫자만 이용할 수 있고,+, - 연산만 할 수 있기 때문에 memo[20][연산횟수]로 메모이제이션을 하면 됩니다.

이 문제는 "위상정렬"과 메모이제이션을 이용하여 해결할 수 있다. 인입 간선이 0인 노드를 시작점으로 하여, 건물을 지을 때 걸리는 시간을 메모하여 최종 목적하는 건물을 지을 때 걸리는 시간을 확인하면 된다. https://www.acmicpc.net/problem/1005

DP를 이용하여 해결한다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=298&sca=3050

쉬운 계단수는 앞에서 선택된 숫자 다음에 올 수 있는 숫자는 앞숫자-1, 앞숫자+1 이라는 것을 생각하여 해결 할 수 있다. 자리수가 1일때는 1~9까지 9개가 존재한다. 자리수가 2일때부터 다음숫자에 0이 나올 수가 있다. 앞자리가 0, 9일때는 뒤에 1, 8만 올 수 있으므로 하나만 선택가능하다. 하지만 1~8은 -1 또는 +1 인 숫자가 올 수 있다. 이를 이용하여 다음과 같이 해결하면 된다. memo[length][number] = memo[length-1][number - 1] + memo[length-1][number + 1 이 결과를 MOD 로 나눈 나머지를 저장하면 된다. https://www.acmicpc.net/problem/10844

내리막길은 DFS와 DP를 혼합하여 해결할 수 있는 문제이다. DFS를 이용하여 종점을 찾아서 다시 돌아오면서 DP로 현재 경로에서 종점으로 갈 수 있는 경우를 메모한다. 이미 메모한 곳을 찾으면 해당 값을 반환하면 된다. * -1로 초기화 하여, 방문한 곳을 0으로 표시하면 다시 방문하지 않아도 된다. 최종 위치에서 되돌아 가면서 경로를 표시하고, 새로운 경로로 가면서 최종 위치로 도달할 수 있는 경로를 만나면 그값을 더하여 처리한다. 10 1020 19 18 17 16 15 14 13 12 11 19 18 17 16 15 14 13 12 11 10 18 17 16 15 14 13 12 11 10 9 17 16 15 14 13 12 11 10 9 8 16 15 14 13 12 11 10 9 8 7 15..

두줄로 타일깔기는 라인 길이에 따라 타일을 배열하는 방법을 생각해서 처리하면된다. 구현할 때 재귀를 이용하여 처리하면 stack overflow 가 발생한다. f(n) 을 구하는 방법은 f(n-1) 의 타일 개수에 1 x 2 타일을 하나 추가하는 방법과f(n-2)의 타일 개수에 2 x 2 타일을 추가하는 방법 두개를 더하면 된다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=687&sca=3050http://huiyu.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%ED%83%80%EC%9D%BC-%EC%B1%84%EC%9A%B0%EA%B8%B0-%EB%AC%B8%EC%A0%9C

전깃줄 문제는 다이나믹 알고리즘의 LIS를 응용하는 문제이다. 입력받은 전봇대의 쌍 중에서 하나를 기준으로 정렬하여, 정렬되지 않은 전봇대중 가장 많이 정렬되어 있는 전봇대의 값에서 전체를 빼면 제거해야할 최소의 전봇대 개수가 된다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=684&sca=3050

계단오르기는 다이나믹으로 해결할 수 있다. 연속해서 오른 계단이 하나인 것과 두개인 것을 계산하여 처리할 수 있다. 1번은 연속해서 오른 계단이 하나인것, 즉 두번 뛰어서 오른 계단에 대한 정보를 확인하는 것이다. i-2 번째 계단의 1번 연속, 2번 연속해서 오른 계단의 최대값가 현재 계단의 값의 합이다. 2번은 연속해서 오른계단이 두개인것, 즉 이전계단에서 한번오른 것이다. 이전계단에서 한번오른 값과 현재의 값을 더하여 결정한다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=792&sca=3050

숫자카드 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있다. 27123을 2글자씩 읽어서 숫자로 확인하고 34이상이면 분할한다. 27, 123 으로 분할하고 카드로 표현할 수 있는 형태가 몇개인지 확인한다. 카드로 표현 가능한 개수는 마지막 수를 표현하는 카드가 한자리 수인지, 두자리 수인지로 구분하여 점화식을 구성한다. D[i] = (D[i-1][0] * 2 )/2 + D[i-1][1] + (D[i-1][0] * 2 )/2 끝자리가 한자리수이면 마지막에 하나더 숫자가 붙어서 두자리 또는 한자리가 될수 있기 때문이다. 끝자리가 두자리수 이면 한자리수로 붙어서 표현이 가능하다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=683&sca=3050

LIS 문제중 가장 간단한 형태인것 같다. 숫자들중 순서대로 나보다 큰 숫자들 중 정렬이 가장 많이 되어 있는 숫자를 찾아서 +1을 하여 기록한다. http://saecom-dalcom.tistory.com/9http://comganet.github.io/dp/2016/06/03/dp-1007http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1144&sca=3050

가장높은 탑 쌓기 문제는 다이나믹 프로그래밍을 이용하여 처리한다. 우선 밑면의 넓이 기준으로 정렬을 하면 현재 인덱스보다 작은 인덱스의 무게만 비교하면 넓이는 신경쓰지 않고 확인할 수 있다. 대신 정렬을 이용하기 때문에 기존의 인덱스가 변하게 되므로 인덱스만 따로 저장해 둔다. 그다음은 현재 벽돌보다 작은 무게의 벽돌을 찾아서 현재벽돌의 높이 + 작은무게벽돌의 높이(자신의 위에 있는 벽돌의 높이도 추가되어 있음)만 저장한다. 더 큰 높이의 벽돌이 있으면 갱신한다. 올릴 수 있는 벽돌이 없다면 자신의 높이만 저장한다. 이렇게 result 배열에 결과를 저장하고가장 높은 높이의 벽돌을 찾아서 해당 벽돌의 인덱스를 역순으로 찾아서 출력하면 된다. http://www.jungol.co.kr/bbs/board.p..

배낭채우기문제는 다이나믹으로 처리한다. 배낭의 무게를 10부터 이동해가면서, 현재 시점에 최고의 무게를 확인하면서, 현재의 무게를 뺀 이전 무게의 최고값과 현재의 최고값을 더하면서 배낭을 채우면 된다. 보석 배낭무게 무게 가치 1 2 3 4 5 6 7 8 9 10 11 12 13 14 2 40 - 40 40 80 90 120 150 140 190 200 230 260 270 300 3 50 - - 50 50 90 100 130 160 170 200 210 240 270 280 5 110 - - - - 110 110 150 160 190 220 230 260 270 300 10 200 - - - - - - - - - 200 200 240 250 280 맥스값 - 40 50 80 110 120 150 160..