삼성 서티 시험(삼성 소프트웨어 검정) 준비하기

약 9개월 전 알고리즘 문제풀이(PS - Problem Solving) 시작하기라는 글을 포스팅 한적이 있다.

(http://plzrun.tistory.com/entry/알고리즘-문제풀이PS-시작하기)

하지만 나처럼 PS 자체에 대해 관심이 있다기 보다는 잠깐의 취업 준비를 위해 공부하는 사람들이 많다는 것을 알게 되었다.

"삼성에서 소프트웨어 시험을 본다고 해서 준비하려고 하는데, 어디부터 시작하고 어디까지 어디까지 공부해야 하나요?"와 같은 질문글이 많았기 때문이다.

사실 나는 이런 질문들을 그다지 좋아하지 않는데,

그 이유는 영어를 잘하는 방법을 묻는 것이 아니라 오픽 시험점수나 토익 시험점수를 잘 받는 방법을 물어보는 것과 같다고 생각하기 때문이다.

하지만 이제서야 이런 시험이 있고 그것이 꽤 만만치 않다는 것을 알게 된 것이 그 분들만의 잘못은 아니기 때문에

어느 정도 그런 분들의 필요에 맞춰 글을 써보려고 한다.

다만, 해당 알고리즘에 대한 설명은 없고 공부할 방향만을 제시할 것이다.

나의 좁은 안목으로 보기에 현재 삼성 서티의 수준은 완전 탐색이 전부다.

심지어 완전 탐색도 아니고 그냥 큐나 스택 하나 써서 넣고 빼고만 반복해도 풀리는 문제가 나온다.

보통 한 문제만 풀어도 합격이고, 요즘은 문제가 쉬워져서 너도나도 다 2문제는 푼다고 한다.

그럼 완전 탐색(Exhaustive Search)은 뭘까?

모든 경우를 다 해보는 것이다.

그럼 모든 경우를 다 해보기 위해서는 어떤 알고리즘을 써야할까?

이 때 써야 하는 알고리즘이 DFS, BFS이다.

dfs는 깊이 우선 탐색이고

bfs는 너비 우선 탐색이다.

그래서 뭐?

이름은 중요하지 않다.

항상 언급하지만 숲이 먼저다.

이 알고리즘이 정확히 어떤 용도로 쓰이는지, 정확히 어떤 경우에 적용할 수 있는지를 잘 알아야 한다.

DFS, BFS는 그래프의 노드를 탐색하는 방법이다.

다시 말해서 모든 노드를 한번씩 다 가본다는 얘기다.

물론 하나씩 다 방문할 때 중복해서 방문할 수도 있고,

어떤 패턴을 가지고 방문할 수도 있다.

또 탐색 중간에 원하는 결과를 갖게 되면 더 이상 탐색하지 않고 빠져나오도록 하는 경우도 있으며,

bfs만의 특성을 이용해 특수한 경우에는 최단거리를 찾을 수 있고,

dfs만의 특성을 이용해 중복된 노드 방문을 허용하면서 노드 방문의 모든 경우의 수를 알아낼 수도 있다.

하지만 결국 이 알고리즘(dfs, bfs)은 모든 노드를 다 들여다 보기 위한 알고리즘이란 것을 잊어서는 안된다.

여기서 세부적인 알고리즘 구현 방법은 언급하지 않겠다.

어차피 대부분의 사이트들이 숲보다는 나무들의 세세한 면을 다 언급했기 때문에 내가 다시 적는 것은 시간낭비라 생각한다.

또한 이 글을 보는 대부분의 사람들은 dfs와 bfs가 무엇인지 정도는 알고 있을거라 생각하기 때문이다.

dfs와 bfs가 뭔지 궁금하면 방금 내가 언급한 것을 계속 명심하며 위키를 찾아보기 바란다.

그럼 다시 원래 우리의 목적으로 돌아가자.

서티를 잘 보려면 어떻게 해야할까?

서티 문제는 대부분 그냥 구현문제이거나 완전탐색 문제이다.

그러므로 이를 대비하기 위해서는 DFS, BFS를 잘 풀면 된다.

그러면 DFS, BFS의 전형적인 구현방법을 숙지하고,

이와 관련된 문제를 많이 풀어보면 된다.

이 때 dfs, bfs 문제라고 쓰여있는 문제를 몇 문제 풀고나면,

그냥 완전탐색으로 분류된 문제를 풀어보면 좋다.

(둘다 같은 문제이지만 어떤 식으로 분류되어있느냐에 따라 문제를 바라보는 관점이 달라지기 때문에 위와같이 언급했다.)

그 이후부터는 삼성 서티 기출이란 문제들을 풀어본다. (검색하면 여기저기 나온다.)

여기까지 하고 나면 더 욕심이 생길 것이다.

과연 문제는 bfs와 dfs만 나올까?

사실 더 대비를 해야하는 것이 맞다.

나는 그 이후에 binary search, hashing, 최단거리 알고리즘(Dijkstra, Bellman Ford, Floyd Warshall, SPFA), MST(최소신장트리)구하는 알고리즘(Prim, Kruskal), Trie를 추천한다.

이는 순서대로 하는 것을 추천하며, 각 알고리즘마다 주의해야할 것들을 적어보면 다음과 같다.

• 이분 탐색(Binary Search)의 경우 처음 코딩할 때 정답이 어디에 들어있는지 헷갈리는데, 이는 자기만의 방법을 찾는 것이 중요하다.

• Hashing의 경우 문자열을 정수로 변환해서 빠르게 비교할 때 쓰면 좋다는 건 알겠는데, 문자열 자체를 정수로 바꾸는데 드는 시간이 결국 문자열 길이만큼 들여다 봐야 하므로 시간적 이득이 없다고 생각되는 경우 Rabin Karp Fingerprinting이라는 알고리즘을 찾아보길 바란다. (내 블로그에도 간략하게 써있다.)

• 최단거리 알고리즘의 경우 MST(Minimum Spanning Tree)구하는 알고리즘과도 뭐가 다른지를 인지해야 한다.

• MST 구하는 알고리즘에서 Prim은 Dijkstra 코딩 방식과 거의 비슷하다는 것을 알고 뭐가 다른지를 인지하면 된다. Kruskal에서는 Union-Find(Disjoint Set)라는 자료구조를 쓰는데, 이를 잘 익혀서 적용할 줄 알면 된다. 특히 유니온 파인드의 경우 코드가 정말 쉽고 two set 문제를 풀거나 다른 곳에서도 많이 쓰이므로 알아두는 것이 좋다.

• 마지막으로 Trie는 정말 시간이 남으면 보길 추천한다. 트라이는 알고리즘이라기 보다는 자료구조인데, 사실 별거 아니다.

결론은 서티를 준비하기 위해선 DFS, BFS, BS(Binary Search), Hashing, 최단거리 관련 알고리즘, MST 관련 알고리즘, Trie를 추천하며,

사실 1문제만 맞출 생각이라면 dfs, bfs, bs정도만 하면 된다고 생각한다. (요즘은 이것만 해도 2문제 다 푼다 카더라~)

마지막으로 부분합 기법(?)이 자주 쓰이는데....

이 부분은 나중에 써야겠다. (대충 적어보면 입력으로 들어오는 선분이나 사각형 따위의 끝점만 표시해두고 마지막에 반복문 전체 돌아서 다 더하는 방법이다.)

비법은 다 적었는데, 사실 마음이 아프다.

어떤 알고리즘을 딱히 할 필요가 없다니...

절대 그렇지 않다. ㅠㅠ

알고리즘은 전산의 기초 of 기초이다.

알고리즘을 모르는 개발자는 의료지식이 없는 의사와 같다.

병원에 갔는데 내가 물어보는 모든걸 구글에 검색해서 알려주는 의사가 있다면, 당신은 그 의사를 신뢰할 수 있는가?

제발 소프트웨어 입사시험이 끝나고 나서도

알고리즘 공부는 계속 이어나갔으면 한다.

적어도 스스로를 개발자라고 생각한다면,

개발에 알고리즘 공부가 필요없다는 얘기만큼은 안했으면 좋겠다.

보통 그런 사람들 코드를 보면... 매우 암담하다.

 

 

=================================================================================================================================

 

- 2018.10.07

** https://www.acmicpc.net/workbook/view/2134

sw 시험 대비로 여기 문제가 잘 모여있네요..

 

(14500, 14501, 14502, 14503, 14888, 14889, 14890, 14891, 15683, 15684, 15685, 15686, 14499, 12100, 13458, 3190, 13460, 2468, 1600, 2931, 1938, 1937, 2638, 2206, 14442, 11559, 1018, 1726, 3085, 1525, 9376)