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

오늘은 출근을 하면서 어떤 문제가 S사 역량 테스트 1번 유형으로 나올 수 있을까를 생각해봤습니다.

기출 문제가 예전 도스시절이나 혹은 그 이전의 게임 형태였었습니다.

그래서 생각한 것이 포트리스입니다.

기억하시는 분들이 있는지 모르겠는데

대포를 쏴서 서로 잡는 게임인데 각도와 초기 속도를 조절하여 적을 맞추는 것입니다.

1) 옆에서 보는 모습으로 구현

대포는 항상 포물선 운동을 하고 있어 2개정도의 상수만 결정해 주면 경로가 나오게 됩니다.

나와 적, 혹은 나와 목표물을 직선으로 표시하고

대포의 경로가 직선을 지나가면 폭파시키는 것이고 지나가지 못하면 불발입니다.

(두 점사이로 포물선이 지나가는 것 계산할 수 있으시죠? 예전 수학시간에 배운 것인데)

입력변수로 위의 상수를 번갈아 주면

출력값으로 폭파 여부를 출력

(그래픽은 생략)

예전에 공학용 계산기 EL9300에서 제공하는 (유사)베이직 프로그램으로 짜서 수업시간에 놀았던 것이 기억나네요.

2) 위에서 보는 모습으로 구현

2차원 평면에 사각형으로 나와 적의 탱크들이 4각형으로 표시되고

입력 변수로 후방에서 쏜 포의 떨어지는 x,y 좌표와 범위

출력값으로 쏘았을때 마다 남아 있는 탱크와 피해량

떨어진 대포의 유효 범위를 4각형, 마름모, 원형으로 표현할 수 있고

원형이라면 4각형인 탱크의 전체가 포함되면 피해량 100%, 조금이라도 걸치면 50%씩 줄어듬

중심점과 반지름이 있을때 주변의 사각형이 안에 들어오는지 걸치는지 밖에 있는지

판단할 수 있으시지요? 1)번의 확장입니다.

그림이 없어 이해를 하실지 모르겠는데 간단히 게임을 구현하는 것이 S사 1번 유형이라면

이 정도면 기출과 비슷한 정도이지 않을까 생각합니다.

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

중간부터 보신분들도 있을 것 같고 어떤 분들을 위한 것인지 다시 한번 말씀을 드리면

진짜 알고리즘을 공부하시려면

1. 다른 강좌를 듣고, 좋은 책을 보시고

2. 유명 온라인저지 사이트에서 좋은 문제를 많이 접하시고

3. 유명한 대표적인 알고리즘을 이해하시면

분명 실력이 올라갑니다.

다만 상반기 공채를 봐야 하는데 이제 부터 위처럼 할 시간이 없거나.

위처럼 했는데 공채에는 어떤 문제가 나올까? 하시는 분들이 보시면 됩니다.

제가 생각하는 것은 다음과 같은 가정에서 시작합니다.

1) 대규모 공채 (1:1 면접은 다 소용없습니다.)

2) 온라인 시험

3) 신입사원 수준

4) 알고리즘이 아니라 업무 역량

5) 시험 볼때 참고자료를 보거나 가져갈수 없슴

위와 같다고 보면 어려운 문제를 낼 수 가 없습니다.

토익처음 시작했을때 다들 점수가 낮았는데 지금은 800/900 넘는 분들이 많은 것 처럼

몇년이 지나면 어려운 문제를 내도 풀 수 있겠지만 아직은 아닌 것 같습니다.

위와 같은 조건일때 나올만한 문제?/Tip?을 이야기 하고 싶었습니다. 

가끔 입력 조건등을 봤을때 출제자는 어려운 알고리즘을 쓰는 것 까지는 바라지 않았는데

이 문제는 DP를 썼어야 했는데, 위상정렬이 필요한 것이었구나 하고 오해?를 하는 경우를 많이 봤습니다.

물론 입력 변수가 많거나 범위가 넓으면 정식 알고리즘을 써야 하지만

그렇지 않은 경우도 많이 있어서 쓰고 있습니다.

문제나 TIP관련 내용도 안쓰고 한 회를 때웠네요.

사실 온라인 공간에 글을 쓰는 것이 창피합니다.

정보 올림피아 금상 정도나 탑코더 우승 쯤 해야 내가 고수니까 잘 들어봐 하고 말이 먹힐 수 도 있곘지만

三人行必有我師 (삼인행 필유아사, 3명이 가면 반드시 내가 배울 것이 있는 사람이 있다.)

란 말을 생각하면서 누군가는 필요한 정보라고 생각해서 쓰고 있습니다.

아직 머리에 해주고 싶은 말이 있어 글을 계속 쓰는데 박박 긁어서 없어지면

그만쓰겠습니다.

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

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

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

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

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

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를

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

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

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

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