[강좌] 프로그램을 배웠으나 알고리즘 시험을 봐야 한다면. #21

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

소프트웨어 공학을 에서 간트차트라던가 CPM(Critical Path Method)를 배웠는데

이번 편은 경로 탐색 관련인데 이전 편 어디선가 잠깐 언급했던 주제입니다.

당신은 이번 과제의 PM이다.

1. 각 단계의 담당자들에게 일정을 확인하였더니 위키의 오른쪽 그림처럼 산정되었다.

이 과제의 최소 소요일정을 계산하여라.

   물론 회사에서는 MS Project등을 써서 실제 손으로 계산하는 경우는 없지만
   일정이 계속 바뀌게 된다면 손으로 계산하는 것 보다 미리 하나 짜두면
   쉽게?할 수 있습니다. (아~ 억지로 문제 만들기 힘듭니다.)

2. 이 그림에는 없지만 시작점과 끝점이 하나로 모이지 않는 경우는 어떻게 할 수 있을까?

시작점도 2개 이상, 끝나는 점도 2개 이상

원래 CPM은 위상정렬을 이용하여 푸는 문제인데 제가 이 문제를 언급한 이유가

위상정렬을 공부하고 위상정렬로 풀라는 뜻이 아닌거 아시지요?

당연히 위상정렬이 무엇인지는 알아야하지만 그건 기술면접용이나 1:1 면접을 하시는 곳에

지원하시면 하시고

초급?인 입사시험용으로는 너무 가혹?합니다.

실제로 내면 풀 수 있는 사람이 거의 없을 거에요.

일단 어떤 문제이든 경우의 수가 적으면 완전탐색으로 가능하다! 라는 자신감을 갖고 나서

하지만 현실은 경우의 수가 크다는 것을 깨닫고

한없이 작아진 나를 바라보고 각종 개념이 괜히 나온 것이 아니구나. 를 깨닫고

이후 공부를 하시면 좋겠습니다.

February 28, 2017 at 08:39AM

클량 - 아카이브