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

제가 처음에는 공부를 할 때는 알려주는 사람도 없어서

온라인저지 사이트가 있는 줄도 몰라서 정보 올림피아드 기출 문제를 가지고 공부를 시작했는데

 

좋아하는 문제였고 풀고나서 많이 깨달음을 얻은 문제가 있습니다.

 

금광문제라고 "중등"부 문제 였습니다.

https://www.acmicpc.net/problem/10167

 

기출문제이니 찾아보시면 "정식"해법이 있을 텐데 "벤다이어 그램"의 형태가 힌트입니다.

(아~ 1편 사이트에 강좌 뿐만 아니라 기출이 있는데 거기 보시면 해법도 나옵니다.)

 

저의 강좌는 초급 수준이니 초급으로 풀면 아래와 같습니다.

앞에서 말씀드렸던 2차원 완전탐색의 일종이네요. 

 

금광의 좌표가 넓지 않은 곳에 분포되어 있다면

for (x

  for (y

     for (dx

        for (dy

 

외와 같이 4중 포문을 이용하면 풀수 있습니다.

이걸 하다보면 유사한 지역을 반복해서 더하고 있는 것을 알게되고

고민을 더 하다가 보면 DP로 발전할 수 있습니다.

이 문제를 DP라고 하기도 그렇고 아니라고 하기도 그런데

DP를 배우지 않았다고 하더라도 수학적 감이 좀 있으면 생각할 수 있는

방법이기도 합니다. 

 

이것을 이해하면 풀수 있는 유사한 문제가 온라인저지 사이트에 많이 있습니다.

 

어느편에선가 이야기 한 것 처럼 문제를 볼 때 입력변수의 크기를 잘 봐야 합니다.

이 문제는 "두 정수 x와 y(0 ≤ x,y ≤ 10^9)" 이렇게 되어 있어서 완전탐색으로

절대 풀 수 없는 문제라는 것을 알려준 것입니다.

 

하지만 초급 수준에서는 완전 탐색으로 풀어보세요.

 

대부분 온라인저지 사이트에서는 초급 수준은 Fail로 처리되기 때문에

Pass하기 위해서는 DP를 알고 있어야 하는데 이게 큰 허들이 되어서

포기하게 됩니다.

 

제가 온라인 저지로 사람을 뽑는 회사에 담당자라면 이런 문제를

출제하여서 지원자의 수준을 잘 볼 수 있을 것 같습니다,

 

부분점수가 있다고 공지를 하여 초급으로 풀 수 있는 TC를

앞에 높으면 초급으로 풀어도 부분점수를 받을 수 있어서

 

알고리즘이 많이 필요한 부서에는 고득점인 사람을 배정하고

초급만 푼사람은 일반 부서에 배정하는 방법도 있을 것 같습니다.

 

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