- 2019년 10월 25일 업데이트: 2019년 하반기 문제 분석 추가
- 2020년 6월 18일 업데이트: 2020년 상반기 문제 분석 추가
- 2020년 10월 20일 업데이트: 2020년 하반기 문제 분석 추가
- 2021년 12월 9일 업데이트: 2021년 상반기/하반기 문제 분석 추가
BOJ에는 삼성 SW 역량 테스트 기출 문제와 A형 테스트 기출 문제가 수록되어 있다.
오늘은 이 문제들을 분석해보려고 한다.
먼저, SW 역량 테스트 기출 문제이다. 문제는 각 연도별로 8개씩, 각각 상반기/하반기, 그리고 오전/오후로 나누어져 있다. 시험 시간은 3시간이며 총 2문제를 풀어야 한다.
2021년 12월 9일 현재 기출 문제는 총 45개가 있고, 연도와 상/하반기, 그리고 오전/오후를 분류했다. 또한, 출제진이 의도한 풀이와 실제 문제의 풀이도 함께 적어보았다. 의도한 풀이와 실제 풀이가 같은 경우에는 빈 칸으로 두었다.
연도 | 오전/오후 | 문제 번호 | 제목 | 의도한 풀이 | 실제 풀이 |
? | ? | ? | 뱀 | 시뮬레이션 | |
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 | |
2021 상 | 오전 | 1 | 상어 초등학교 | 시뮬레이션 | |
2021 상 | 오전 | 2 | 상어 중학교 | 시뮬레이션 + (DFS 또는 BFS ) | |
2021 상 | 오후 | 1 | 마법사 상어와 비바라기 | 시뮬레이션 | |
2021 상 | 오후 | 2 | 마법사 상어와 블리자드 | 시뮬레이션 | |
2021 하 | 오전 | 1 | 주사위 굴리기 2 | 시뮬레이션 + (DFS 또는 BFS ) | |
2021 하 | 오전 | 2 | 온풍기 안녕! | 시뮬레이션 | |
2021 하 | 오후 | 1 | 마법사 상어와 복제 | 시뮬레이션 | |
2021 하 | 오후 | 2 | 어항 정리 | 시뮬레이션 |
의도한 풀이와 실제 풀이가 다른 경우가 있는데, 이유는 다음과 같다.
- 구슬 탈출 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 |
2021 상 | 0 | 1 | 4 | |
2021 하 | 0 | 1 | 4 |
2017년 상반기부터 2018년 상반기는 브루트 포스의 문제가 거의 다였고, 2018년 하반기부터 시뮬레이션의 비중이 매우 크게 높아졌다.
해가 갈수록 문제의 출제 경향이 브루트 포스 및 BFS에서 시뮬레이션으로 변하고 있다. 시뮬레이션도 단순 문제의 내용을 구현하는 문제에서 DFS나 BFS를 이용해서 구현하는 방식으로 진화하고 있다.
- 2019년 10월 25일 내용 추가: 위의 예상과 같게 단독 시뮬레이션 문제가 줄고 다른 알고리즘과 함께 시뮬레이션을 하는 문제가 2019 하반기에 출제되었다.
- 2021년 12월 9일 내용 추가: 단독 시뮬레이션 문제가 다시 많아지고 있으며, 2차원 배열에서 시뮬레이션 하는 중에 연결 요소를 찾기 위해 DFS 또는 BFS를 사용해야 하는 경우가 많아지고 있다.
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개 이상의 문제를 시험 보는 경우에 가장 어려운 문제로 그래프 알고리즘을 출제하기도 한다.
주로 출제되는 그리고 현재까지 출제된 그래프 알고리즘은 다음과 같다.
훌륭한 분석입니다. fan입니다.
정말 좋은 글 잘 읽고 갑니다. 신유형이 나왔다고 하길래 공부 범위를 넓혀야 하나 고민이 많았는데, 덕분에 기존 범위 그대로 열심히 준비하기로 결심했습니다. 다른 분들도 이 소식을 알고 도움이 되었으면 좋겠네요. 혹시 이 글을 제 블로그에 공유해도 될까요?
개인적인 풀이법과 난이도 분석도 혹시 도움될까 하여 공유합니다!
모의문제도 분석해 보았으며, 기출의 경우 최신 경향과 맞는 2018년도 기출부터 하였습니다.
[SWEA 모의문제]
– 원자 소멸 시뮬레이션 (최상)
– 보호 필름 (최상)
– 핀볼 게임 (시뮬레이션 + 완전탐색, 상)
– 벽돌 깨기 (BFS + 완전탐색, 중)
– 점심 식사시간 (시뮬레이션 + 완전탐색, 중)
– 등산로 조성 (BFS + 완전탐색, 중)
– 줄기세포배양 (시뮬레이션, 하)
– 무선 충전 (시뮬레이션, 하)
– 활주로 건설 (완전탐색, 하)
– 보물상자 비밀번호 (시뮬레이션, 최하)
– 특이한 자석 (시뮬레이션, 최하)
– 미생물 격리 (시뮬레이션, 최하)
– 홈 방범 서비스 (완전탐색, 최하)
– 디저트 카페 (완전탐색, 최하)
– 탈주범 검거 (BFS, 최하)
[2018년 상반기 오전 기출]
– 감시 (시뮬레이션 + 완전탐색, 중)
– 사다리 조작 (완전탐색, 최하)
[2018년 상반기 오후 기출]
– 드래곤 커브 (시물레이션, 최하)
– 치킨 배달 (완전탐색, 최하)
[2018년 하반기 오전 기출]
– 큐빙 (시뮬레이션, 최상)
– 인구 이동 (BFS, 중)
[2018년 하반기 오후 기출]
– 나무 재테크 (시뮬레이션, 최하)
– 아기상어 (시뮬레이션 + BFS, 중)
[2019년 상반기 오전 기출]
– 미세먼지 안녕! (시뮬레이션, 하)
– 낚시왕 (시뮬레이션, 최하)
[2019년 상반기 오후 기출]
– 이차원 배열과 연산 (시뮬레이션, 최하)
– 연구소3 (BFS + 완전탐색, 중)
[2019년 하반기 오전 기출]
– 게리맨더링2 (시뮬레이션 + 완전탐색, 하)
– 새로운 게임 (시뮬레이션, 최하)
[2019년 하반기 오후 기출]
– 원판 돌리기 (시뮬레이션 + BFS, 중)
– 주사위 윷놀이 (시뮬레이션 + DFS, 중)
[2020년 상반기 오전 기출]
– 모노미노도미노2 (시뮬레이션, 상)
– 청소년 상어 (시뮬레이션 + DFS, 하)
[2020년 상반기 오후 기출]
– 어른 상어 (시뮬레이션, 하)
– 스타트 택시 (시뮬레이션 + BFS, 하)
[2020년 하반기 오전 기출]
– 컨베이어 벨트 위의 로봇 (시뮬레이션, 최하)
– 마법사 상어와 파이어볼 (시뮬레이션, 최하)
[2020년 하반기 오후 기출]
– 마법사 상어와 토네이도 (시뮬레이션, 최하)
– 마법사 상어와 파이어스톰 (시뮬레이션 + BFS, 중)