글 읽기 - 성능개선 및 재귀

injoon2018 5년 전 0

답변 달아주셔서 맞았습니다!

그런데 코드가 성능이 좋지가 않습니다 ㅠ

cin.tie(NULL); ios_base::sync_with_stdio(false); 를 하기전에는 시간도 32ms가 나오고 메모리도 조금 많이 먹는 것 같습니다.

요즘 학교에서 자료구조를 배우고 있는데, 공간복잡도보다는 우선은 시간복잡도에 더 치중을 하라고 들었습니다.

0ms와 어떤 차이가 있는 것일까요?

그리고 이걸 재귀로 풀 수도 있나요??

알고리즘 분류가 동적계획법으로 되어있는데 전 그냥 메모이제이션만 썼기 때문에 찜찜하네요;;

#include <iostream>
using namespace std;
int memo2[505][505];int triangle[505][505];

int main(void)
{
	cin.tie(NULL);		//cin과 cout을 묶지 않아서 속도 향상?
	ios_base::sync_with_stdio(false);	//c와 동기화를 해제해서 속도
	int number;
	cin >> number;
	for (int i = 0; i < number; i++)
	{
		for (int k = 0; k < i+1; k++)
			cin>>triangle[i][k];
	}
	memo2[0][0] = triangle[0][0];
	for (int i = 1; i < number; i++)
	{
		for (int k = 0; k < i + 1; k++)
		{
			if (k == 0)
				memo2[i][k] = memo2[i - 1][k] + triangle[i][k];
			else if (k == i)
				memo2[i][k] = memo2[i - 1][k-1] + triangle[i][k];
			else
			{
				if (memo2[i - 1][k - 1] + triangle[i][k] > memo2[i - 1][k] + triangle[i][k])
					memo2[i][k] = memo2[i - 1][k - 1] + triangle[i][k];
				else
					memo2[i][k] = memo2[i - 1][k] + triangle[i][k];
			}
		}
	}
	int highest = memo2[number - 1][0];
	for (int i = 0; i < number; i++)
	{
		if (highest < memo2[number - 1][i])
			highest = memo2[number - 1][i];
	}
	cout << highest << "\n";
}

kimsy96 5년 전 1

동적계획법이란게 부분문제를 여러번 계산하지 않고 메모를 해서 중복계산을 방지하여 속도를 올리는 풀이니까 이 풀이도 동적계획법이라고 할 수 있겠지요

속도가 느린 이유는.. 음 이풀이도 채점데이터를 모두 통과했고 논리상으로도 틀린게 없어보이긴 합니다만 저렇게 조건문으로 분기를 많이 나눌필요없이 짧게 구현이 가능합니다.

그러면 속도가 더 올라가겠죠

다이나믹 프로그래밍을 접근하는 방법에는 재귀적 동적계획법과 이런 식의 반복적 동적계획법이 있습니다. 아무거나 한 가지 방향으로 밀고 나가시면 될거 같습니다. 풀이는 크게 다르지 않습니다만 반복적 동적계획법을 풀 때 부분 문제간 의존관계를 고려하지 않아도 된다는 장점 정도..?

kimsy96 5년 전 1

너무 옛날에 풀어서 잘 기억이 안나지만.

반복적 계획법으로는 식이 이렇게 좀 더 간단히 구현 가능할거 같고

for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            dp[i][j]=max(dp[i-1][j]+arr[i][j],dp[i-1][j-1]+arr[i][j]);
        }
    }

kimsy96 5년 전 1

재귀dp는 이런식으로..?

int solve(int i,int j)
{
    if(i==n)
        return arr[i][j];
    int &ret=dp[i][j];
    if(ret!=-1)
        return ret;
    ret=0;
    ret=max(solve(i+1,j),solve(i+1,j+1))+arr[i][j];
    return ret;
}

kimsy96 5년 전 1

젤 윗댓글이 이상하네요

~~반복적 동적계획법~~을 풀 때 부분 문제간 의존관계를 고려하지 않아도 된다는 장점 정도..? --> 재귀적 동적계획법 ㅇㅇ

injoon2018 5년 전 0

감사합니다 덕분에 동적계획법에 대해 조금 더 알게되었습니다!

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

문제

문제

출처

ICPC

성능개선 및 재귀

injoon2018 5년 전 0

kimsy96 5년 전 1

kimsy96 5년 전 1

kimsy96 5년 전 1

kimsy96 5년 전 1

injoon2018 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말