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

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

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

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

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

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

   https://ko.wikipedia.org/wiki/%ED%81%AC%EB%A6%AC%ED%8B%B0%EC%BB%AC_%ED%8C%A8%EC%8A%A4_%EB%B6%84%EC%84%9D%EB%B2%95

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

   물론 회사에서는 MS Project등을 써서 실제 손으로 계산하는 경우는 없지만

   일정이 계속 바뀌게 된다면 손으로 계산하는 것 보다 미리 하나 짜두면

   쉽게?할 수 있습니다. (아~ 억지로 문제 만들기 힘듭니다.)

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

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

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

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

https://ko.wikipedia.org/wiki/%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC

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

지원하시면 하시고

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

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

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

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

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

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

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

지난편에 많은 문제가 아래와 같다고 하였는데

"전처리 + 모든 경우의 수 + 조건 만족 확인"

전처리도 쉽지 않은 경우도 많이 있습니다.

입코딩으로 하기는 쉬운데 실제 손이 안따라가는 경우도 많이 있죠.

아래와 같은 경우 입코딩을 한다면

"문자열을 받아서 각 문자와 연산자를 분리라고

문자의 끝을 보고 진수를 알면 10진수로 바꾸면 되잖아.

그리고 나서 연산자를 case문에 넣고 연산자 별로 계산하면 되지"

1. 4567O + 10111B 와 같이 여러 진수의 +, -, /, * 연산의 결과는?

    O : 8진수, B : 2진수, D :10진수, H: 16진수

힌트1) gets 을 쓰지 않고 scanf로만으로도 충분

힌트2) 4567O의 문자열에서 일단 무슨 진수를 알수 있을까?

          문자열의 길이를 끝까지 가고 나서 마지막 문자열을 보고 진수를 파악한 다음

          다시 처음 부터 와서 8진수임을 알고 처리할까?

많은 전처리에 대해서는 완전탐색처럼 딱 정해져있지 않아서

과제나 프로젝트를 많이 해본사람이 자신도 모르게 많은 방법을 알고 있을 것 같습니다.

전산관련과를 졸업하고 과제도 했으면 위 정도는 하겠죠.

단, 1시간 30분안에 코딩까지 끝내지 못하는 분이 많이 있을걸요.

연습이 필요합니다.

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

다음 Problem Solving 문제에는 어떤 자료구조를 사용할까요?

1. 8가지 일이 각 30분씩 걸린다고 하면 최종 일을 끝내는 시간은 언제일까?

    (일을 하는 도중에 신규 일이 들어올 수 있고, 모든 일의 시작시간은 다 알고 있음.)

2. 8가지 일이 걸리는 시간이 모두 다를 때는 (따로 값이 주어짐)

3. 2번 문제의 8가지 일이 2명에게 일이 주어질때 가장 빨리 끝나는 시간은?

4. 8가지 일이 다른 위치에 있고 3명에게 각각 전달될 수 있는 시간이 있을때

     (따로 8가지 일거리와 3명의 작업자와의 도달 시간이 주어짐,

     1번에서 이야기 한 것 처럼 일을 하는 도중에 일이 올 수 있으나 언제 일이 오는지는

     알고 있음, 한명이 동시에 2가지 일을 할 수 없음, 일을 끝내는 순서는 상관없음)

    가장 빨리 끝나는 시간은?

1 -> 4번 순으로 문제를 어떻게 풀까 생각해보세요.

그럼 4번도 푸는 방법을 생각할 수 있을 것 같은데

처음부터 4번 문제를 받으면 쉽게 해법이 생각나지 않습니다.

생각해보시라고 이제 부터 푸는 방법은 말씀드리지 않을려구요.

심각한 알고리즘 이런건 아니니 잘 생각해보세요. 

전 회의에서 말씀드린 "전처리 + 모든 경우의 수 + 조건 만족 확인" 에서

전처리는 없는 형태의 문제입니다. 

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