DP에 관한 질문이 있습니다 선생님들 (장문)

PS 갤러리
마이너

알고리즘 문제를 해결하는 Problem Solving을 다루는 갤러리입니다.

매니저

캐티(tae826)

부매니저

하루룽(ailedear) Gravekper(gravekpe…) 옥토끼(moonrabb…) 나는최고(mebest)

개설일

2018-05-28

[질문] DP에 관한 질문이 있습니다 선생님들 (장문)앱에서 작성

ㅇㅇ(211.36) 2023.07.22 22:48:54

조회 498 추천 2 댓글 11

안녕하십니까 선생님들 탑다운 형식과 바텀업 형식의 차이점에 대해 질문드리려고 합니다

제 질문의도를 잘 나타낸 문제를 찾기 힘들어서 예를 들기 위한 간단한 문제를 만들어보겠습니다 제가 급조한 문제라 오류가 있을 수 있고, 제 풀이법이 비효율적일 수 있으나 질문의도를 위한 것으로 생각해주면 감사하겠습니다.

[문제]

1번 지역부터 N번 지역까지 N개의 지역이 존재한다. 출발은 1번지역이고, 항상 지역의 숫자가 커지는 방향으로만 도로를 따라 이동할 수 있다. 이때 1번지역으로부터 N번지역으로 이동할 때 드는 최소비용을 출력하시오.

[입력]

첫줄에 지역의 개수 N, 도로의 개수 M이 주어진다. 이후 M개의 줄에 a,b,c 가 주어지고, 이는 a부터 b까지 가는 도로의 비용이 c임을 의미한다.

[제한]

2 < N < 100 , 2 < M < 100, 1 <= a < b <= N , 0 < c <100

[출력]

1번지역으로부터 N번지역으로 이동할 때 드는 최소비용

이러한 문제를 dp로 푼다고 하였을 때 먼저 바텀업 방식으로는 pair를 저장하는 vec[100] 배열에 a부터 b까지 가는 비용 c를 vec[a].push_back({b,c}); 이런식으로 저장하고, 일차원 dp배열을 매우 큰 수(INF)로 초기화한 뒤 for문을 통해 다음과 같이 진행할 것 같습니다.

dp[0]=0;

for (int i = 2; i < N; i++) {

for (int j = 1; j < i; j++) {

for ( pair item : vec[j] ) {

if ( item.first == i ) {

dp[i] = min(dp[i], dp[j] + item.second );

}

이런식으로 짜게되면 N이하의 임의의 자연수 k에 대해서 dp[k]에는 k까지의 거리의 최소값이 들어가 있을 것이므로 이 문제에서는 dp[N]만을 출력해주면 될 것입니다.

이 문제를 탑다운으로 풀게될 경우 위와 같이 일차원dp배열을 매우 큰 수(INF)로 초기화 한 뒤 재귀함수를 짜보면

int func(int now) {

if (now == N) return 0;

if (dp[now] == INF)return dp[now];

for (pair item : vec[now]) {

dp[now] = min(dp[now], func(item.first) + item.second);

}

return dp[now];

}

이런식으로 될 것이고, main문에서는 func(0)를 출력해주면 될 것입니다.

여기서 제가 헷갈리는 부분은 탑다운으로 구현하였을 때 dp[k]에 바텀업처럼 1번 지역으로부터 k번지역까지의 거리의 최소값이 들어가있지 않다는 점입니다. 물론 dp[k]에 해당 값이 들어가도록 구현할 수 있는 방법이 있는 것은 알고있습니다. ( func을 N부터 0로 가는 방향으로 재귀문 작성 )

하지만 그렇게 코드를 짜게 될 경우 체크해야 할 것이 많아 번거롭기에 이런 식으로 재귀함수를 짜고 있었는데 제가 지금 짜고있는 코드가 일반적이지 않은것인지, 아니면 탑다운dp 특성상 원래 이렇게 내가 원하는 값이 들어가있지 않은것인지 궁금합니다.

제가 dp문제를 많이 풀어보진 못하였지만, 이제껏 dp문제를 풀 땐 몇차원 dp로 설정해야하는지, 각 차원에는 어떠한 값을 찾아야 하는지를 중점적으로 생각하면서 풀이하고 있었고, 위 문제와 같은 경우 "dp를 1차원으로 설정하고, dp[k]에 k번째까지 가는데 드는 최소비용을 저장하자" 라는 사고과정을 거친 뒤 코딩을 하기 시작합니다. boj 2098번 TSP문제와 같은 최소비용문제에서는 위 탑다운 풀이방법처럼 출발점부터 시작하는 재귀문으로 해결하기에 원래 탑다운이 그런것인지 헷갈려서 질문드렸습니다.

제가 헷갈리는 부분을 정확하게 알리고 질문하고싶어 글이 굉장히 늘어져서 읽기에 굉장히 불편하시겠지만 양해부탁드립니다. 감사합니다.

고정닉 0

전체 댓글 0개

등록순

본문 보기

타인의 권리를 침해하거나 명예를 훼손하는 댓글은 운영원칙 및 관련 법률에 제재를 받을 수 있습니다.
Shift+Enter 키를 동시에 누르면 줄바꿈이 됩니다.

갤러리 리스트
번호	말머리	제목	글쓴이	작성일	조회	추천
2872	설문	연예인 안됐으면 어쩔 뻔, 누가 봐도 천상 연예인은?	운영자	24/06/17	-	-
39128	일반	아오 민수시치... 내 시간...	ㅇㅇ(1.245)	23.09.28	227	1
39127	일반	1557 [6]	ㅇㅇ(14.51)	23.09.28	362	4
39126	일반	28306 풀이 기원 D+30 [3]	ㅇㅇ(119.204)	23.09.28	160	1
39125	일반	오큰수 왜 deque 쓰면 안 풀리지? [3]	ㅇㅇ(1.241)	23.09.28	291	0
39124	일반	문제 풀이 방송이나 할까 [15]	무구정광대다라니경	23.09.28	408	0
39123	일반	아레나 레이팅 바꼈네	ㅇㅇ(61.101)	23.09.28	158	0
39122	일반	보통 메이저급 대회 수상은 몇학년때 함? [6]	ㅇㅇ(14.54)	23.09.28	422	0
39121	일반	scpc 4번은 다가리고 보면 존나 어렵지 [2]	ㅇㅇ(58.124)	23.09.28	340	0
39120	일반	현실에서 잘한다는 소리듣는 실력은 대충 어디부터일까 [20]	ㅇㅇ(118.235)	23.09.28	543	1
39119	일반	scpc 4번이 쉬운것도 아니였는데 [2]	ㅇㅇ(118.235)	23.09.28	295	0
39117	일반	치터새끼 부계판 것 같은데 신고넣어야지 ^오^ [9]	ㅇㅇ(218.50)	23.09.28	579	7
39116	일반	파이썬 비트 연산 질문 [4]	ㅇㅇ(116.36)	23.09.28	168	0
39115	질문	실랜디 80%이상이면 코포에서 어느정도임? [7]	ㅇㅇ(14.33)	23.09.28	452	0
39114	일반	이번 SCPC 물로켓? [7]	ㅇㅇ(106.101)	23.09.28	424	1
39113	일반	대학별 scpc 수상자수(updated ver) [1]	ㅇㅇ(58.76)	23.09.28	837	14
39112	일반	자스로 코테 준비하려는데 백준 클래스 하면 되는거야?? [8]	ㅇㅇ(182.214)	23.09.27	450	0
39111	일반	어제 E번 [8]	ㅇㅇ(211.243)	23.09.27	206	0
39110	일반	트리 높이랑 레벨 이거 맞음? [5]	ㅇㅇ(175.223)	23.09.27	235	0
39109	일반	피갤에 다시 치터떡밥이 왔구나 [3]	ㅇㅇ(223.39)	23.09.27	381	1
39107	일기	블루 도전 성공했냐 ? [6]	HiLight	23.09.27	560	15

처음 이전 451 452 453 454 455 456 다음 검색

게시물은 1만 개 단위로 검색됩니다.

게시물 검색결과

갤러리 리스트
번호	제목	갤러리	날짜
3000	레클리스 파이어 옛날엔 경파한 노래라고 느꼈는데 되게 끈적이네 이거	아이돌마스터	24/06/21
2999	2024-1 / 컴퓨팅 핵심 / 변해선 교수님	낙성대	24/06/21
2998	92바다 살까?	SFF	24/06/19
2997	네이밍은 상황에 따라 다른거뿐임.	게임업계	24/06/19
2996	python 고수님 도와주십셔...	PYTHON	24/06/18
2995	백준만 풀다가 프로그래머스하니까 적응이 안되네	PS	24/06/17
2994	근데 진짜 출제위원들 ㅂㅅ들임?	정보처리기사	24/06/17
2993	아리엘 포센 너무 좋네	일렉트릭기타	24/06/17
2992	유용한 모드들 모음	마인크래프트	24/06/16
2991	사상최악의쓰래기IDE Xcode	닌텐도 DS	24/06/16
2990	노베 정처기 코딩 연습하려하는데 ide 추천좀	정보처리기사	24/06/15
2989	DLX21 기본팬 연결 방법	데스크탑	24/06/14
2988	프로그래머스 2단계만 박살내면 충분한가?	백엔드	24/06/14
2987	혹시 유니티 게임개발 현업자 있음?	Github	24/06/13
2986	Command Block IDE 1.20.6	마인크래프트	24/06/13
2985	아이고 또 이상한거 출시했네	컴퓨터 본체	24/06/13
2984	백준 풀때 보통 ide로 풀잖아? 실제 대회도 그렇게 함?	PS	24/06/12
2983	베이베이,바오바오,누안누안도 데뷔 공개 행사 라이브했었네	바오패밀리	24/06/12
2982	개발자 모니따 세팅은 걍 고해상도나 울와 단일이 짱인듯요	SFF	24/06/12
2981	M2 써멀패드 붙이고 1년 다되가는 듯	맥북	24/06/12