동적프로그래밍 코드 질문입니다!

문제. 알파벳 {a, b, c} 세 원소로 구성된 연산 테이블이 있고 테이블의 행, 열, 해당 교차하는 값 3가지를 통해서 {aa = b, ab =b, ac=a} 와 같은 값을 얻을 수 있다.
a b c
a b b a
b c b a
c a c c

이러한 값을 토대로 임의의 문자열에 대하여 결과가 a가 도출될 수 있는지의 여부를 출력하고(‘possible’ or ‘impossible’) 가능시 연산 방법을 괄호를 통해 연산순서를 나타낼 수 있도록 동적 프로그래밍 기법을 통하여 작성하시오.
예시
입력 : bbbba
결과 : possible, [b((b(bb))a)]

위의 예시에서 테이블을 참고하여 가장 먼저 연산되는 소괄호부터 해석한다면 (bb)는 (b)가
되고, (b(b))는 (b)가 되며 (b)a는 c가 되어 최종적으로 bc=a라는 요구조건을 만족함을 알 수 있다.

  • 언어는 반드시 파이썬을 사용해야 한다
  • 알고리즘은 동적프로그래밍 기법만 허용(재귀 사용 X)
  • 여러 경우가 있을 경우 처음으로 구한 값을 출력
  • 입력 값인 문자열의 길이는 5로 고정한다.

문제를 풀다가 도저히 감이 안잡혀서 그러는데 혹시 방향성을 제시해주실수 있을까요? ㅠㅠ

1 Like


문제 원본입니다

이거 context free language 멤버십 알고리즘 비슷한 거 같네오 … 촘스키 노말 폼인가?

이게 도움이 될지 모르겟읍니다 ㅠ

감사합니다! 좀 더 찾아봐야겠어요 ㅠㅠ

저도 처음 보고 바로 저걸 떠올렸는데요. 순서가 거꾸로인거 같아서
연속 행렬 곱셈 알고리즘과 같이 쓰면 될거같다는 생각을 했어요.

표를 이렇게 그리고요.

저 파란부분 위쪽을 사용하는거죠.

예를들어 bbbba이면 저표의 12345값은 각각 b,b,b,b,a가 되는거에요

2 Likes

자 그럼 한줄씩 같이 채워봅시다. ^^

1 Like

이건 무엇을뜻하냐면.

(1,2)는 1이랑 2랑 합쳤을때 어떤 결과가 나오는지 보는거에요. 1은 b이고 2도 b이니 (1,2)는 b겠죠?
이렇게 쭉 채워넣습니다.

1 Like

감사합니다 ㅠㅠ

그렇다면 (1,3)은 무엇일까요?

1 2 3 이렇게 있다면
(1,2) 3 이거나
1 (2 3) 이겠죠??

두가지 경우를 모두 구하는데 우리는 이미 (1,2)와 (2,3)을 구해서 표에 써넣었으므로 그걸 이용합니다.

그럼 1, 3은
(1,2) 3 = bb = b
1 (2 3) = bb = b
즉 b네요.

이런식으로 다음 대각선도 쭉 계산해줍니다.

그런데 3,5의 값이 2개가 나오죠? 다 적어줍니다.
모든 경우의 수가 필요해요.

자 (1,4)는 어떻게 구해야할까요?

(1 2 3) 4
1 (2 3 4)
(1 2) (3 4)
로 나뉘겠죠?

그거 모두 계산해서 다 적어주면 됩니다.

(1 2 3) 4 = bb = b
1 (2 3 4) = bb = b
(1 2) (3 4) = bb = b

b네요. 적습니다.

2,5도 똑같이 계산하면
(2 3 4) 5 = ba = c
2 (3 4 5) = ba, bc = c, a
(2 3) (4 5) = bc = a
a,c네요. 적습니다.

자 마지막으로 ㅎㅎㅎㅎ

1,5 계산할 때가 왔습니다. 눈치채셨겠지만 2개로 나누는 것만 하면되요.
이렇게요

1 (2345) = ba,bc = c, a
(12)(345) = ba,bc = c,a
(123)(45) = bc = a
(1234)5 = ba = c
이렇게요.

다 표에 적혀있읍니다. ^^

1,5는 a,c네요 ㅎㅎㅎ
a가 있습니다. POSSIBLE!!

2 Likes

이해되시면 괄호로 구분하는거 설명해드립죠

1 Like

이해 됬습니다 ㅠㅠ
정말 감사합니다 완벽하게 이해되었어요!!

교수님보다 설명 잘하시네요 ㅠㅠ

어떻게 합쳐서 최종적으로 a가 나오는지는 저위의 표로는 판단을 할 수 없죠.
저건 그냥 경우의수를 적어놓은거니까요 ^^

우리에겐 새로운 표가 필요합니다. ㅎㅎㅎㅎ

이 표의 각 값이 어떻게 만들어지는지를 적어놓을 새로운 표를 만듭니다. (이걸 슬라이스 표라고 합시다)
메모리 아껴야하니 걍 아래쪽에 씁시다 ^^;;;
대각선 방향으로 대칭되는게 매칭되는 애들입니다.

(1,2) 이런식으로 묶었을때는 사실 적을 필요가 없죠?
하지만! (1 2) 3이나 1 (2 3)으로 묶을때는 각각의 값이 나오는 걸 적어야합니다. 어떻게 하면 되냐면
시작부터 묶이기 전까지의 인덱스를 적는거죠.

예를들면
(1 2) 3 = 3
1 (2 3) = 2
이렇게요. 사실 위쪽 셀에 적인 값이 하나면 아무거나 적어도 상관없습니다. ㅎㅎㅎ

a,c가 문제겠군요.

(3 4) 5 = c
3 (4 5) = a이므로 같게 적으려면
5,4가 되겠죠?
같은 방식으로 쭉 적으면


이렇게 됩니다. 같은 문자나오는건 아무거나 적어도 되요.

그럼 자 이제 따라가 봅시다.
슬라이스표의 (1,5)가 2이므로
1 (2345)로 나뉜걸 알 수 있죠.
이게 bc잖아요. 그럼 (2,5)에서 c에 해당하는걸 찾습니다.
5네요. 그럼 1((234)5)이렇게 되어있는거네요. c = (234)a이면 234는 b인걸 알 수 있죠?
(2,4)에서 b에 해당하는걸 찾습니다. 3이네요.그러면 (2(34))이렇게 되어있는거죠?

결론적으로 (1((2(34))5))이네요.

4 Likes

야밤에 막써서 가독성 개판이라 이글을 보실 모든분께 정말 죄송합니다 ㅠㅠ

2 Likes

정말 감사합니다

오타가있는데 이거
4,5 네요 ㅎㅎㅎㅎ 순서가 거꾸로되엇군요.
보실때 참고하세용

1 Like

안녕하세요! 코드 보고 이해하는중이였는데요,
(1 2) 3 = 3
1 (2 3) = 2
[1] 이부분도 3,2가 아니라 2,3이 아닌가 해서요.

[2] 그리고, (1,2)(3,4) 같이 두개의 그룹으로 나오는 경우에는 2,4 두가지 경우가 되는건가요?

[3] (1,5) 는 a,c 두개의 값이 들어있는데 슬라이드표에는 왜 2만 있나요??
(2,5) 와 (3,5) 는 각각 4,5가 들어있는거에 반해서요.

아뇨 이부분은 맞아요. 3앞에서 끝나니 3이고 2앞에서 끝나니 2인거죠.

이 말이 경계면 뒤의 숫자를 적는다는거엿어요.

물론 일관된 규칙이있다면 다른규칙을 써도댑니당 ㅎㅎㅎ

1 Like

그니까 저 때 쓴 규칙은 이제

1 2 | 3 4 5

이렇게 나뉘면 3을 적겠다.

1 | 2 3 이면
2를 적겠다는

규칙이었어요.
제가 그때 졸려서 말을 잘못햇네요 ㅎㅎㅎ
헷깔리게해서 죄송합니당

1 Like