프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr DP 테이블을 활용해서 풀 수 있는 문제. 풀이 코드def solution(k, ranges): result = [] arr = [k] # arr[i] = i번째 값 n = 0 # 작업 횟수 while k > 1: if k % 2 == 0: k //= 2 else: k = k * 3 + 1 n += 1 arr.append(k) dp = [0] * (n + 1) # dp[i] ..
동적프로그래밍
11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net DP 문제다. 수열이 주어졌을 때, 가장 긴 증가하는 부분 수열의 길이를 구하면 되는 문제. 점화식만 구하면 쉽게 풀 수 있는 문제다. 처음에는 dp테이블을 2차원으로 만들어서 dp[i][j] = i번째 수로 시작해서 j번째 수로 끝나는 수열에서 증가하는 부분수열의 길이로 저장하려고 했는데 굳이 그럴 필요 없이, dp테이블을 일차원 배열로 만들고, dp[i]는 i번째 수로 끝나는 증가하..
2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net DP문제다. 규칙은 간단하다. 1. 포도주 잔을 선택하면 그 잔에 들어 있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 마실 수 있는 포도주의 최댓값을 구하면 된다. dp[i]를 i번째 놓여있는 포도주를 먹을 때의 최댓값이라고 했을 때, 처음에는 dp[i] = max(dp[i-2] + arr[i], dp[i-3] + arr[i-1] + arr[i])면 충분하다고 생각했다. 그래서..
10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net DP 문제다. 45656 처럼 인접한 모든 자리의 차이가 1인 수의 개수를 구하는 문제 N이 입력값으로 들어오고, N자리의 계단 수의 개수를 출력하면 된다. 먼저, dp[n][i]라는 2차원 리스트 dp 테이블을 만들었다. 해당 dp테이블은 n자리의 계단 수 중 i로 끝나는 계단 수의 개수를 저장하는 dp테이블이다. 1자리 계단 수와 2자리 계단수를 직접 써보면서 규칙을 찾을 수 있었다. 만약 n자리 계단 수의 경우, 2가지 경우의 수로 나뉜다. 1. n자리 계단 수이고 끝나는 숫자가 0 또는 9인 경우 이 경우에는 이전 숫자가 1 또는 8인 경우에만 가능하다. 즉, dp[n]..
2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net DP 문제다. 계단을 오르면서 얻을 수 있는 총 점수의 최댓값을 출력하면 된다. 규칙은 크게 3가지가 존재한다. 1. 계단은 한번에 한 계단, 혹은 두 계단 씩 오를 수 있다. 2. 연속된 세 계단을 밟을 수 없다. 3. 마지막 계단을 반드시 밟아야 한다. 1번, 3번 조건은 쉽지만 2번 조건이 까다로웠다. 연속된 세 개의 계단을 밟을 수 없으므로 dp테이블을 갱신할 때, 이전 dp값에서 연속된 계단을 밟았는지 아닌지 판단하는 로직이 필요하다고 생각했다. 그래서 count라..
1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net DP 문제다. 정수 삼각형의 맨 꼭대기에서 밑으로 내려오면서 선택된 수의 합이 최대가 되는 경로에 있는 수의 합을 구하는 문제. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 시간 제한이 2초이므로 약 4,000만 번 연산이 가능한데, n의 범위는 500정도밖에 되지 않았다. 그래서 O(N^2)도 여유롭기 때문에 그냥 다 계산하면 되겠다라는 생각이 먼저 들었다. 먼저 dp 배열을 2차원 리스트로 만들어준다. dp[i][j]에는 i번째 층에서 j번째 숫자를 선택했을 때..
1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net DP 문제다. 1번부터 N번의 집을 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 그리고 인접한 집의 색은 달라야 한다. 즉, i번째 집의 색은 i-1번째 집의 색의 영향을 받아서 정해진다. i-1번째 집이 빨강일 경우 i번째 집은 초록, 파랑만 가능하다. i-1번째 집이 초록일 경우 i번째 집은 빨강, 파랑만 가능하다. i-1번째 집이 파랑일 경우 i번째 집은 빨강, 초록만 가능하다. 쉬운 문제인 줄 알았는데 생각보다 까다로웠다. 만..
1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net DP문제다. n개의 정수로 이루어진 임의의 수열에서 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하는 문제 시간 제한은 1초고 n의 범위가 10만이하이므로 O(NlogN)까지는 가능하겠다는 생각을 했다. 먼저 문제를 풀 때, DP는 점화식을 만들어야 하므로 현재 항과 이전 항의 관계를 구하려고 했다. 예를 들어 10 -4 3 1 5 6 -35 12 21 -1 이라는 수열이 있을 때, 5가 포함된 연속합 중 최댓값을 구하려면 1. 10 + (-4) +..
