SW 역량 테스트 문제 분석

2019년 9월 23일 3 Comments
  • 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 하?22048 (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 하1001
2016 하1010
2017 상3010
2017 하4000
2018 상3010
2018 하0140
2019 상1130
2019 하2120
2020 상1130
2020 하1140
2021 상014
2021 하014

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개 이상의 문제를 시험 보는 경우에 가장 어려운 문제로 그래프 알고리즘을 출제하기도 한다.

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

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

광고

Categories프로그래밍, 코딩 테스트