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

하고 싶은 이야기의 방향은 다음과 같습니다.

0. 알고리즘 전반에 대해 다루지는 않습니다.

    제가 그런거 할 수 있는 수준도 아니고 프로(IOI 선수들)이 보면

    저와 취준생 수준이 안타깝고 이해가 안갈 수 도 있습니다.

    예전 유머란에 김태희가 과외학생에게 "왜 이게 이해가 안가?" 물어봤다는 이야기도 있고

    (과외학생은 왠지 자신 모르는 것이 너무 미안했다고)

    학교때 선배이기도 한 교수님(대학교때 수학 경시?대회 출신)이 공업수학 시간에

    "너네는 왜 공부를 안하니, 했는데 이게 이게 이해 안가?" 라고 하신 적도 있고

    암튼 천재와 고수는 하수의 맘을 모릅니다.

1. 온라인저지의 세계는 넓고도 깊지만 입사시험용이라면 어떻게 해볼만하다.

2. 온라인저지 시스템이 뭔지 알아야 한다.

3. 입사 시험 정도에 주로 출제되는 것이 무엇일까 생각해 본다.

4. 자료구조 + 알고리즘을 알아야 한다는데 범위는 어느정도일까?

5. 시험을 본다면 외워야 (이해정도를 넘어서) 하는 알고리즘은 어떤 것일까?

6. 어떤 Skill 들이 필요할까?

   이 후는 아직 생각중 입니다.

 

하지만 1:1 대면 인터뷰라면 위의 것 다 필요없습니다.

실력자가 몊마디 물어보면 정말 홀딱 벗겨지는 느낌이 듭니다.

(나는 그 동안 뭐했나. 생각해보면 당연히 알아야 하는 것이고....)

 

그럴려면 지원분야에 대해 넓고도 깊게 알아야 합니다.

하지만 신입사원대상 대규모 온라인 저지 시험이라면 해볼만 합니다.

하루 종일 본다면 신규 아이디어도 있을 수 있지만 3시간 2문제이면 어려운것을 물어보면

합격할 사람이 없습니다.

하지만 이게 몇년 계속되고 정규교육 과정에 알고리즘이 들어가면 점점 문제의 수준과

학생수준이 올라갈 것이라고 생각합니다.

그럼 회사에 입사하는 학생의 수준도 올라가고

(하지만 지금도 모든 SW관련학과에서 알고리즘은 배웁니다.

 또, 알고리즘을 잘하면 프로그램을 잘하냐 이런 반론도 많습니만.

 암튼 기본이 시험 떨어지면 회사에 가서 다른 실력을 보여줄 기회도 없습니다.)

 

 

이번 편은 완전탐색에 대해 좀 더 이야기 해보겠습니다.

 

제가 5편에서 고등학교때 배웠던 순열/조합을 공부하면 도움이 된다고 했는데

다들 자신이 있는지 모르겠네요.

10!, 10P2, 10C2, 10H2, 10Π2 다들 계산하실 줄 아시죠?

 

모르시겠다면 검색해서 계산할 수 있게 해야 합니다.

본인이 제대로 가고 있는지를 대략 확인 할 수 있는 방법입니다.

 

완전탐색으로 계산을 하는데 컴퓨터가 평생해도 안끝날일을 시키고 있고

Timeout이 되는 것을 뻔히 알면서 시키면 안되겠지요.

 

6편에서 쾨니히스베르크의 다리를 소개해 드렸지요.

이 다리 문제를 잘 보면 몇개의 점이 연결된 형태로 변경된다는 것을

아실 수 있습니다. (기하학적 위상수학인가요?)

 

이 문제는 완전탐색으로 한 붓그리기가 안된다는 것을 증명할 수 있습니다.

(실제 쾨니히스베르크 처럼 다리가 몇개 없다면)

모든 경로를 DFS로 가보면 한번씩만 거치고 갈수 있는 방법이 없으니까요.

 

이런 것처럼 많은 문제가 점, 선, 면, 공간의 문제로 변환이 가능합니다.

(Problem Solving으로 위장?된 포장을 벗기면)

 

1. 위 다리 처럼 몇개의 점이 어떤 관계에 따라 이어져 있고 그 점을 선택함으로써

   모든 경우를 따져보는 것

 

2. 문자열처럼 1차원 배열에 문자나 숫자가 주어지고 문자열 찾기라던가

   최대공통문자열, 최대 증가 문자열등.

 

3. 2차원 배열에 좌우/상하간의 관계에 따라 이동하거나 특징에 따라 모으던가

   없애던가.

 

4. 공간상에서 3차원 관계에 따라 경우를 따져보던가 도형을 평면도로 펴서 보면 쉬운 경우도 많이 있습니다.

 

이런 방법과 고등학교때 배운 경우의 수가 합쳐지만 많은 기초적인 Proble Solving 문제를

만들 수 있습니다.

 

올림피아드 수준에서는 이 정도는 기초도 안되는 것이지만 여기를 못지나 가면 더 높은 수준으로 못가고

이 강좌는 목표가 있으니.... 너무 높은 수준까지는 기대하지 마세요.

 

다음 편은 실제 문제와 연결해 보겠습니다.

 

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