초보와 고수사이 넘사벽 중간쯤

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

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

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로 풀지만

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

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

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

1. 많이 써서 했던 말인지 아닌지도 헤갈리는데 했다면 한번 더 했다고 생각하세요.

쉬운 온라인 시험에서는 완전탐색으로 풀라고 했는데

다 완전 탐색으로 풀 수 있다고 한 것은 아닙니다.

O(n^3) 처럼 표시된 Big-O Notation 도 좋은데

완전 탐색이라면 순열/조합등의 경우를 따져서 100만가지 정도 나온다면

완전 탐색으로 할만하고 그 이상이면 분명 다른 방법을 물어보고 있는 것입니다.

한가지 100만가지가 넘더라도 가지치기가 되어서 빨리 경우의 수가 줄어든다면

완전 탐색으로도 해볼만 합니다.

제가 한달도 전 쯤에 툭쳐도 완전탐색은 코드는 나와야 한다고 했는데 거기까지는 하신 것이지요?

이게 그 때가서 해야지 하면 절대 안됩니다.

매일 매일 외워서 5분안에 치는 연습을 하고 나머지 시간에는 생각을 하는데 써야지

코드를 치는데 30분 걸리면 생각할 시간이 없어서 계속 조바심 나서 붙을 사람도 떨어집니다.

(중복)순열/(중복)조합/DFS/BFS

2. 온라인 시험은 제출횟수가 있어서 제출한 것 중 가장 잘한 것을 채점하는 것이 아니라

마지막 것을 채점하니 제출할때 마다 복사해 두세요. 제출한 것을 부르는 기능이 있는지 없는지 모르겠네요.

3. PC에서 실행 시키면 DOS창으로 결과가 나오는데 값이 크면 선이 넘어서 잘 안보이는 경우가 있는데

이럴때는 도스창에서 실행시키고 test.exe > test.txt 이런식으로 파이프 라인을 쓰고

test.txt를 열면 결과를 작은 창에서 보지 않고 넓게도 볼 수 있습니다.

4. 조건의 조합을 다 해봐야 합니다.

TC를 다 보여주지 않습니다. 값이 일부만 맞으면 빼먹은 조건이 있을 수 있으니 여러 가지를 해봐야 합니다.

a조건의 가장 작은 값, 큰 값

b조건의 가장 작은 값, 큰 값

a조건의 가장 작은 값과 b조건의 가장 큰 값

a조건의 가장 큰 값과 b조건의 가장 작은 값

최소한 위의 것은 TC를 만들어 해보야 합니다.

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

요즘 아이들과 포켓몬Go를 하는데

이 게임과 알고리즘 문제를 어떻게 합쳐볼까 고민하다가 아래와 같이 생각해 봤습니다.

1) 지도상(보통 2차원 격자, 1간 이동에 1분 소요)에 여러 포켓몬의 위치, 해당 포켓몬의 CP, 사라지는 시간을 알고 있을때,

    얻을 수 있는 포켓폰의 CP의 최대합은 얼마인가?

    (포켓몬 잡는 시간은 무시)

    일반적인 TSP 문제 ( https://en.wikipedia.org/wiki/Travelling_salesman_problem ) 와 유사하지만

    도달 할 때 이미 포켓몬이 없어지는 경우가 있으니 그것도 고려해야 합니다.

2) 지도 포켓스탑이 위치가 나와 있고 한번 돌리면 5분마다 다시 활성화가 된다고 할때

    지도상의 어느 경로로 돌아야 포켓스탑을 가장 효율적으로 사용할 수 있는가?

    (1시간 동안 포켓스탑 노가다를 한다고 가정)

이런 종류의 문제를 만들 수 있을 것 같습니다.

저도 실제 문제로 만들거나 풀어본 것은 아니지만 충분히 문제로 만들 수 있을 것 같습니다.

게임만 하지 마시고 이런 게임을 어떻게 만들 수 있을까? 아니면 어떤 알고리즘과 연결될 수 있을까?

를 생각해 보면 나중에 비슷한 문제를 만났을때 당황하지 않을 것 같습니다.

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