1exxn   11달 전

DP로 구현못할거 같아서 그냥 구현해보았습니다.

예제를 보니까 그냥 U -> O -> S -> P -> C 먼저 나오는대로 누르는거 같더라고요

그래서 그렇게 코드 짰는데 틀렸어요.

이런 문제는 DP로 어떻게 푸는지도 궁금하고 제가 문제를 잘못 이해하고 있는지도 궁금합니다.

nflight11   11달 전

현재는 주어진 문자열이 UOSPCUOSPC이고 앞 다섯 문자의 비용이 비쌀 때 최솟값을 출력하지 못하는 것 같습니다. 아래 소스의 출력이 5가 나와야 합니다.

이런 문제는 꽤 표준적인 dp 문제라고 생각됩니다. MR.DR 문자열 등의 유사한 문제가 기억나네요. dp[i][j]를 i번째 문자까지 사용하여 UOSPC 중 앞 j개 문자를 채웠을 때의 비용 최솟값으로 정의한 dp테이블을 생각해 보세요. dp 상태 전이는 정의로부터 거의 명백합니다.

1exxn   11달 전

제가 DP에 대해 잘 몰라서 그러는데

dp 상태 전이는 정의로부터 거의 명백합니다라는 말이 이해가 잘 안가요.

okgo2026   11달 전

dp[i][j]를 i번째 문자까지 사용하여 UOSPC 중 앞 j개 문자를 채웠을 때의 비용 최솟값으로 정의

=> 초깃값?

=> 전이?

ex) fibonacci

f(0)=0

f(1)=1

n>=2, f(n) = f(n-1) + f(n-2) 

lcr7324   11달 전

우선, 먼저 나오면 무조건 누르는 것이 과연 이득일까요? 아래 예시를 보고 생각해봅시다. 떠올리신 풀이는 통상적으로 "그리디"라고 하는 접근법입니다. 이 경우에는 "무조건 가장 먼저 나온 원하는 문자가 나오면 즉시 누르는 것이 이득일 것이다"는 생각으로 풀이를 작성한 것이죠. 이런 풀이는 구현하기가 상대적으로 쉬운 편인 경우가 많기 때문에 대강 따져보아서 반례가 잘 떠오르지 않으면 이 방식으로 바로 코딩하고 제출해보고 싶은 유혹에 빠지기가 쉽습니다. 하지만 이 풀이가 항상 옳다는 증명을 하는 것이 가장 어려운 문제 유형도 그리디라고 저는 생각하며, 언제나 그리디 방식의 풀이를 떠올렸을 때에는 이 풀이가 정당한 이유를 치열하게 생각해보아야 합니다.

예전 설탕 배달 문제의 답변 글에서 DP는 현재 상태의 값을 이전 상태의 값들로부터 구할 방법을 찾는 과정이라고 설명 드렸던 기억이 납니다. 이번에는 최종적으로 구해야 할 dp[x] = 전광판의 왼쪽부터 x번째 모듈까지만 사용했을 때 "UOSPC"를 표시하기 위한 총 비용의 최솟값 (단, 만들 수 없다면 -1)로 정의해봅시다... 그런데 너무 막막하군요. 당장, 아래 예시 입력에서 dp[8] = 45, dp[9] = 45인데 dp[10] = 5입니다. 대체 여기서 무슨 관계를 찾을 수 있을까요?

문제가 너무 복잡해보일 때는 단순하게 바꿔봅시다. 만들어야 하는 문구가 "UOSPC"가 아니라 "U" 한 글자였다면 어떻게 풀었을까요? 이건 너무 간단한가요? 그렇다면 "UO"라면요? "UOS"라면 어떻게 할까요? "UOS"까지 왔을 때의 풀이를 떠올릴 수 있다면 이를 확장해서 "UOSPC"를 만드는 최소 비용을 구하는 풀이로 만드는 것은 어렵지 않을 것입니다. "U"에서 "UO"로 넘어가는 방법의 원리를 깨닫고 이를 "UOS"까지 만들 수 있다면 "UOSPC"를 만드는 방법은 반드시 찾을 수 있을 것입니다.

여기까지의 힌트를 보고 충분히 고민했는데도 잘 모르겠다면 추가 댓글 남겨주세요.

1exxn   11달 전

지금까지 열심히 생각해본 결과 "해답을 못찾았습니다"

일단 U일때 전 U의 비용을 일단 dp에 넣고, 후 U의 비용이 dp에 있는 비용보다 적으면 다시 dp에 넣으면 된다는 건 어렵지 않게 도출해내었습니다.

이제 UO일때 문제가 생겼습니다.

그때 코드 짜면서 생각해서 U -> O로 가면 idx = 0 -> 1이 되는 코드였습니다.

이제 근데 다른 U가 나와서 idx = 0으로 되돌렸을때 문자열이 UOUUU면 완성을 못한 상태여서 -1이 출력이 됩니다.

그렇다고 idx = 1로 유지하면 다른 UO가 나왔을때 그 비용이 더 적으면 최소를 구하는게 아니게 되니까

그렇다고 리스트를 알아서 여러개를 만들 수도 없고


그러면 idx 없이 해보자 하자마자 문제가 생겨요. U -> O라는 순서를 어케 판별하지? 

그리고 제 뇌는 여기서 멈췄습니다.

lcr7324   11달 전

1) $dp_{U}[x]$ = 전광판의 왼쪽부터 x번째 모듈까지만 사용했을 때 "U"를 표시하기 위한 총 비용의 최솟값 (단, 만들 수 없다면 -1)로 정의해봅시다. $dp_{U}$에 관한 점화식을 세울 수 있나요?

2) $dp_{UO}[x]$ = 전광판의 왼쪽부터 x번째 모듈까지만 사용했을 때 "UO"를 표시하기 위한 총 비용의 최솟값 (단, 만들 수 없다면 -1)로 정의해봅시다. $dp_{UO}$에 관한 점화식을 세울 수 있나요?

여기서 중요한 점은, $dp_{U}$에 관한 점화식을 세우는 데 성공했다면 $dp_{UO}$에 관한 점화식에는 $dp_{U}$를 써먹을 수 있다는 것입니다. 어떻게 써먹을 수 있을까요? 계속 고민해봅시다.

okgo2026   11달 전

idx 정보가 굳이 필요할까요?

......U

.......O

.........S

........P

........C

를 보면서 생각해보시면 좋을 거 같습니다.

1exxn   11달 전

임의로 문자열을 "UOSPUOSUU"로 세워보았고 각각의 비용을 "1 5 1 3 4 1 2 6 3"로 한번 세워보았습니다. 

dpu[x]에 관한 점화식을 못 찾겠습니다.

dp만으로 U라는 특정 문자열을 판별할 수 잇는 방법 자체를 찾지를 못해서

lcr7324   11달 전

너무 dp 값 그 자체에만 얽매일 필요가 없습니다. 당연히 이 점화식에는 어느 위치의 문자가 무엇인지에 대한 정보와 어느 위치의 비용이 얼마인지에 대한 정보가 들어가야 합니다.

예시를 조금 바꿔봅시다.

문자열이 "UOSPUOSUU"이고, 각각의 비용이 [5, 4, 3, 2, 3, 2, 3, 2, 1] 이라고 해봅시다.

문제에서 문자열의 $i$번째 문자를 $S_{i}$라 하고 $i$번째 모듈을 키는데 드는 비용을 $a_{i}$라 했으니 이를 그대로 씁시다.

모종의 방법으로 우리가 $dp_{U}[6] = 3$임을 알았다고 합시다. $S_{7} = 'S'$입니다. 그렇다면 $dp_{U}[7]$은 얼마일까요?

답을 알려드리자면 $dp_{U}[7]$은 $dp_{U}[6]$과 마찬가지로 3입니다. 왜 이 값이 $dp_{U}[6]$과 같을까요? 생각해봅시다.

그 다음으로 $dp_{U}[7] = 3$, $S_{8} = 'U'$라는 정보만 가지고 $dp_{U}[8]$의 값을 알아낼 수 있을까요? 부족하다면, 무슨 정보가 추가로 필요할까요? 위에서 언급했지만 아직 사용한 적이 없는 정보 중에서 무엇이 이 자리에 필요할지 생각해봅시다.

lcr7324   11달 전

점화식이 자기 자신의 값만 참조할 필요가 없다는 개념이 잘 이해가 가지 않는다면, 우리가 배열의 최댓값을 구하는 방법을 잘 생각해봅시다.

배열 $\{a\} = \{a_{1}, a_{2}, \cdots, a_{N}\}$이 주어졌을 때 $M_{i} = {\textrm{max}}(a_{1}, a_{2}, \cdots, a_{i})$로 정의해봅시다.

보통 최댓값을 구할 때, "지금까지 구한 최댓값과 현재 위치의 값을 비교해서, 현재 위치의 값이 더 크다면 지금까지 구한 최댓값을 갱신"하는 방식으로 많이 하죠?

이걸 그대로 식으로 옮기면 $M_{i} = {\rm{max}}(M_{i-1}, a_{i})$가 됩니다. 위 문장에서 밑줄 친 부분이 이 식에서 어디에 대응되는지 보이시나요?

그런데 이것 또한 점화식입니다. 우리가 평소에 인지를 잘 못할 뿐이지, 우리는 이미 점화식의 개념을 문제 풀이에 많이 활용하고 있습니다. 이것을 인지하고 의식적으로 잘 활용할 수만 있으면 DP 문제의 접근도 훨씬 수월해진다고 생각합니다.

1exxn   11달 전


dpu[x]의 인덱스도 1부터 시작하나요?

만약 그렇다면

문자열 s : UOSPUOSUU
비용 p : [5, 4, 3, 2, 3, 2, 3, 2, 1]

이라고 했을때

dpu[6] = dpu[7] = 3인 이유가 U를 표시하기 위한 최소 비용을 구하는데 도움이 되지 않기 때문이라고 생각합니다.

s8 = U이고, dpu[7] = 3일때 dpu[8]의 값은 min(dp[7], p[8])이라고 생각합니다.

결론 : dpu의 점화식 : if U: dp[i] = min(dp[i-1], p[i])


이제 UO를 표시하기 위한 최소 비용 구하기로 확장해보았습니다.

dpuo[x]라 할때 일단 [5, 9, 9, 9, 2, 5, 5, 2, 1] 

점화식 : 

처음 생각할땐 이렇게 했는데 문제가 어디가 UO인지를 모르는게 문제입니다.


일단 여기까지 생각해보았습니다.

nflight11   11달 전

@1exxn

dp_UO [i]가 dp_UO [i-1]의 값과 다르다는 것은 최소한 i번째까지 봤을 때 i-1번째까지 봤을 때는 나타나지 않았던 UO가 생겼다는 소리입니다. 그러면 i번째 문자는 반드시 O여야만 합니다.


이외에 또 다른 조건이 하나 더 있어야만 갱신이 일어날 수 있으나... 그 조건이 무엇일지 알아내는 건 연습문제로 남기겠습니다.

lcr7324   11달 전

예전 글에서도 언급했지만, 점화식을 문장 형태로 정확하게 서술할 수 있어야 합니다. 식이 실제로 성립하냐 아니냐를 떠나서 문장이 온전해야 합니다. 국어 선생님에게 가서 이 문장이 비문인지 아닌지, 설명이 충분한지 여쭤보았을 때 문제가 없다는 답변을 받을 수 있어야 합니다. 국어 선생님은 일반적으로 수학과 프로그래밍에는 관심이 많지 않으실테니, 식이 실제로 성립하는지 아닌지는 아마도 잘 모르실 겁니다. 하지만 쓰인 글에 문법적인 하자가 없는지, 논리적으로 잘 완성된 문장인지는 검토해주실 수 있겠죠. 논리적으로 글 쓰는 방법을 연습한다고 생각해봅시다.

$dp_{U}[x]$를 전광판의 왼쪽부터 x번째 모듈까지만 사용했을 때 "U"를 표시하기 위한 총 비용의 최솟값 (단, 만들 수 없다면 -1)로 정의했었습니다.

"만약 $U$라면, $dp_{U}[i]$는  $dp_{U}[i-1]$과 전광판의 $i$번째 모듈을 키는데 드는 비용 중 작은 값이다."

1) 위 문장은 문법적으로 올바른가요? 빠진 문장 요소가 있지는 않나요?

2) 위 문장은 항상 참인가요?

3) 위 문장은 $dp_{U}[i]$를 구하는 데에 필요한 모든 정보를 포함하고 있나요?

위의 세 질문은 전부 구별되는 질문입니다. 작성해주신 점화식 if U: dp[i] = min(dp[i-1], p[i])를 그대로 문장으로 옮긴 것입니다. 특히 1번 질문은 이 문제의 풀이를 알지 못하는 국어 선생님도 답변할 수 있는 내용이라는 것을 한번 생각해보세요.

각각에 대해 답변해보겠습니다.

1) 주어가 빠졌습니다. 무엇이 "만약 $U$"일 때를 말하는 것인지 주어가 들어가야 완성된 문장이 됩니다. 이 문제를 풀고 있는 사람이라면 저 문장의 주어가 전광판의 $i$번째 모듈이라는 것을 대강 알아듣겠지만 컴퓨터는 절대 알아들을 수 없습니다.

2) $dp_{U}[i−1]$이 $-1$인 경우에 성립하지 않습니다.

3) 전광판의 $i$번째 모듈이 $U$가 아닌 경우에 $dp_{U}[i]$를 구할 방법이 서술되지 않았습니다.

왜 이렇게까지 깐깐하게 구냐고요? 이렇게까지 깐깐하게 따져야 정확하게 풀이를 낼 수 있고, $U$에서 $UO$로 넘어가는 풀이를 정확하게 찾아낼 수 있기 때문입니다. 정확히 어떤 경우에 $dp_{U}[x]$가 $-1$이고, 어떤 경우에 $-1$이 아닌지 그 조건을 명확히 설명할 수 있어야 하고, 정확히 어떤 경우에 $dp_{U}[i]$의 값이 $dp_{U}[i−1]$의 값과 달라지는지 이해해야 이 아이디어를 기반으로 $dp_{UO}$와 $dp_{U}$를 연관지을 수 있기 때문입니다.

이 글타래에서 제가 작성하고 있는 모든 글은 인덱스 $1$에서 시작하는 것을 기준으로 삼고 있는데, 편의상 $dp_{U}[0]=−1$로 정의하겠습니다.

지금까지 고민하신 내용에서 다음 사실은 깨달으셨을 거라고 생각됩니다.

"모든 $i \ge 1$인 $i$에 대해, $dp_{U}[i]$의 값은 $dp_{U}[i−1], S[i], a[i]$에만 의존한다."

다시 말해 $dp_{U}[i]$를 구하는 점화식을 저 세 값과 기타 상수들만을 이용해서 표현할 수 있다는 것입니다. 깔끔하고 멋진 식 하나를 딱 완성하고 싶은 마음이 있을 수 있겠지만 그보다 우선 논리적으로 완성된 글의 형태로 점화식을 쭉 서술해봅시다. 힌트를 드리자면 "만약 ~~ 하다면 $dp_{U}[i]=−1$, 그렇지 않고 ~~ 하다면 ~~~, ..." 같은 형태로 짧은 문장 하나로 딱 떨어지지 않을 것이니 모든 경우를 차분히 잘 정리해봅시다.

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