오뚝이개발자

문제 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 나의 풀이 dp를 사용하면 된다. dp 2차원 리스트에 각 위치에는 (0,0)부터의 부분합을 저장한다. 주황색 부분의 부분합을 구하려면 전체 합에서 A, B, C 부분을 빼주면 된다. 식으로 나타내면, (x2,y2)까지의 부분합 - (A+B) - (A+C) + A 가 된다. A부분이 두번 빼지니까 마지막에 한 번 더 더해주면 된다. 코드 # http..

문제 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 나의 풀이 DP를 사용하는 문제이다. 메모리 제한이 아주 극심해서 여기에 신경쓰면서 코드를 구현해야 한다. 2차원 리스트로 DP를 구현하면 메모리 초과가 발생하므로 각각의 변수에 저장하도록 한다. 코드 # https://www.acmicpc.net/problem/2096 import sys input = sys.stdin.readline N = int(input()) dp = [list(map(int, i..

문제 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/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 나의 풀이 DP를 사용해 쉽게 풀 수 있는 문제이다. input으로 주어진 각 수는 아래의 연산 중 한 가지를 할 수 있다. 2로 나누어 떨어지면 2로 나눈다. 3으로 나누어 떨어지면 3으로 나눈다. 1을 뺀다. 이를 반복해서 결과적으로 1이란 수를 만들어야 하는데, 이를 DP의 점화식과 연관지어 생각해보면 쉽다. 만약 내가 10이란 수를 input으로 받는다고 가정해보자. 10->5->4->2->1 10->9->3->1 10->9->8->7->...->1 위의 경우 말고도 10을 1로 만들기 위해선 굉장..

문제 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/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..

문제 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 www.acmicpc.net 생각의 흐름 맨 마지막으로 더하는 수가 각각 1,2,3인 경우로 나누면 dp를 사용해야 함을 알 수 있다. dp[i] =..