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

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

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