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

초급 알고리즘 책이라면 뒤편에 조금 설명되어 있지만

알고리즘 대회에서는 가장 중요한 것이 Dynamic Program (동적계획법, 동적프로그램, DP) 입니다.

완전탐색에 비해 성능차이가 어마어마 하게 많이 나지요. 물론 효율적이고, 알아야 대회를 나갈 수 있습니다.

하지만 간단한 문제는 꼭 DP로 풀지 않고 완전탐색으로 풀수 있으면 충분한 경우도 있습니다.

(실행시간은 더 걸리겠지만)

당신은 S사에 입사해서 신입사원입니다.

1. 아래 링크의 오른쪽 그림과 같은 배낭(요즘 용어로 백팩)을 가지고 출장을 가려고 합니다.

   https://ko.wikipedia.org/wiki/%EB%B0%B0%EB%82%AD_%EB%AC%B8%EC%A0%9C

   15Kg을 담을 수 있는 가방에 최대한 넣을 수 있는 가장 큰 금액은 얼마인가?

2. 갯수가 1개씩이 아니고 여려개가 있을때는 가장 큰 금액은 얼마인가?

배낭문제는 대표적인 DP 문제이지만 DP로 풀지 말고 완전탐색으로 풀라고 하는 것입니다.

이런 문제를 딱보고 DP네 하고 쉽게 정석인 DP로 풀수 있으면 제 강좌를 읽기에는 본인 수준이 좀 높은 것이에요.

몇회의 강좌 동안 하고 싶었던 말은 이미 알고 있는 많은 문제들도 완전탐색으로 풀어보자 입니다.

언제인가 말했던 것 처럼 한동안 모든 문제를 완전탐색으로 풀면 세상이 완전탐색으로 보이고

다 이렇게 풀 수 있을 것 같은 착각이 들지만 계산해보면 실제 이렇게 풀 수 있는 문제는

입력조건이 아주 제한적일 때만 입니다.

이걸 느낄때까지 완전탐색으로 하다가 DP로 넘어가야 합니다.

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

이번 편은 쉬어가는(왜?) 편입니다.

온라인저지 시스템에 제출할때 몰라도 크게 상관은 없지만 알면 예상치 못하게 도움이 되는 것입니다.

1. 시험을 볼때 C나 C++을 선택하면 Visual Studio로 JAVA이면 Eclipse로 PC에서 TEST후

    온라인저지 시스템에 제출하게 되는데 이 환경이 달라서 PC에서는 문제가 없지만

    서버에 제출하면 문제가 되는 경우도 있고 서버에는 문제가 없으나 PC에서는

    문제가 있는 경우도 있습니다.

    표준입출력으로 scanf나 printf를 쓰게 되는데 이 함수들이 buffer overflow 발생시킬 수  있는

    문제가 많은 함수라 Visual Studio에서는 못쓰게 하고 대신 scanf_s 같은 함수를 쓰도록 하는데

    검정시스템에서는 scanf를 쓰기 때문에 프로젝트를 만들때 SDL을 체크 해제하게 합니다.

    그런데 SDL을 해제 체크하더라도 warning이 발생하는데 warning이라서 동작에는 문제가 없는데

    신경이 쓰인다면 

     #pragma warning(disable: 4996) 를 사용하면 됩니다.

    (warning 번호가 4996 이니 숫자를 외울필요는 없습니다.) 

    해당 주제는  아래 글을 참고하세요.

    http://lureout.tistory.com/425

    동작에는 문제가 없으니 무시하고 해도 됩니다. 하지만 warning을 무시하는 습관이 들면

    다른 warning도 무시하고 그냥 하는 경우도 발생해서 괜히 시간을 보내는 경우도 많이 있습니다.

2. 입력되는 값의 범위를 잘 봐야 합니다.

    입력되는 값들이 큰 경우는 int 대신 long long을 써야 합니다.

    C를 처음 배울때나 써봤지 그 이후는 잘 안써봤는데 일부러 입력값들을 크게 해서

    long long을 쓰지 않으면 int 범위를 넘게 하는 트릭형 문제들도 있습니다.

    물론 계산 과정 중에 곱셈과 나눗셈이 있을때

    곱셈을 했을때 int 범위가 넘어가는 경우도 꼭 확인이 필요하고

    0으로 나누어지지 않는지 확인도 필요합니다.

    PC에서는 확인이 쉽지만 저지시스템에 넣으면 확인이 안되고 그냥 error가 발생하거나

    틀렸다고 나옵니다.

3. 입력되는 값의 범위에 따라 TC를 만들어봐야 합니다.

    소프트웨어 공학에 Test Case 만드는 것에 대해 나오는데

    입력변수가 여러개라서 모든 조합을 다 할 수 없다면

    1) 각 입력 변수의 경계값

    2) 각 입력 변수의 경계값의 조합

    은 꼭 TEST하고 제출해야 합니다.

    그렇지 않고 주어진 TC만 TEST하고 넣으면 Fail, 왜 안되는지 고민을 많이 하게 됩니다.

4. 많은 분들 아시지만 if 조건에 상수를 앞에 쓰는 습관을 가지면 좋습니다.

    if(a == 3) 대신에 if(a = 3)으로 쓰면 문법적으로는 틀리지 않아서 디버깅에 힘들어지는 경우가 있으나

    if(3 == a) 로 쓰면 혹시 if(3 = a)로 실수를 하더라도 컴파일러가 error를 발생하니 쉽게 찾을 수 있습니다.

    (최신 컴파일러는 warning을 주기도 합니다. 그래서 warning을 무시하면 안됩니다.)

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

소프트웨어 공학을 에서 간트차트라던가 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 면접을 하시는 곳에

지원하시면 하시고

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

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

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

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

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

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

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