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

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로 설계된 것만 해보세요.

 

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

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

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

 

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

 

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