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

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

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

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

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

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

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

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

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

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

    가장 빨리 끝나는 시간은?

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

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

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

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

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

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

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

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

지난편까지 점부터 3차원 공간의 기본 문제를 소개했다면

이제 조금 복잡하게 모든 경우릐 수를 구하는 것에 대해 생각해 봅니다.

1. 장기에서 차가 2번 움직일 수 있는 경우의 수는 몇가지 인가. 

2. A그룹에 4명, B그룹에 4명, C그룹에 4명이 있다.

   그룹을 섞어서 3명을 뽑아서 팀을 만드는 조건은

3. 10개의 직사각형 거울중 3개를 거는 방법은 몇가지 인가?

   (거울은 가로/세로로 걸 수 있다.)

문제는 일단, 전처리 + 모든 경우의 수 + 조건 만족 확인 로 푸는 경우가 많은데

지금까지는 계속 모든 경우의 수를 찾는 연습을 하고 있습니다.

1. 궁쪽을 빼면 상하로 10칸 좌우로 9칸을 움직일 수 있네요.

    일단 막혀 못갈 수 도 있지만 일단 움직일수 있는 경우가 좌우/상하가

    따로 있다고 생각하지 말고 19π2 중복 순열로 한번에 계산 하는 것이 훤씬 편합니다.

    상,하,좌,우 중 하나 또 한번 상,하,좌,우 중 하나 를 고르면 너무 복잡해집니다.

    19π2를 의 모든 조건을 구하고 1~10까지는 상하의 좌표, 11~19까지는 좌우의 좌표로 생각

    차가 움직일때는 순서와 관련있으니 순열(중복)

2. 각 그룹을 따로 생각하지 말고 1~4까지는 A그룹, 5~8까지는 B그룹 이렇게 생각하고

    12C3의 모든 경우를 생각하면 되고, 한그룹에서 2명이나 3명이 나오면 안된다는 조건이 있으면

    일단 구한 12C3에서 해당 조건을 빼면 되고

3. 10C3을 고르면 될 것 같지만 직사격형 거울을 돌려서 거는 경우가 있으니 아예 거울의 형태가

    2가지라고 생각하면 쉽습니다. 그래서 20C3을 하여 모든 경우를 구하고

    1~10까지는 세로형태, 11~20까지는 가로형태, 1과 11은 하나의 거울을 거는 형태만 다르니

    함께 뽑을 수 없습니다.

    20C3까지 뽑은것에서 위의 경우를 따져서 빼주는 것이 각 거울을 가로 세로 따지면서

    뽑는 것 보다 훤신 쉽습니다.

기본 경우의 수는 공식으로 쉽게 뽑히는데 이런식으로 그룹을 만들어 놓으면

쉽게 보이지 않습니다. 이런 것을 잘 구분하는 것을 전편에서 사신의 눈이라고 표현했습니다.

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

휴가인데 평소보다 빨리 깬 아침이네요.

이번 편은 3차원 공간으로 표현된 문제에 대해서 이야기하겠습니다.

1. 3차원 공간의 단위 길이가 1인 6면체를 쌓고 막대를 꽂으면 막대가 지나간

   단위 6면체는 몇개인가?

2. 3차원 테스트리스 처럼 여러가지 다면체를 위에서 떨어뜨리면 최고 높이가 얼마가 될까?

3. 평면의 높이가 각각 다를 수 있는데 높이를 높이거나 낮출때 비용이 들어가는데

   갖고 있는 예산내에서 동일 높이가 되는 최대 정사각형의 넓이는?

4. 다면체 공간 표면상에서 특정 모양의 표면의 넓이나 특정 동작을 했을때 넓이나 위치는?

처음에는 같이 문제를 풀어보고 싶었는데 공간상, 시간상 할 수 없으니 이런 유사한 문제를

 온라인저지 사이트에서 찾아서 풀어보세요. 너무 어려운 것에 매달리지 말고

3차원 공간의 문제는 완전탐색도 중요하지만 공간상 생각하기가 쉽지 않기 때문에

2차원 문제보다 더 어렵게 생각할 수 도 있는데 이럴 때는 전개도로 펴서 보면 쉽게 풀수도 있습니다.

온라인 저지에 보면 많은 경우 대회용 문제라서 완전탐색으로 풀면 타임아웃이 나오니 너무 실망하지 말고

1. 부분점수만 받겠다라고 풀던가

2. 더 높은 수준으로 공부해서 Pass 하던가

3. 대회용이 아닌 문제만 풀던가

 입니다.

정말 고수가 되려면 2처럼 해야 하지만 목적에 맞는 공부를 하세요.

그래서 이 전편에서 이야기 한 것 처럼 보려고 하는 시험의 기출문제를 구해서

 유사?한 비슷한 수준을 공부하는 것이 중요합니다.

이게 딱 시험을 Pass 하는 방법이구요.

물론 압도적인 실력을 가지면 좋지만 그게 노력도 노력인데 너무 시간이 많이 걸려서 힘들지요.

어떤 분들은 매일 꾸준히 1문제라도 풀어야 한다고 하는 분도 있는데

방학때 한 동안은 하루종일 문제를 풀어 어느 수준을 넘는 것이 중요합니다.

뭐든 띄엄띄엄 시간이 쌓인다고 어느 레벨을 넘지는 못하는 것 같습니다.

몇 편인가에 엑셀에 정리하면서 풀라고 한 것 처럼 그 이후에는 가끔 손을 풀어주고

정리한 내용을 주기적으로 보면 실력이 어느 정도 유지 될 수 있을 것 같습니다.

전편에서 이야기한 완전탐색 도구코드(DFS/BFS/순열/조합)는 매일 한번씩 처보고요.

내가 전공이 전산이고 알고리즘과목도 우수한 성적으로 통과했고 텀프로젝트도 하고

동아리에서 안드로이드 프로그램도 짜서 얼마나 업무 역량이 높은데 떨어지겠어라고 생각하면

떨어집니다.

1. 온라인저지 시스템에 익숙하지 않고

2. 포장된 알고리즘 문제인 Problem Solving에 익숙하지 않으면

   손을 못댑니다.

그런 우수한 사람을 놓치면 회사도 아깝고

제 생각은 3시간 2문제 보다 1대1 면접이 훨씬 실력을 확실히 볼수 있고

온라인저지라면 쉬운 문제 부터 어려운 문제까지 더 긴 시간 동안 봐야 실력 검증이 확실할것입니다.

(당사자에게는 괴롭겠지만)

물론 신입사원에게 많은 것을 바라지는 않겠지만

다음편 부터는 어떤TIP들이 있나 생각해 보겠습니다.

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

2차원배열에서 완전 탐색을 한다면 어려가지 문제가 있을 수 있겠지만

1. NxN 배열의 좌상단에서 출발하여 우하단으로 도착할때

   갈 수 없는 길도 있고 아이템도 있어서 도착시에 최대 점수는

2. 배열에 0과 1이 흩어져 있을때 상하좌우로 붙어 있는 그룹은

   몇개로 분류할 수 있는가?

3. Cross Word 처럼 글자나 숫자가 있을때 행과 열을 선택했을때

   연결되는 단어가 단어 사전에 등록되어 있는 글자의 숫자는

4. 1초에 1명씩 옆의 사람에게 감염이 되는데

   특정 위치에서 감염이 시작한다면 모두 감염되는 시간은 몇초인가.

어렵지 않는 난이도이라도 문제는 정말 여러가지 만들 수 있습니다.

1번 문제는 고수들은 DP로 풀겠지만 초보는 순열/조합등으로 조금 높은 수준은

DFS로 풀수 있습니다.

2번은 DFS나 BFS로 풀수 있는데 꼭 BFS로 풀어야 합니다. DFS는 Stack 메모리를

계속 쓰기 때문에 N이 커지면 StackOverflow가 납니다. 그리고 이 문제는

Flood Fill이라는 알고리즘 주제와 연관이 됩니다.

3번은 행과 열에서 몇개씩 고르는 방법

4번 BFS의 여러가지 용도 (숙제, 인터넷 찾아보세요.)

결론적으로 13회에서 말씀드렸던 (중복)순열/(중복)조합에 DFS와 BFS는

자다가 깨서도 사용할 수 있어야 합니다.

(중복)순열/(중복)조합/DFS/BFS 를 하려면 재귀를 알야야 하는데

재귀로 다른 건 못해도 지금 말한 최대 6개의 코드는 꼭 외워야 합니다.

(이해가 아닙니다.)

아~ 그런데 그림과 상세 데이터도 없이 문제의 예를 설명하려니 힘든데

취준생들에게 도움이 되고 있는 것 맞나요?

재수생?들은 아실텐데 제가 바로 가고 있나요?

앞으로도 한동안 계속 연재?를 하겠지만 이것이 결론입니다.

완전탐색으로 표현할 수 있는 순열/조합/DFS/BFS 코드만 가지고도

수 많은 문제를 풀 수 있습니다.

그러니까 데스노트의 사신의 눈을 가지면 이름과 남은 생명이

보이는 것 처럼 문제를 보면 이것이 어떤 방법으로 하면 되겠다

라는 것이 보이는 눈을 갖는 훈련이 필요합니다.

+ 생각으로는 할 수 있는데 손이 안따라가는 경우가 많이 있습니다.

  생각으로 풀 수 있으면 손이 따라갈 수 있게 훈련

+ 각종 TIP이 있는데 알면 빨리 풀고 모르는 고생하는

+ 혹시 유명한 알고리즘의 예제를 보여 준다면 그것을 활용할 수 있는 능력

  (문제를 보고 주어진 문제가 어떤 유명한 알고리즘을 적용하면 되는지

   알아야 풀지요.)

1차원이라고 하면 문자열이나 숫자를 이용한 문제가 많이 있습니다.

(스토리를 입히면 더 실제 문제 같지만 시간이 없어서 그냥 씁니다.)

1. 문자열에 포함된 가장 긴 회문 (앞에서 읽어도 뒤에서 읽어도 같은 글자)의 길이는

2. 여러 문자열 중 최장 공통 문장의 길이는?

3. 문자열을 앞뒤를 붙였을때 최장 연속된 글자열의 길이는?

   (원형 문자열이죠)

4. 문자열 중에 특정 문자열의 갯수는?

2번 같은 문제는 대표적인 문제로 유명한 풀이 방법이 있지만

길이가 길지 않으면 CPU의 힘으로 완전탐색으로 풀수 있습니다.

4번 문제도 찾아보면 KMP등 유명한 알고리즘들이 있습니다.

상용 프로그램의 성능을 좌우하는 알고리즘이지요.

그런데 경우마다 모두 유명한 최고의 성능의 알고리즘을 공부해서는

끝이 없습니다.

다 외울 수 도 없고 인터넷 세상에 외워서 하는 것도 시대에 뒤떨어진것이고요.

나머지도 기본은 완전탐색으로 풀수 있는 연습이 필요합니다.

자료구조중 스텍과 큐도 1차원 배열을 이용한다고 해야 할까요?

1차원 배열을 완전 탐색으로 푸는 방법은

1. 점으로 보고 순열/조합 등으로 경우의 수를 뽑아 내서 풀 수도 있고

2. 간단히 for 문으로 풀리는 경우도 많이 있습니다.

오늘 하고 싶은 말은

1. 어떤 경우에 최적화된 알고리즘이 무엇이 있는지는 알아아 햔다.

    (이름이나 원리만, 외우지 말고)

   나중 면접용이라던가, 실제 업무를 할때 유명한 알고리즘이 있는데

   그걸 본인이 구현하는 우를 범하지 말자. 아무리 해도 최적 알고리즘

   보다는 못한다.

2. 유명 알고리즘을 쓰지 않고 짧은 경우를 만들어 완전탐색으로 풀어본다.

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

완전탐색 중 가장 많이 사용하는 것 관련 이야기입니다.

12편에서 이야기한 점들 간의 관계에 대한 대표적인 것이 아래와 같습니다.

그리고 고등학교때 배웠던 순열/조합 계산할 수 있는냐 물었었죠?

4P4 = 4! = 4x3x2x1 = 24 입니다.

고등학교때는 이 숫자가 중요했지만 이제는 각 Case가 더 중요합니다.

지금 이 24가지를 다 찍는 프로그램 짜실 수 있으세요?

1 2 3 4

1 2 4 3

.....

4 3 2 1

P[24][4] 이런 배열에 넣어보세요.

이런 식으로 P(순열), C(조합), Π(중복순열), H(중복조합) 도 해보세요.

최소 (이해해서) 외우고 언제든치 툭 치면 나올 수 있어야 합니다.

자다가도 물어보면 칠 수 있어야 합니다.

걸그룹은 연습생때 자다가 깨워서 음악 틀면 안무를 해야 한다잖아요.

(취준생은 걸그룹 연수생과 다르지 않는 것 같아요.

 나중에 오디션(시험)에서 시키면 해야잖아요. 그것도 잘.)

코드는 인터넷에 널리고 널렸고 본인이 잘 외울 수 있는 코드를 찾으세요.

(저에게 추천해주세요라고는 하지마세요.)

이해도 해야겠지만 외워야합니다. 위 정도는 코드가 짧아서 잘 외우면

3분정도면 칠 수 있을거에용.

이런 시험이 "알고리즘"대회가 아니라고 해서

이 정도 코드를 이해한 것 기억을 되살려서 30~40분 걸려서 짜고 나면 이게 다가 아니니 이 이후를

할 시간이 없습니다. 기본 코드는 항상 칠 수 있어야 합니다.

생각없이 손이 칠 수 있을때 까지 반복연습이 중요합니다.

문제 해결은 도구를 가지고 있는 것이 중요합니다. (옆에 책과 인터넷이 없으면)

대표적 알고리즘을 위워서 바로 적용할 수 있는 것은

업무역량이나 문제해결 이나 이나라 알고리즘 시험입니다.

모사의 역량 시험이 아니라면 알고리즘 시험으로 몇가지 중요한 알고리즘을

외우기만 하면 되는 것을 물을 수 있지만 문제 해결 시험은 보통 그렇지 않습니다.

어려운 Problem Solving은 새로운 알고리즘을 만들어야 하는 경우 도 있지만

신입사원 입사시험에서 3시간동안 많은 것을 바라지 않아요. (바라지 못합니다.)

문제를 보고 이것을 해체해서 빼대를 찾는 것을 하는 것입니다.

가장 쉬운 형태가 스토리를 보고 이게 순열인지, 조합인지, 중복 순열인지, 종복 조합인지를 빨리 알수 있어야 합니다.

위처럼 문제에 "1부터 10까지를 모든 순열의 경우를 표시하라." 라고 나오지는 않아요.

(이건 예전 학력고사 세대 정도)

결국 같은 난이도? 복잡도겠지만.

여기에 스토리를 붙이면 이렇겠죠.

1. 사과가 10개 있다, (사과의 무게는 따로 있고)

한상자에 1.5kg~ 2.5kg 이면 출하 할 수 있다.

출하할 수 있는 경우는 모두 몇 가지 인가?

최소 이정도는 되어야 문제 같아 보이지요?

2. 위 1번과 유사한데 사과 공장에 사과가 10가지의 무게로 분류되어

   있다.(사과의 갯수는 무한대)

한상자에 1.5kg~ 2.5kg 이면 출하 할 수 있다.

출하할 수 있는 경우는 모두 몇가지 인가?

3. 암나사와 숫나사가 앞뒤로 자웅동체?인 나사가 있습니다.

   (각 나사의 암나사, 숫나사의 규격은 주어집니다.)

  앞뒤로 여러가지 규격의 암나사와 숫나사의 규격이 있을때

  최대 연결 할 수 있는  나사의 갯수는 얼마인가?

만들고자 하면 무수히 할 수 있지만 이번 편은 점들 간의 관계를 봤습니다.

위 공식을 외우고 위 세 문제를 풀어보세요.

이 정도는 풀실수 있으시지요? 취준생이니까.

(학교 중간 고사 시험 정도 밖에 안되지요? 그런데 그 수준을 계속 유지 하기가 어렵지요.)

다음 편은 1차원 배열의 관계를 보겠습니다.

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

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

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 문제를

만들 수 있습니다.

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

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

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

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

10편 끝에 시험을 잘보는 법의 링크가 있고 지난번 글이 번외편이라고 써서

연재?가 끝나는 것으로 생각을 하신분 들이 계신가요?

댓글을 보니 마지막 글 이런 이야기가 있는데 제가 분명히 다음 편은 뭘하겠다고 썼는데.

아직도 할말이 많아서 한참 남았고 마지막 글은 꼭 마지막이라고 쓰겠습니다.

번외편은 Problem Solving 보다는 기술면접? 이런 것에 도움이 될 것 같았고

저는 게임을 하지 않는데 요즘 회사며 길거리에 게임을 하면서 다니는 사람들이

너무 많아서 취준생이면 게임 보다는 좀~ 더 유익한 것을 보고, 듣자라는 뜻있었습니다.

그리고 댓글로 응원도 좋지만 더 알고 싶은 것을 써주시면 법과 사규에 어긋나지 않는 것이라면

생각해 보겠습니다.

(무슨 알고리즘 을 설명해 달라, 이런 건 못해요. 그건 알고리즘 고수들에게 물어보세요.)

제가 7편에서 온라인저지로 할 수 있는 것이 아래 정도가 있다고 말씀을 드렸습니다.

1) 시키는 대로 동작

2) 최대, 최소 구함

3) 최대 성능 구현

이 중 신입사원은 1),2) 정도를 물어보지 않을까 했고

1)번은 학교 과제를 실제로 자기가 해봤으면 풀수 있는 정도로 생각하고

   나중에 다시 한번 이야기하고

2)번에 대해 이야기 해보겠습니다.

많은 문제가 최대나 최소의 값을 물어봅니다.

일상생활을 할때 최대나 최소의 경우를 고르는 경우는 그렇게 많지 않습니다.

어느 정도 기준이 되면 그것로 만족하지요.

집에 가는 길이나 버스를 자동차를 어디서 갈아타는지, 바둑이나 장기를 둘 때도

그래서 문제를 보면 가장 최대에 가까운 것을 먼저 하려고 합니다.

(최선을 선택하지 못했기 때문에 이세돌님이 알파고에게 진 것이고,

 이세돌님이 인간 능력의 한계를 넘어서기는 했지만 알고리즘과 물량공세 진 것이고

 이것이 우리들 보통 사람의 미래라고 생각합니다.)

그렇게 하면 문제가 없는 경우도 많이 있고,

하지만 회사는 최대 이익과 최소 손해를 추구하기 때문에 최대/최소가 중요합니다.

내가 선택한 것보다 더 좋은 방법이 있었는데 못했으면 손해이지요.

(이게 최선이에요? 라고 물어보는 사람이 많아요.)

알고리즘 책을 보면 가장 큰 것 부터 처리 하는 Greedy(욕심장이) 알고리즘이라고 있지요.

많은 문제가 Greedy로 풀리고 최대나 최소가 아니더라도 어느 정도 최대나 최소에

가깝기 때문에 일상생활에 많이 쓰이지요.

하지만 그 결과가 "최대"나 "최소"가 아닌 경우가 많이 있지요.

동전교환 같은 문제가 대표적입니다.

우리의 화폐가 보통 100원 50원 10원 이런 식으로 경우는 문제가 없는데

동전 단위가 1원 4원 6원 이고 거스름돈 8원을 줘야 한다면

욕심장이 알고리즘에서는 6원 1개 1원 2개 총 3개의 동전을 주게 되고

완전탐색으로 하는 경우  4원 2개를 주면 됩니다.

최소값은 2인 것이지요. 그리디 보다 1개를 더 적게 줄 수 있죠.

그래서 이번 편에서 하고 싶은 이야기는 최대/최소를 구할때는 "Greedy를 쓰면 안된다." 입니다.

DFS/BFS/DP 다 Greedy가 아니고 모든 경우를 다 따지는 것입니다.

(온라인저지 입사 시험을 대비한다면 제가 알고리즘 책에서 공부할 것 몇개 빼드렸습니다. 각종정렬과 Greedy 알고리즘)

그래서 모든 최대/최소 문제는 DFS나 BFS로 풀어보는 연습이 필요합니다.

하지만 온라인저지 사이트의 많은 문제는 DFS나 BFS로 풀면 Timeout이 나오는 경우가 많으니

통과하려면 DFS나 BFS로 설계된 것만 해보세요.

또, 통과하지는 않아도 조건이 작은 것은 맞춘다는 생각으로 모든 문제를 완전탐색으로 풀어보세요.

한참 그러고 나면 세상이 완전탐색으로 보여요.

(그렇지만 완전탐색으로 풀수 있는 문제가 제한된다는 것을 알면 알고리즘 세상의 깊이를 느낄 수 있습니다.)

그럼, 다음 편은 어떤 종류의 완전탐색 문제들이 있을까? 생각해 보겠습니다.

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

시간이 있어서 번외편을 올립니다.

꼭 기술면접이 아니라도 업계상식이 많으면 누구와 이야기해도 좋으니

오고가면서 게임을 하시지 말고 아래의 것을 참고해서 관련 업계 상식을 늘려보세요.

또 모르죠, 기술면접에 관련 내용이 나와서 한마디 할 수 있을지도.....

POD cast (팟빵에 다 있지만 feed URL 찾기가 쉽지 않네요.)

 - 나는 프로그래머다!

 - 나는 PM이다!

 - 자가발전 (이중 한 분이 클리앙 회원이라고 하셨는데...)

 - 차정인 기자의 T타임

만화로 쉽게 배우는 시리즈

 - 암호 ( http://book.naver.com/bookdb/book_detail.nhn?bid=7198188 )

 - 프로젝트 매니지먼트 (http://book.naver.com/bookdb/book_detail.nhn?bid=6777141 )

 - 데이터베이스 ( http://book.naver.com/bookdb/book_detail.nhn?bid=5324913 )

   등등

   (만화를 좋아하는 저는 이 밖에도 만화로.... 이런 책을 많이 가지고 있습니다.

    대학교때는 만화로 배우는 공업수학으로 공업수학 공부를 했어요.

    중고등학교때 교과서가 만화책이면 전교 1등을 했을텐데)

네이버 케스트

 - 용어로 보는 IT ( http://navercast.naver.com/list.nhn?cid=122&category_id=122 )

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

오늘은 꼭 온라인 시험이 아니더라도 해당되는 실행 시간 관련 이야기를 해보겠습니다.

러시아 페인트공 알고리즘이라는 것이 있습니다. "조엘 온 소프트웨어" ( http://book.naver.com/bookdb/book_detail.nhn?bid=1528741 ) 라는 책에 나오는 많이 인용되는 이야기입니다. 한번만 해도 되는 일을 반복해서 하는 것에 대한 우화입니다.

(우리 일상도 그렇고 우리가 짠 프로그램도 그렇고)

시험을 볼 때 일단 구현을 해서 원하는 답이 나와도 제한 시간을 초과하면 온라인저지 시스템에서 Timeout이 걸립니다.

물론 신입사원 레벨에서는 좀 넉넉히 주겠지만 암튼 걸리는 경우가 많이 있습니다.

(어제 예를 든 1), 2), 3) 모두 해당되지만 특히 2), 3)에 많이 해당됩니다.)

이럴 때는 아래와 같은 경우가 있습니다.

1) 알고리즘의 복잡도 (O(10^n 처럼)가 높은 경우

2) 가지치기를 안한 경우

3) 반복 계산을 하는 경우

1) 알고리즘의 복잡도 (O(10^n) 같은 높은 경우

   알고리즘 능력과 많이 관계가 있습니다. 복잡도가 낮게 짤 수 있을 수록 알고리즘 실력이 뛰어난 것이죠.

   (O(n^3) 로 풀던 것을 O(n^2)로 풀면 시간이 많이 줄어들겠지요. 몇 개 안되면 효과가 적지만)

   이건 당장 어쩔 수 없습니다. 계속 공부 하다 보면 효과적인 방법을 생각할 수 있게 되겠지요.

2) 가지치기를 안한 경우

   완전탐색(DFS/BFS)등에서 원하는 답을 얻었거나 더 이상 할 필요가 없음에도 계속 하는 경우가 있습니다.

   이럴 때는 가지치기만 확실히 하는 것 만으로도 실행 시간이 많이 줄어듭니다.

3) 반복 계산을 하는 경우

   예를 들어 외판원 문제 (TSP, https://ko.wikipedia.org/wiki/%EC%99%B8%ED%8C%90%EC%9B%90_%EB%AC%B8%EC%A0%9C )같은 문제를 풀 때 순회 순서를 정하고 거리를 구해 보는데 순회 순서를 바꿀 때 마다 거리를 다시

   구하면 시간이 많이 걸립니다. 그런데 모든 장소에서 모든 장소까지를 미리 계산해 table을 만들어 사용하면 순회 순서만 정해지면

   총 거리는 매번 모든 위치를 계산할 필요가 없이 표를 보고 쉽게 계산이 됩니다.

   위에 러시아 페인트공이 바로 이렇게 반복해서 하는 작업이 있지요.

   또, 문자열 뒤에 문자열을 계속 추가하는 것도 대표적인 예입니다.

문제를 풀 때 반복 계산하는 것을 찾게 되면 속도도 빨라지고 완전탐색으로 할 때 

Momoization ( https://ko.wikipedia.org/wiki/%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98 )을 자연스럽게 구사하게 되고 한계를 느끼면 Dynamic Program로 연결이 됩니다. 처음 부터 DP를 공부하면 알고리즘 공부 포기하게 되요.

사실 이것은 어떻게 하던지 답은 맞았으나 시간초과일 때 사용해야 하지만

반대로 생각해 보면 시간초과가 되면 답이 맞았는지도 모르고 이렇게 하는 습관이 있어야

평소에도 실행 시간이 짧은 코드를 만들 수 있습니다.

다 적어 놓고 편집하는 것이 아니라서 번호만 붙었지 순서가 뒤죽박죽입니다.

다음 편에는 최대/최소를 구할 때 많이 사용하는 완전탐색에 대해 생각해 보겠습니다.

아래는 삼성 SW 검정 시험 (S직군이 보는) 관련 글인데

총 4등급 중 상위 2등급에 관한 글이지만 아래 부분은 시험을 보는 방법에

대한 것이 참고가 될 것입니다.

http://hongjun7.tistory.com/129

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