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

지난주 시험 잘 보신 분들은 면접이 있지요?

기사 보니 코어 과목 위주로 질문은 한다고 한다던데

 

컴퓨터 구조, OS, 소프트웨어 공학, 네트워크, DB 이런 것일텐데

그냥 읽어보지 말고 물어볼만한 것을 찍어서 적어 놓고 반복해서 읽어보는 것이 중요합니다.

그리고 답변할때 ~ 하는 것 이라고 하지 말고 ~ 하는 시스템, ~ 하는 알고리즘, ~ 하는 방법

이렇게 답변하는 것이 좀 더 좋습니다.

 

지난주 시험 4문제 중 보험설명 문제가 있었지요?

문제는 찾아서 보세요.

 

예전에 2차원 문제 설명할때 겹치는 도형 설명한것 기억 나시나요?

그것과 유사하게 풀면 되는데

 

1. 먼저 최대 설명 건 수 가 N 이라고 하면 NCN 부터 NC1 까지 모든 경우를 찾은 후에

2. 겹치지 않는 것을 구하고

3. 겹치지 않는 것에 대해 건당 보수를 더 해서 가장 큰 것이 답이었지요.

 

여기서  2. 겹치지 않는 것을 구하는 방법이 예전에

2차원 상에서 여러 사각형의 겹치게 그리고 그 넓이는 구하는 것이 있었지요?

그때 원래는 플레인 스위핑이라는 알고리즘을 쓰는 것인데 사각형의 면적이 작으면

사각형의 내부를 1씩 채우고 그 수를 세면 된다고 했는데

 

이 문제가 그것과 아주 유사합니다.

1. 에서 구한 모든 조합의 경우에서 각 경우를 1씩 채워 보면 겹치는 것을 쉽게 알 수 있습니다.

 

플레인 스위핑 처럼 수식으로 하면 기간이 아무리 길어도 같은 시간에 결과가 나오지만

이렇게 채우는 것은 기간이 길면 길수록 채우는 시간이 많아지기 때문에 시간이 많이 걸리나

이 문제 처럼 짧은 기간에 대한 것은 쉽게 풀 수 있습니다.

 

이 문제가 조금 더 어렵게 나오려면 하루에 2건을 처리 할 수 있다 라고 하면 채울때 2까지는

허용하면 쉽게 문제가 풀리게 됩니다. 이때는 오히려 플레인 스위핑 방법이 더 어려울 수 도 있습니다.

 

완전탐색인데 겹치는 것을 구하는 팁만 알면 쉽게 구할 수 있는 문제였습니다.

 

 

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