추가 적립 안내

삼성소프트웨어 검정시험을 출제,검토,강의했던 핵심비법

본서는 삼성 소프트웨어 역량테스트에서 출제될 수 있는 핵심 알고리즘과 문제들로 구성되어 있다. 이 책을 읽는 이들이 컴퓨터 프로그래밍 언어인 C++ 혹은 JAVA의 문법을 이해하고 있다는 전제하에 언어의 기본적인 문법에 대한 설명은 생략하였다. 처음 컴퓨터 프로그래밍을 접하는 수험생은 C++, JAVA 학습서와 병행하며 학습하기를 권한다.

실제 시험은 C, C++, JAVA 세 개의 언어 중 하나를 선택하여 시험에 응시할 수 있으나 몇몇 자료구조와 API의 사용을 위해 C언어에 대한 설명은 생략하였다. 만약 C언어로 학습하길 희망하는 수험생은 본서에서 사용하는 자료구조들을 직접 구현하는 방법도 같이 학습하여야 한다. 교재 안에서 소개되는 C++의 자료구조나 API의 종류가 많지 않으므로 C언어에만 익숙한 수험생도 C++을 공부하여 C++로 시험에 응시하길 바란다.

이 책은 C++의 입출력함수로 cin/cout 대신 scanf/printf를 사용한다. 입력이나 출력해야 하는 데이터가 많아질수록 입/출력 속도에서 차이를 보이기 때문이다. JAVA에서도 입력 속도 개선을 위해 Bufferedreader/BufferedWriter를 사용할 수 있으나 입력 값을 직접 파싱해야 한다는 번거로움과 각 줄의 입/출력 데이터가 많을 때만 제한적으로 성능의 차이를 보이기 때문에 따로 언급하지는 않는다.

이 책은 한마디로 삼성 입사를 위한 필독서이다. 또한, C++의 입출력함수로 cin/cout 대신 scanf/printf를 사용한다. 입력이나 출력해야 하는 데이터가 많아질수록 입/출력 속도에서 차이를 보이기 때문이다. JAVA에서도 입력 속도 개선을 위해 Bufferedreader/BufferedWriter를 사용할 수 있으나 입력 값을 직접 파싱해야 한다는 번거로움과 각 줄의 입/출력 데이터가 많을 때만 제한적으로 성능의 차이를 보이기 때문에 따로 언급하지는 않는다. 삼성 소프트웨어 역량테스트(SAQ)는 알고리즘 이론뿐만 아니라 실제 프로그램 개발능력을 평가하는 실기시험이다. 2018년 상반기 기준, 시험에서 제공하는 C, C++, JAVA 세 가지 중 하나의 언어로 실제 프로그램을 코딩하여 그 결과를 채점하는 시험이다. 시험장에 입장하면 간단하게 시험 시 주의해야 할 사항에 대해 설명을 듣게 되고, 그 후 감독관이 알려준 웹페이지에서 시험 시작 시간 정각에 모든 수험생들에게 동시에 문제가 공개된다. 시험시간은 웹페이지에 있는 시간 기준이며, 시험이 시작되면 수험생은 해당 문제를 읽고 문제 하단에 답안을 작성하여 제출하여야 한다. 시험장에는 2장의 연습장이 제공되며, 추가 연습장은 지급이 되지 않는다. 다만, 새로운 연습장이 필요한 경우 기존에 받은 연습장과 교환할 수 있다. 바로 코딩을 시작하기보다는 연습장을 활용하여 코딩할 내용들을 미리 정리하고 검토하는 습관을 들이는 것이 좋다.
또한, 시험장에는 사용자가 코딩하기 쉽도록 만든 편집기, IDE(Integrated Development Environment, 통합 개발 환경)가 준비되어있다. 언어별로는 C, C++을 위한 IDE로 Visual Studio를, JAVA를 위한 IDE로 Eclipse를 제공하고 있다. 주의할 부분은 수험생의 컴퓨터에 있는 IDE에 작성된 코드로 채점하는 것이 아니라 문제가 주어진 웹페이지 하단의 코드 작성란에 있는 코드로 평가를 한다는 점이다. 또한 시험장에서 사용할 수 있는 프로그램은 메모장, 계산기, IDE뿐이며 엑셀(excel)같은 프로그램을 사용하면 부정행위로 간주되니 이 점에 유의해야 한다.

01 삼성 소프트웨어 역량테스트에 대한 이해 7

02 알고리즘 문제 해결 과정 11

03 IDE 설치 및 사용방법 19
3.1. Visual Studio 20
3.2. Eclipse 26

04 시간/공간복잡도와 자료구조 37
4.1. 시간복잡도와 공간복잡도 38
4.2. 자료구조 44
-배열(Array) 43
-리스트(List) 47
-스택(Stack) 50
-큐(Queue) 53

05 유형별 알고리즘 59
5.1. 논리 구현(Implementation) 65
-문제 5-1-1. 이해도 점수 70
-문제 5-1-2. 갤러그 74
-문제 5-1-3. 로봇 쥐 78
5.2. 그래프 이론(Graph Theory) 87
-문제 5-2-1. 인접배열과 인접리스트 90
5-2-1. 깊이 우선 탐색(Depth First Search, DFS) 96
-문제 5-2-2. 순열 출력하기 98
-문제 5-2-3. 방 탈출 게임1 106
-문제 5-2-4. 외판원 순회 111
-문제 5-2-5. 화산 폭발1 118
5-2-2. 너비 우선 탐색(Breadth First Search, BFS) 126
-문제 5-2-6. 미로 찾기1 130
-문제 5-2-7. 방 탈출 게임2 137
-문제 5-2-8. 화산 폭발2 144
5.3. 정렬 및 탐욕법(Sorting & Greedy Algorithm) 154
-문제 5-3-1. 딱지 수집 164
-문제 5-3-2. 드래곤 사냥 169
5.4. 동적 계획법(Dynamic Programming, DP) 178
-문제 5-4-1. 징검다리 건너기 184
-문제 5-4-2. 미로 찾기2 189

06 실전문제 195
-문제 6-1. 와인 파티 197
-문제 6-2. 숫자 변환 203
-문제 6-3. 워크숍 210
-문제 6-4. 교실 청소 217
-문제 6-5. 전염병 222
-문제 6-6. SW단어카드 229
-문제 6-7. 정육면체 굴리기 237
-문제 6-8. 뱀 게임 247
-문제 6-9. 숫자 지우기 258
-문제 6-10. 디스트로이어 263
-문제 6-11. 연산자 274
-문제 6-12. 선물상자 281
-문제 6-13. 방 탈출 게임3 288
-문제 6-14. 도둑의 경로 296

1. 삼성 소프트웨어 역량테스트에 대한 이해
삼성 소프트웨어 역량테스트(SAQ)는 알고리즘 이론 뿐만 아니라 실제 프로그램 개발능력을 평가하는 실기시험이다. 따라서 2018년 상반기 기준, 시험에서 제공하는 C, C++, JAVA 세가지 중 하나의 언어로 실제 프로그램을 코딩하여 그 결과를 채점하는 시험이다.
시험장에 입장하면 간단하게 시험시 주의해야 할 사항에 대해 설명을 듣게 되고, 그 후 감독관이 알려준 웹페이지에서 시험 시작시간 정각에 모든 수험생들에게 동시에 문제가 오픈된다. 시험시간은 웹페이지에 있는 시간 기준이며, 시험이 시작되면 수험생은 해당 문제를 읽고 문제 하단에 답안을 작성하여 제출하여야 한다.
시험장에는 2장의 연습장이 제공되며, 추가 연습장은 지급이 되지 않는다. 다만, 새로운 연습장이 필요한 경우 기존에 받은 연습장과 교환할 수 있다. 서두에 말한 것처럼 연습장을 활용하여 코딩할 내용들을 미리 정리하고 검토하는 습관을 들이는 것이 좋다.
또한 시험장에는 사용자가 코딩을 하기 쉽도록 만든 편집기, IDE(Integrated Development Environment, 통합 개발 환경)를 사용할 수 있게 준비 되어있다. 언어별로는 C, C++을 위한 IDE로 Visual Studio를, JAVA를 위한 IDE로 Eclipse를 제공하고 있다. 주의할 점은 수험생의 컴퓨터에 있는 IDE에 있는 코드로 채점하는 것이 아니라 문제가 주어진 웹페이지 하단의 코드 작성란에 코드를 제출하여야 제대로 된 평가를 받을 수 있다. 또한 시험장에서 사용할 수 있는 프로그램은 메모장, 계산기, IDE뿐이며 엑셀(excel)같은 프로그램을 사용하면 부정행위로 간주되니 이 점에 유의하자.
시험은 총 3시간동안 2문제를 풀게 된다. 난이도는 일반적으로 1번문제가 좀 더 쉽다고 알려져 있으나, 문제 유형이나 개인별 체감도에 따라 난이도는 다르게 느낄 수 있다. 일반적으로 문제 하단에 sample case가 주어지는데 sample case를 가지고 내가 작성한 코드가 올바른 결과를 출력하는지를 확인해 볼 수 있다. 하지만 sample case에 대해 모두 정답을 출력했다고 해서 그 문제를 완벽히 풀었다고 말할 수 없는데, 실제 채점은 sample case가 아닌 숨겨진 채점용 evaluate case를 가지고 채점을 하기 때문이다. 채점용 evaluate case에는 sample case에는 없지만 수험생들이 실수로 놓치기 쉬운 예외 케이스(corner case)들도 많이 존재한다. 따라서 sample case를 통과해야하는 것은 물론, 시간이 된다면 sample case외에 존재할 수 있는 예외 케이스를 직접 만들어 올바른 정답을 제한시간 내에 출력하는지를 살펴보는 것이 중요하다.
답안 작성란은 C/C++/JAVA 언어별로 작성할 수 있는 공간이 주어지고, 간단한 기본 템플릿이 주어진다. 이 템플릿을 IDE에 복사해서 코딩을 시작하는 것이 편리하다. 다만, 앞에서 말한 것처럼 컴퓨터에 설치된 IDE에서 코딩을 하는 것은 상관없으나, 최종 제출은 반드시 웹 페이지에서 해야 채점이 된다는 점을 반드시 명심하자.
만약 알고리즘 실기시험이 처음이라면 온라인 저지 사이트에서 제공하는 연습문제나 온라인 알고리즘 대회에 참가하여 문제가 어떤 방식으로 출제되는지 먼저 경험해보길 추천한다.
해외 저지 사이트로는 Topcoder(https://www.topcoder.com), Codeforces (http://www.codeforces.com)등이 있으며 국내 저지 사이트로는 삼성의 SW Expert Academy(https://www.swexpertacademy.com), 코드그라운드(https://www.codeground.org), 정올(http://www.jungol.co.kr), BOJ(http://www.acmicpc.net)등이 있다.
온라인 알고리즘 대회로는 구글의 코드잼(https://code.google.com/codejam)과 앞서 언급한 Topcoder, Codeforces등 여러 사이트에서 정기적으로 대회를 개최하고 있다. 대회의 난이도는 천차만별이지만 연습문제와 다르게 주어진 시간 내에 누가 많은 문제를 푸는가를 경쟁하는 것이기 때문에, 실제 시험과 같은 긴장감을 느끼며 문제를 풀어볼 수 있다. 일반적으로 대회가 끝나면 출제자가 모범코드와 그에 다한 해설을 제공하고, 토론장에서 세계 각국의 참가자들이 해당 문제에 대한 열띤 토론을 펼친다. 토론과정에서 내가 생각하지 못한 다양한 아이디어를 얻을 수 있고, 이를 통해 알고리즘 문제풀이 실력이 크게 상승하는 계기가 될 수 있다.
Summary
삼성 소프트웨어 역량테스트 시험시 제공되는 Sample Case를 가지고 정답을 출력하는 것을 1차 목표로 하되, 실제 채점은 채점용 Evaluation Case로 이뤄지므로 여러 예외 케이스에 대해서도 정답을 출력하는지 확인해야 한다.
시험 전 국내/해외 온라인 저지 사이트에서 문제를 풀어보길 권장한다. 다만, 삼성 소프트웨어 역량테스트의 난이도를 벗어나는 문제들이 많기 때문에 먼저 삼성에서 제공하는 SW Expert Academy (https://www.swexpertacademy.com)에서 연습하기를 추천한다.

Summary
문제를 꼼꼼히 읽는 것도 중요한 부분이다. 수험생들 중 문제를 급하게 읽는 바람에 문제를 잘 못 이해하여 엉뚱한 방향으로 접근하여 시험을 망치는 사례가 많으니 주의하자.
알고리즘 문제를 해결할 때, 연습장에 자신만의 계획을 그려보는 훈련을 꼭 해야 한다. 시험시간의 많은 부분을 알고리즘을 설계하는데 투자하더라도 올바른 방향으로의 알고리즘을 설계할 수 있다면 훨신 효율적으로 문제를 풀 수 있다.
제한조건을 놓치지 말아야 한다. 막막해 보이는 문제여도 제한조건에 힌트가 있는 경우도 있고, 반대로 쉬워 보이지만 제한조건에 함정이 있는 경우도 더러 존재한다. 특히 제한조건을 무시하더라도 sample case에서는 정답이 출력되지만 실제 채점용 케이스인 evaluation case에서는 오답을 출력하는 경우가 있으므로 각별히 신경써야 한다.
본인이 생각한 내용을 컴퓨터 언어로 구현한다는 것은 쉽지 않은 일이다. 특히 처음 코딩을 접하는 수험생들에게는 오로지 연습만이 구현능력을 키우는 방법이다. 매번 반복되는 오류에 지칠 수도 있지만, 오류를 디버깅하는 연습조차 실제 시험에서 큰 도움이 될 것이다.

3. IDE(Visual Studio / Eclipse) 설치 및 사용방법
먼저 시험장에서 사용하게 될 IDE인 Visual Studio와 Eclipse를 미리 설치하고, 사용법에 익숙해 져야 한다. 모두 설치할 필요는 없으며 자신이 선택할 언어가 C/C++인 경우는 Visual Studio를, JAVA인 경우 Eclipse를 설치하면 된다.

1. Visual Studio
Visual Studio 다운로드 페이지(https://www.visualstudio.com/ko/downloads)에 접속하면 아래 그림 1과 같은 화면을 볼 수 있다.
다운로드 페이지에서 그림1에서 보이는 빨간 박스의 Visual Studio Community 2017 “무료 다운로드” 버튼을 클릭하면 자동으로 Visual Studio Installer를 다운로드 받게된다.
해당 파일을 실행시켜 Visual Studio를 설치할 때 다음 그림 2와 같이 “C++을 사용한 데스크톱 개발” 항목을 체크하여 설치를 진행하도록 한다.
2. 알고리즘 문제 해결 과정
알고리즘이란 일반적으로 특정 문제를 해결하기 위한 여러 동작들의 단계나 방법의 모임이다. 우리가 이 교재를 통해 다루고자 하는 컴퓨터 과학에서의 알고리즘이란 수학적인 문제를 해결하기 위한 단계들을 완성하는 과정이라고 할 수 있다. 어떠한 문제를 해결하는 데에 있어 여러 방법이 존재하듯이 컴퓨터 과학에서 알고리즘은 원하는 결과를 도출해 내는 것은 물론, 최적(最適)의 방법을 찾는 데에 그 목적이 있다. 여기서 말하는 최적의 방법이란 다음에 배울 시간복잡도와 공간복잡도의 개념으로 처리시간과 메모리사용 측면에서 효율적임을 뜻한다. 삼성 소프트웨어 역량테스트에서는 문제를 푸는데 필요한 시험시간 뿐만 아니라 알고리즘이 수행하는데 걸리는 시간과 사용하는 메모리의 제한범위가 주어진다.
따라서 아래와 같이 4단계로 구분하여 문제를 푸는 것을 추천한다.
1. 문제를 읽고 완벽하게 이해한다.
문제를 읽고 완벽하게 이해한다는 말은 단순히 주어진 문제를 이해하는 것 뿐만 아니라 제시된 제한조건을 이해하는 것 역시 포함된다.
문제의 내용이 아래와 같은 경우를 살펴보자.

문제에서 생산된 제품의 개수를 출력하라고 했기 때문에 결과값은 0이상의 정수를 출력해야 함을 알 수 있다. 알다시피 C++이나 Java에는 정수를 표현할 수 있는 자료형이 크게 두 가지가 존재한다.
하나는 32비트 자료형인 int로 int가 나타낼 수 있는 숫자의 범위는 -부터 까지(-2,147,483,648 ~ 2,147,483,647)이고, 다른 하나는 64비트 자료형인 long으로(C++에서는 long long) 나타낼 수 있는 숫자의 범위는 -부터 까지(-9,223,374,036,854,775,808 ~ 9,223,372,036,854,775,807)이다.
문제에서 출력값이 이 넘는 경우 출력하는 자료형을 32비트 자료형인 int로 했다면 우리가 원하는 정상적인 결과를 얻지 못하게 된다.
아래 코드를 출력해 보면 확인해 볼 수 있다.
C++

JAVA

이처럼 문제에서 제한사항으로 주어진 내용을 꼼꼼히 읽어야 위와 같은 실수를 방지할 수 있다.

2. 문제를 어떻게 해결할지 계획을 세운다.
많은 학생들이 시험시간에 쫓긴 나머지 문제를 읽고 바로 코딩을 시작하는 경우가 많다. 주어진 문제의 제한조건을 벗어나지 않는 적절한 해결방법이라면 문제가 없으나, 그렇지 않고 코딩을 시작하고 한참뒤에 오류를 발견한다면 시험을 망치게 된다.
문제의 내용이 아래와 같은 경우를 살펴보자.

유명한 알고리즘 문제중 하나인 거스름돈 문제로, 이 문제를 처음 다뤄보는 학생들은 "최소한의 동전개수"를 구하기위해 가장 액면가가 큰 동전부터 주는 것이 문제풀이 방법이라고 생각하기 쉽다.
다시 말해, 거스름돈이 2000원인경우 1000원짜리 2개로, 거스름돈이 2900원인경우 1000원짜리 2개, 700원짜리 1개, 100원짜리 2개로 주는 방법이다.
위 방법대로 문제를 해결하면 1400원이나 2400원 같은 경우
1400 = 1000 * 1 + 100 * 4 : 총 5개
2400 = 1000 * 2 + 100 * 4 : 총 6개 가 된다.
하지만,
1400 = 700 * 2 : 총 2개
2400 = 1000 * 1 + 700 * 2 : 총 3개로, 위의 방법이 잘못됨을 알 수 있다.
이 경우처럼 예외 케이스(corner case)에 대한 충분한 검토 없이 문제풀이를 시작하여 시험 시간의 대부분을 낭비했다면 시험을 통과하기는 힘들 것이다. 삼성 소프트웨어 역량테스트 시험장에서도 연습장을 사용할 수 있기 때문에, 평소 연습장에 코딩할 내용을 미리 적어보고 검토하는 연습을 해보길 권장한다.

3. 작성하려는 알고리즘이 주어진 제한조건에 부합하는지 검토한다.
앞서 말한 것처럼 삼성 소프트웨어 역량테스트(SAQ)는 알고리즘이 수행하는데 걸리는 시간과 사용하는 메모리의 제한범위가 주어진다. 이는 문제에서 원하는 정답을 구하는 것은 물론, 일정 수준 이상의 최적화된 알고리즘을 구현할 수 있는지를 묻는 것이다. 따라서 우리가 생각한 풀이방법이 문제의 정답을 출력하는 알고리즘 일지라도 문제에서 주어진 제한조건에 부합하지 않는다는 것을 미리 판단하여 불필요한 시간낭비를 줄여야 한다. 보통 컴퓨터는 1초에 1억번의 기본 연산을 한다고 가정하고 문제를 접근하는 것이 일반적이다. 또한, 자료형 마다 일정한 메모리공간을 차지한다. 만약 문제에서 주어진 제한조건이 “수행시간:2초 / 메모리 제한:256MB”라면 내가 생각한 알고리즘의 연산 횟수가 최대 입력값에 대해 최대 연산횟수가 2억번을 넘지 않는지, 내가 사용하는 변수들이 사용 할 메모리 공간이 256MB를 넘지 않는지를 미리 계산하여 시험시간을 효율적으로 사용해야 한다.

4. 계획한 내용을 컴퓨터 언어로 구현한다.
앞서 말한 세 단계를 통해 문제에 적합한 최적의 풀이법을 생각해냈다 하더라도 이를 컴퓨터 언어로 구현하는 것 역시 쉽지않은 문제이다. 실제로 컴퓨터 언어를 다뤄보지 않은 많은 학생들이 제일 어려워하고 고민하는 부분이기도 하다.
아래 예제를 살펴보자.

좌표평면에 두 개의 선분을 그리고 두 선분이 만나는지를 육안으로 판단하는 것은 굉장히 간단한 일이지만 실제로 위 문제의 답안을 컴퓨터 언어로 작성해보면 쉽지 않음을 금방 알 수 있다.
우리가 생각한 내용을 컴퓨터 언어로 구현하는 것은 컴퓨터 언어에 능숙한 사람들에게도 쉽지 않은 문제이다. 수많은 반복과 연습, 그리고 오류가 발생하였을 시 이를 해결하는 디버깅 훈련을 통해 구현능력을 키워야 한다.