문제 링크 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 문제 해설 기본적인 dp 문제이다. a~b 까지의 합을 구하는 방법을 0~b까지의 누적합 - 0~a까지의 누적합 으로 구하면 매번 구간합을 구하는 시간 복잡도가 j-i 번 -> 2번으로 바뀐다. 정답 코드 #include using namespace std; int arr[100001]; int sum[100001]; //누적합 int main() { int n,..
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42897# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 우선 해당 문제는 레벨4를 책정받았는데, 이것에 너무 홀려서 어렵게만 생각하지말자. 우선 '원형' 이라는 것을 배제하고 일열로 늘어 놓는다고 가정했을 때, x번째 값을 선택한다면 x-1번째 값은 선택할 수 없다. 따라서, 'x-1번째 값을 선택하는 경우의 수'를 따지거나. 'x-2번째와 x번째를 선택하는 경우의 수' 이 두가지를 고려해서 dp를 설계하면 된다. 따라서, 아래..
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42895 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제해설 입력으로 N=3 이 주어지면, 사용할 수 있는 숫자는 3,33,333,.....,333333333( 최대 9개의 N사용 가능 ) 이다. 이 숫자들을 통해 사칙연산을 일정 횟수 수행하여 만들어지는 수들을 set에 저장해나간다. 여기서 "몇개의 N" 을 사용해서 구해지는지를 알아야 최소 값을 찾을 수 있기에, "몇개의 N으로 만들어진 수인가?" 에 대해서도 구해야한다. 처음에는 d..
dp는 상황을 나누고, 그 간의 관계를 파악하여 점화식 혹은 a=b와 같은 고정된 수식으로 표현하여 문제를 효율적으로 해결하는 방식이다. 예를 들어 동전이 연속으로 앞면이 나올 확률을 구한다고 생각해보자. 모든 상황은 결국 나누면 앞면, 뒷면 으로 나뉜다. 이를 수식으로 표현해보자. n-1 째까지 앞면 나올 확률 * 앞면 나올 확률 = n 째까지 앞면 나올 확률 즉 f(n-1)* 1/2 = f(n) 이라는 점화식을 구할 수 있다. dp는 이런 특정 행동 (동전을 던짐) 에 따른 관계의 변화를 수식으로 표현해서 구할 수 있다. (특정행동 n-1번 = 특정행동 n번 이런식으로 생각하면 쉽다.) 전에 knapsack 알고리즘에 대해서도 정리했었는데, dp라고 생각하고 식을 구해도 해결할 수 있다. 추가로 in..
