글 읽기 - 시간복잡도

lmcoa15 6년 전 0

시간 복잡도와 관련하여 질문있습니다.

처음에 단순한 재귀 호출이라고 접근하였다가 DP로 문제를 풀게 되었는데

찾다보니 시간복잡도가 O(N^2 * M) 이라고 되어있는 것을 봤는데 제가 생각했을 때 재귀 호출이여서

O(2^n) 이라고 생각했습니다.

근데 다시 보니깐 이미 처리한 부분을 dp로 처리하고 바로 리턴하는 것을 보면서 잘못된 생각인 것은 알았지만

정확히 저 코드에서 어떤 부분이 O(N^2 * M)인지 잘모르겠습니다. 이와 비슷한 유형의 문제를 보면 시간복잡도를 생각해야 될 것같은데

이 부분이 잘 이해가 되지 않습니다.

그리고 이런 유형의 문제를 메모이제이션이라고 하는데 정확히 메모이제이션이 다이나믹 프로그래밍인지 아니면

다이나믹 프로그래밍중에서 Top-down으로 하는 것을 메모이제이션이라고 하는지 궁금합니다.

답변부탁드립니다 ㅠㅠ

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
#pragma warning(disable:4996)

int N, M;
int arr[101] = { 0 };
int dp[101][101] = { 0 };
int min_value = -10000000;
int solve(int n, int m) {
	if (m == 0) return 0;
	if (n < 1) return min_value;


	int &ret = dp[n][m];
	if (ret != -1)	return ret;
	ret = solve(n - 1, m);

	int k = 0;
	for (int i = n; i > 0; i--) {
		k = solve(i - 2, m - 1) + arr[n] - arr[i - 1];
		ret = max(ret, k);
	}

	return ret;
}
int main() {

	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);

	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		scanf("%d", &arr[i]);
		arr[i] += arr[i - 1];
	}

	memset(dp, -1, sizeof(dp));
	cout << solve(N, M) << endl;

	return 0;
}

kesakiyo 6년 전 1

dynamic programming 이란 말의 정확한 정의는 큰 문제를 여러개의 작은 문제들로 나눠서 해결하는 방법론입니다.

이에 반해 memoization 이란 한번 계산한 값을 array와 같이 접근이 용이한 곳에 저장한 뒤 필요할 때 다시 사용하는 기법입니다.

두개의 뜻이 엄연히 다르지요.

dynamic programming과 memoization은 둘 중 어떤것도 다른 것의 서브셋 개념이 아닙니다.

이 개념을 정확히 이해를 하셨다면 본인이 작성한 코드가 어떤 패턴으로 작성이 됐고 어떤 방법론을 사용해서 풀었는지 자세히 설명할 수 있을것이라 생각합니다.

시간 복잡도를 계산하는 부분 또한 훈련이 필요한 부분인데 정말 간략하게 설명을 하자면

최대 dp테이블의 크기만큼 함수호출이 일어날텐데 각각의 그 함수호출 내에서 n번만큼 for문이 돌게되니

그러한 시간복잡도가 나오는 것입니다.

lmcoa15 6년 전 0

dynamic programming랑 메모이제이션을 명확하게 구분해주셔서 감사합니다.

시간복잡도는 뭔가 확실이 이해가 되지는 않지만 말씀해주신게 무슨 말인지 알 것 같기도해서.. 문제를 조금 더 많이 풀어봐야 할 것 같습니다.

감사합니다!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간복잡도

lmcoa15 6년 전 0

kesakiyo 6년 전 1

lmcoa15 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말