SW 역량 테스트 문제 분석

• 2019년 10월 25일 업데이트: 2019년 하반기 문제 분석 추가

BOJ에는 삼성 SW 역량 테스트 기출 문제와 A형 테스트 기출 문제가 수록되어 있다.

• 삼성 SW 역량 테스트 기출 문제
• 삼성 A형 기출 문제

오늘은 이 문제들을 분석해보려고 한다.

먼저, SW 역량 테스트 기출 문제이다. 문제는 각 연도별로 8개씩, 각각 상반기/하반기, 그리고 오전/오후로 나누어져 있다. 시험 시간은 3시간이며 총 2문제를 풀어야 한다.

2019년 10월 25일 현재 기출 문제는 총 29개가 있고, 연도와 상/하반기, 그리고 오전/오후를 분류했다. 또한, 출제진이 의도한 풀이와 실제 문제의 풀이도 함께 적어보았다. 의도한 풀이와 실제 풀이가 같은 경우에는 빈 칸으로 두었다.

연도	오전/오후	문제 번호	제목	의도한 풀이	실제 풀이
?	?	?	뱀	시뮬레이션
2015 하	?	1	시험 감독	수학
2015 하	?	2	구슬 탈출 2	브루트 포스	BFS
2016 하	?	1	주사위 굴리기	시뮬레이션
2016 하	?	2	2048 (Easy)	브루트 포스
2017 상	오전	1	테트로미노	브루트 포스
2017 상	오전	2	퇴사	브루트 포스	다이나믹 프로그래밍
2017 상	오후	1	로봇 청소기	시뮬레이션
2017 상	오후	2	연구소	브루트 포스 + (DFS 또는 BFS)
2017 하	오전	1	스타트와 링크	브루트 포스
2017 하	오전	2	경사로	브루트 포스
2017 하	오후	1	톱니바퀴	브루트 포스
2017 하	오후	2	연산자 끼워넣기	브루트 포스
2018 상	오전	1	감시	브루트 포스
2018 상	오전	2	사다리 조작	브루트 포스
2018 상	오후	1	드래곤 커브	구현 (재귀)
2018 상	오후	2	치킨 배달	브루트 포스
2018 하	오전	1	큐빙	구현
2018 하	오전	2	인구 이동	시뮬레이션 + (DFS 또는 BFS )	풀 수 없는 문제
2018 하	오후	1	나무 재테크	시뮬레이션
2018 하	오후	2	아기 상어	시뮬레이션 + BFS
2019 상	오전	1	미세먼지 안녕!	시뮬레이션
2019 상	오전	2	낚시왕	시뮬레이션
2019 상	오후	1	이차원 배열과 연산	시뮬레이션
2019 상	오후	2	연구소 3	브루트 포스 + BFS
2019 하	오전	1	게리맨더링 2	브루트 포스
2019 하	오전	2	새로운 게임	시뮬레이션
2019 하	오후	1	원판 돌리기	시뮬레이션 + BFS
2019 하	오후	2	주사위 윷놀이	브루트 포스
2020 상	오전	1	모노미노도미노 2	시뮬레이션
2020 상	오전	2	청소년 상어	브루트 포스
2020 상	오후	1	어른 상어	시뮬레이션
2020 상	오후	2	스타트 택시	시뮬레이션 + BFS
2020 하	오전	1	컨베이어 벨트 위의 로봇	시뮬레이션
2020 하	오전	2	마법사 상어와 파이어볼	시뮬레이션
2020 하	오후	1	마법사 상어와 토네이도	시뮬레이션
2020 하	오후	2	마법사 상어와 파이어스톰	시뮬레이션 + BFS

의도한 풀이와 실제 풀이가 다른 경우가 있는데, 이유는 다음과 같다.

• 구슬 탈출 2: 브루트 포스로 해결하면 O(4^10*NM) 이지만, BFS를 이용해 O(NM) 에 해결할 수 있다.
• 퇴사: 브루트 포스로 O(2^N)로 해결할 수 있지만, 다이나믹 프로그래밍을 사용하면 O(N)이다.
• 인구 이동: 문제의 조건으로는 시간 제한 안에 푸는 방법이 존재하지 않는다. 따라서, BOJ에서는 인구 이동의 발생 횟수에 대한 조건(2000번 이하)이 추가되었다.

연도별로 난이도를 분석해보았다. 뱀은 연도를 알 수 없기 때문에 제외했다.

연도	브루트 포스	BFS	시뮬레이션 및 구현	기타
2015 하	1	0	0	1
2016 하	1	0	1	0
2017 상	3	0	1	0
2017 하	4	0	0	0
2018 상	3	0	1	0
2018 하	0	1	4	0
2019 상	1	1	3	0
2019 하	2	1	2	0
2020 상	1	1	3	0
2020 하	1	1	4	0

2017년 상반기부터 2018년 상반기는 브루트 포스의 문제가 거의 다였고, 2018년 하반기부터 시뮬레이션의 비중이 매우 크게 높아졌다.

해가 갈수록 문제의 출제 경향이 브루트 포스 및 BFS에서 시뮬레이션으로 변하고 있다. 시뮬레이션도 단순 문제의 내용을 구현하는 문제에서 DFS나 BFS를 이용해서 구현하는 방식으로 진화하고 있다.

• 2019년 10월 25일 내용 추가: 위의 예상과 같게 단독 시뮬레이션 문제가 줄고 다른 알고리즘과 함께 시뮬레이션을 하는 문제가 2019 하반기에 출제되었다.

A형 테스트의 문제를 분석해봤다.

제목	의도한 풀이	실제 풀이
괄호 추가하기	브루트 포스
파이프 옮기기 1	브루트 포스
캐슬 디펜스	브루트 포스 + 시뮬레이션
색종이 붙이기	브루트 포스
⚾	브루트 포스 + 시뮬레이션
Brainf**k 인터프리터	시뮬레이션
배열 돌리기 4	브루트 포스 + 시뮬레이션
게리맨더링	브루트 포스 + (DFS 또는 BFS)
다리 만들기 2	브루트 포스 + BFS

파이프 옮기기 1은 다이나믹 프로그래밍으로도 풀 수 있다. 하지만, 문제에 방법의 수가 1,000,000보다 작거나 같다라는 조건이 있기 때문에 의도한 풀이는 브루트 포스라는 것을 볼 수 있다.

다리 만들기 2는 MST로도 풀 수 있다. 하지만, 문제의 섬의 개수 제한이 6개보다 작다는 조건 때문에 의도한 풀이가 브루트 포스임을 알 수 있다. 만약, 섬의 개수 제한이 매우 컸다면 이 문제는 MST문제이다.

A형 테스트의 문제는 브루트 포스를 기반으로 하고, 시뮬레이션이나 DFS 또는 BFS가 추가되는 형태임을 볼 수 있다.

결론

2019년을 기준으로 역량 테스트와 A형 테스트에 출제되는 알고리즘은 브루트 포스, DFS, BFS 3가지 밖에 없다. 시뮬레이션의 경우에는 과거에는 문제의 내용을 단순히 구현만 하면 되던 문제였지만, 현재는 문제의 내용을 구현하기 위해서 DFS나 BFS를 써야 하는 문제 또는 브루트 포스와 섞여있는 문제가 출제되고 있다.

시뮬레이션 및 구현 문제의 구현 난이도는 2016년부터 2017년까지 점점 상승하다가, 2018년 큐빙 문제로 정점을 찍고, 현재는 2017년과 2018년의 중간 수준으로 출제되고 있다. 중간이라기엔 큐빙 문제의 구현 난이도가 너무 복잡하기 때문에, 2017년의 난이도보다 25%정도 어려운 수준이라고 볼 수 있다.

역량 테스트의 목적은 알고리즘 대회 출신, 알고리즘 문제 풀이 전문가를 뽑는 것이 아니기 때문에, 앞으로도 이정도의 출제 경향(시뮬레이션, 브루트 포스, DFS와 BFS)을 유지할 것 같다.

2018년을 기준으로 시뮬레이션의 비중이 매우 높아졌기 때문에, 구현이 복잡한 문제를 위주로 풀면서 브루트 포스, BFS 문제를 틈틈이 연습하는 편이 좋을 것 같다. 추천하는 공부 비중은 50:25:25 이고, 50은 시뮬레이션이다.

다른 기업

다른 기업의 코딩 테스트에는 위에서 언급한 시뮬레이션, 브루트 포스, DFS와 BFS를 제외한 알고리즘이 나오기도 한다. 주로 4개 이상의 문제를 시험 보는 경우에 가장 어려운 문제로 그래프 알고리즘을 출제하기도 한다.

주로 출제되는 그리고 현재까지 출제된 그래프 알고리즘은 다음과 같다.

• 난이도가 있는 BFS
  • 숨바꼭질 5
• 위상 정렬
  • 작업
• 최소 스패닝 트리 (프림, 크루스칼)
• 최단 거리 (다익스트라)

광고

• 시뮬레이션, 브루트 포스, BFS, 다이나믹 프로그래밍을 공부하기 좋은 강의
• 코딩 테스트 및 코딩 인터뷰 모두를 준비하기 좋은 강의