프로그램을 배웠으나 알고리즘 시험을 봐야 한다면. #31

한동안 글을 안썼더니 머리에 고인 것이 있어서 연속해서 써봅니다.

 

길찾기 문제 많이 보셨지요?

10x10 배열에 중간 중간에 숫자가 있고

S에서 시작 E에서 끝날때 최대값은?

이동은 아래와 우측 방향 밖에 움직일 수 없음

 

S000000600

0007000000

0000004000

0900000000

0000000800

0000100000

0900040000

0000000000

0003000000

000000070E

 

이것을 푸는 방법은 어떤 것이 있을까요?

 

정말 알고리즘을 배우지 않은 사람은 눈으로 봐서 어떻게 하든 큰값을 연결하려고 합니다.

사람은 보통 그리디 방법으로 생각하지요.

직관이 그런것 같기도 하지만 바둑에서 수 읽기를 한다고 하니 어느 정도는 탐색을 하는 것 같고

일단 사람이 하는 방법은 항상은 최선의 방법이라는 보장은 없습니다.

 

우리가 배운 DFS, BFS, 중복조합 그리고 DP가 있을 수 있을 것 같습니다.

여기의 DP는 정말 간단한 기초 중에 기초이니 여기까지는 해보세요.

(정말 한 문제를 여러가지 방법으로 풀어보세요.)

 

그리고 중복조합을 특별히 이야기 하는 것은 모든 조합을 다 구하고 빼는 것이 훨씬 더 쉽기 때문입니다.

위의 경우 이동은 18번 (9+9) 이므로

우측과 하측츨 섞어서 9번씩만 조합으로 뽑기가 쉽지 않습니다. 

차라리 아래처럼 많이 뽑은 후에 고르는 것이 훨씬 쉽습니다.

 

00000 00000 00000 000 > 11111 11111 11111 111 까지 선택할 수 있는데

 

이 경로는 아래와 우측을 9개씩만 선택해야 하기 때문에 갯수를 세서 0이 9개가 아니면 경로 계산을 하지 않으면 됩니다.

시작에서 0은 좌측 1은 아래로 경우의 수가 시키는 대로만 따라가면서 점수를 더하여 최대의 값이 답이 됩니다.

 

물론 DP가 비교도 할 수 없게 빠르고 보통 DFS로 풀지만

고등학교때 수학처럼 푸는 방법은 다양하고 하다 보면 점점 좋은 방법을 생각할 수 있는 것 같습니다.

 

이렇게 쉬운 문제를 묻지는 않겠지만 문제를 보면 다양한 방법으로 생각해 보시라고 써봤습니다.

 

#삼성_소프트웨어_역량_테스트