오뚝이개발자

문제 https://codingcompetitions.withgoogle.com/kickstart/round/0000000000435a5b/000000000077a882 Kick Start - Google’s Coding Competitions Hone your coding skills with algorithmic puzzles meant for students and those new to coding competitions. Participate in one round or join them all. codingcompetitions.withgoogle.com 나의 풀이 DP를 사용하여 푸는 간단한 문제이다. 문자열의 길이 n만큼의 dp 배열을 만들어서 모두 1로 초기화 한다. 이 배열은 해당 인덱..

문제 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 나의 풀이 DFS와 DP가 합쳐진 유형의 문제이다. 시작지점이 정해진 것이 아니므로 각 지점을 시작지점으로 했을 때 최장거리를 계산해 이들 중 다시 가장 큰 값을 답으로 출력하는 문제이다. 그냥 단순히 모든 지점을 시작점으로 해서 DFS로 탐색해도 되지만 이미 했던 연산을 중복해서 계산하므로 시간초과가 난다. 따라서 DP를 사용해 해당 지점을 시작점으로 했을 때 갈 수 있는 최장경로..

문제 https://programmers.co.kr/learn/courses/30/lessons/12971 코딩테스트 연습 - 스티커 모으기(2) N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다. 원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 programmers.co.kr 나의 풀이 dp를 사용하면 되는 문제이다. 케이스는 두 가지이다. 첫 번째 스티커를 사용하는 경우와 사용하지 않는 경우이다. 따라서 dp1,dp2 두 개의 dp 배열을 만들어 저장하면 된다. dp1의 경우 첫 번째 스티커를 사용하므로 dp1[0] = sticker[0], dp1[1] = dp1[0]이다. dp2의 경우 첫 번째 스티커를 사용..

Dynamic programming이란? 일반적으로, 분할정복 알고리즘과 유사하게 큰 문제를 더 작은 문제로 나누어 푸는 기법(역시 최적해를 찾는데 사용되는 경우가 많다.) 결정적인 차이점은 다음과 같다. 동적 프로그래밍의 경우 작은 문제들이 반복된다.(피보나치의 경우 f(5)를 구하기 위해선 f(4),f(3)이 필요한데 f(4)를 구하기 위해 f(3)이 다시 필요하다.) 동적 프로그래밍의 경우 작은 문제들의 답이 항상 같다는 것이다. 따라서, 위의 경우처럼 반복되는 계산을 줄이기 위해 메모이제이션(Memoization)을 사용 실제로 피보나치 수열을 구하는 함수를 구현할 때, 재귀로 구현하게 되면 반복되는 계산으로 인해 수가 커지면 실행시간이 아주 오래 걸리지만, 동적 프로그래밍으로 구현하면 금방 해결..

문제 https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 생각의 흐름 이전에 포스팅한 1, 2, 3 더하기 3과 유사하지만 차이점은 더할 때 같은 숫자가 연속으로 나오는 경우는 가짓수에 포함하지 않는다는 것이다. 그럼 이를 어떻게 구별해내야 하는가? 단순히 생각해보면 된다. 예컨대, 4를 만드는 가짓수를 구한다고 하자. 이 경우 가능한 case는 1, 2, 3을 만드는 case들에 각각 끝에 3, 2, 1을 더해주어서 만들어야 한다. 근데 이 때 주의할 점은 3을 더할때는 1을 만드는 case들 중..

문제 https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 생각의 흐름 dp[i]에 i를 1, 2, 3 더하기로 i를 만들 수 있는 경우의 수를 저장한다. 동적 프로그래밍을 위한 점화식은 dp[i]=dp[i-1] + dp[i-2] + dp[i-3]이 된다. 이처럼 이전의 3항까지만을 더해주는 이유는 1, 2, 3으로 만드는 수이기 때문에 3만큼 작은 수를 만들 수 있는 가짓수를 더해주면 3이라는 수로 그 부족분을 보충해줄 수 있기 때문이다. 코드 # 백준 15988 t = int(input()) dp..