injoon2018   2년 전

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

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

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

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

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

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

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

kimsy96   2년 전

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

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

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

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

kimsy96   2년 전

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

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


kimsy96   2년 전

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

kimsy96   2년 전

젤 윗댓글이 이상하네요

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

injoon2018   2년 전

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

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