소프트웨어 마에스트로 15기 코딩테스트 정리
SWM(소마) 란?
과학기술정보통신부의 주도 아래 진행되는 국가과정으로, 창업에 관심이 있는 소프트웨어 분야 인재를 지원하는데에 그 초점이 맞추어진 교육과정입니다.
컨셉을 한 문장으로 정리해보자면
우리가 모든 준비를 해줄테니 넌 프로젝트만 만들어라!
에 제일 가깝습니다.
저기서의 "모든 준비" 에는
- 월 장학금 100만원
- IT기기 구입비 150만원
- 프로젝트 개발 도중의 비용 지원
등등이 있습니다.
코딩테스트
올해 소프트웨어 마에스트로 과정의 코딩테스트는 프로그래머스 환경에서 진행되었으며, 작년 1차 전원 합격이 있었던 14기에 비해 큰 문제 없이 원활히 진행되었습니다.
최종적으로 결과를 돌아보자면 최근 몇년에 비해 1차 커트라인이 상승했으나,
2차 커트라인은 최종적으로 비슷한 수준이었어서
정부 지원금 감소로 인한 규모 축소가 바로 와닿았습니다.
1차, 2차 둘 모두
- 알고리즘 4문제
- mysql 1문제
구성이었으며, 작년의 출제 기조를 이어받아
2차 코딩테스트에서 mysql 문제의 난이도가 높았던 것이 주요한 특징입니다.
준비
사실 필자는 mysql 관련한 부분만 조금 준비를 해갔습니다. 백준을 통해 굉장히 오랜시간 문제를 풀어왔기 때문인데, 코딩테스트 직전에 Diamond V 까지 달성해놓고 시험을 봤습니다.
준비 관련해서는 제 글이 별 도움이 될 것 같지는 않고, 다른 분들 글 보시면 조금 더 도움이 되시지 않을까 싶습니다...
1차 코딩테스트
필자는 1차 코딩테스트에서 1,2,3,4,5 번을 모두 해결하였습니다.
1차 코딩테스트의 난이도는 작년 대비 쉬운 편이었습니다.
난이도를 대략적으로 어림잡아 보면
solved.ac 기준
브론즈 - 실버하위 - 실버상위 - 골드,
mysql은 프로그래머스 1단계 정도였습니다.
안정적인 커트라인은 4솔 으로 4번 문제를 포기하고
실버까지를 안정적으로 풀어내면 확실하게 합격할 수 있었습니다.
보통 3솔 선에서 안정적으로 합격하는데, 타 년도 대비 문제가 쉽게 출시되어서 커트라인이 올랐습니다.
1번(bronze)
평이한 난이도의 구현 문제입니다.
지문에서 하라는 바를 그대로 구현해주면 됩니다
2번(silver)
적절한 난이도의 구현 문제였습니다.
높이가 2라는 조건을 활용하면 밑변의 길이가 반드시 삼각형의 넓이라는 점을 관찰할 수 있으며, 입력으로 들어오는 점들을 통해 밑변의 길이를 구해내면 됩니다.
3번(silver)
구조체나 c++ 기준 std::map을 적극적으로 활용해야 했던 문제입니다.
해당 개념을 알고 있다는 전제 하에 체감 난이도가 확 내려가며,python 언어의 경우 기본적인 배열에 문자열 값을 넣어 dictionary 자료구조를 사용할 수 있으므로 파이썬 언어 사용자분들에게 더 쉬운 문제이지 않았나 싶습니다.
4번(gold)
수열을 그리디하게 구성하는 문제였습니다.
각각의 숫자들에게 두 가지 경우의 수가 있는데,
- 나머지를 계산해보고 해당 숫자가 들어가야할 자리에 들어감.
- 나머지 계산 없이 빈 장소 중 아무것이나 골라서 들어감.
배열이 정렬되어서 들어오므로
모든 수에 대해서 들어갈 수 있는 두 가지 경우 중 가장 왼쪽에 수를 써넣으면
사전순으로 가장 앞서는 단 하나의 수열을 만들어 낼 수 있습니다.
2번 빈 장소 의 관리에 std::priority_queue를 사용하였습니다.
시간복잡도는 O(NlogN)
5번
group by 문을 사용해서 적절히 묶어주면 금방 해결할 수 있습니다.
2차 코딩테스트
필자는 2차 코딩테스트에서 1,3,5번을 해결하였습니다.
2차 코딩테스트는 난이도가 매년 오르고 있는데,
난이도를 대략적으로 어림잡아 보면
실버 - 골드 - 골드 - 플래티넘
정도의 난이도를 가지고 있었습니다.
mysql 역시 어려운 난이도를 가지고 있고, 일반적 mysql 코딩테스트에서 묻지 않는 개념들을 요구하고 있으므로 공부시간을 조금 투자할 필요가 있을 듯 싶습니다.
확실한 커트라인은 3솔 으로, 2솔으로도 합격이 가능한 것으로 알고 있습니다.
2시간 내에 실수 없는 골드 랜덤디펜스라서 난이도가 꽤나 되는 편입니다.
최근 몇년간의 출제 기조인 빡구현 / 그리디 사고력 위주와 그 형태가 조금 달라져서, 코딩테스트 준비에 적합한 프로그래머스에 가까운 스타일이라기보다는
전반적으로 백준에 더 가까운 스타일이라고 느꼈습니다.
1번(silver)
문자열에 대해서 묻던 쉬운 난이도의 문제였습니다.
현대 프로그래밍 언어의 대부분은 string간의 덧셈 연산을 지원하고 있으므로,
string을 여러 부분string으로 분리하는게 문제의 핵심 발상인데 크게 어렵지 않습니다.
구현 시 마지막 substring을 처리 안하는 실수가 잦으니 유의하도록 합니다.
2번(gold)
동적 계획법을 사용한 Gold V 백준 문제에서와 비슷한 발상을 요구합니다.
스타트링크 (Startlink)
dp[i][A][B] // 시간이 i, 바구니 1과 2의 위치가 각각 A,B 일때의 최고 점수
다음과 같은 3차원 dp 테이블을 구성하고,
바구니 A와 B가 각각
- 왼쪽으로 한칸
-1 - 가만히 있음
0 - 오른쪽으로 한칸
+1
의 전체 9가지 경우에 대해서 계산해줄 수 있습니다.
최종적인 정답은 모든 a와 b에 대해서 dp[N][a][b] 의 최댓값입니다.
저는 그리디로 접근하였어서 풀지 못하였습니다.
3번(gold)
머지 소트, 세그먼트 트리 등의 완전 이진 트리를 가지고 노는 발상을 할 수 있는가 를 묻는 문제였습니다.
트리에서 한 정점을 잡고 뒤집는 연산을 진행해주면
해당 트리 밑의 모든 숫자들의 순서가 반대로 뒤집히는데,
트리의 리프 노드가 아닌 N-1개 모든 노드에 뒤집는 연산을 선택적으로 적용하여
리프노드를 왼쪽에서부터 나열하였을때 사전순 최소를 만들어주면 됩니다.
N이 1e6으로 백트래킹 등의 풀이로는 시간초과를 거의 확실히 받게 되며,
저는 세그먼트 트리를 통해 해결하였습니다.
뒤집는 연산의 여부를 저장할 배열을 하나 만들고,
보고 있는 정점의 왼쪽에 붙어있는 모든 숫자들과
오른쪽에 붙어있는 모든 숫자들을 서로 비교합니다.
왼쪽 구간에서의 최솟값보다 오른쪽 구간에서의 최솟값이 더 작으면, 구간 전체를 뒤집어서 오른쪽 구간이 더 앞서도록 해야 사전순 조건을 충족할 수 있으며,
루트 노드부터 dfs를 돌리면서 이러한 처리를 통해 어느쪽을 먼저 탐색해야 할지를 기록해 주었습니다.
이 과정에서 구간 최솟값을 logN에 찾아내기 위해서 RMQ 세그먼트 트리를 사용하였습니다.
명백하게 뇌절 풀이입니다, 이것보다 쉽게 해결할 수도 있습니다.
반례 걱정할 일이 없이 가장 확실한 풀이이기에 이렇게 작성하였습니다.
4번(platinum)
램프를 켜고 끄는 platinum IV 그리디 문제에서의 발상을 차용합니다.
스타트링크 (Startlink)램프가 +와 x 두가지 형태로 주어지는데, 이중 + 램프는 서로간에 간섭할 수 없기에 켜져있는 경우 반드시 꺼야 합니다.
이러한 전처리를 거치고 나면
x 램프만 남는데, 전체 배열을 45도 회전해서 보면
백준 문제에서와 똑같은 발상을 요구받으며,
ㄱ 모양의 1줄을 비트마스킹 브루트포스로 처리하고
나머지 모든 x 램프를 그리디하게 처리해주면 됩니다.
발상 자체는 금방 떠올렸으나, mysql 문제에 너무 많은 시간을 투입하여 실제로 완성까지는 못했어서 조금 아쉬운 문제였습니다.
5번
서브쿼리를 3개정도 사용해도 되고, mysql 사용자 변수를 사용해도 됩니다.
프로그래머스 2레벨 정도의 SUM 함수를 "거의 대부분" 숙지하고 있어야 하며,
요구사항이 많아서 AC 코드의 길이가 긴 편이었습니다.
정리
올해 15기 코딩테스트에 사용된 알고리즘을 정리해보자면,
구현 자료구조-map 그리디 동적계획법 문자열 트리 머지 소트 비트마스킹 완전탐색
정도가 있습니다. 해당 개념들을 전부 커버하려면 solved ac 기준 Platinum 정도는 되어야 하지 않을까 싶네요.
커트라인으로 보자면
- 1차 코딩테스트 4솔 안정권
- 2차 코딩테스트 2~3솔 안정권
이었으며, 2차 코테의 난이도가 적절하다고 느껴졌기에 아마 커트라인은 1차 코딩테스트에서만 살짝 조정이 있지 않을까 싶습니다.
