아주 간단한 풀이 스케치

저작권의 철퇴를 맞기 싫어서 프로그래머스에 기출문제가 업로드되기 전 까지는 문제 내용을 공유할 수도, 제가 제출한 코드를 공개할 수도 없습니다 ㅠ_ㅠ 그로 인해 아주 두루뭉술하게 작성하는 점 양해부탁드려요

 

Q1

알고리즘 분류 : STL map, 구현

예상 난이도 : S4

 

특이사항 X

 

Q2

알고리즘 분류 : 수학

예상 난이도 : S4

 

서술이 조금 더 매끄러웠으면 좋았을 것 같긴하다만 아무튼 특이사항 X

 

Q3

알고리즘 분류 : 배열, 구현

예상 난이도 : S4

 

특이사항 X

 

Q4

알고리즘 분류 : 그리디

예상 난이도 : S1-G4

 

정확성은 n발을 10곳에 나누어 배치하는 모든 경우를 따져서 챙길 수 있을 것 같고, 효율성은 라이언이 챙겨갈 점수를 선택하고 나면(ex : 10,8,3점만 챙기겠다) 라이언이 각 점수에 화살을 몇 발 맞춰야하는지가 정해짐. $2^{10}$개의 모든 조합을 확인하는 방식으로 통과 가능

 

Q5

알고리즘 분류 : 트리, 비트마스크, BFS/DFS

예상 난이도 : G5-G3

 

정확성은 백트래킹으로 챙길 수 있을 것 같고, 효율성은 비트마스킹을 통해 상태를 관리하고 방문 표시를 남고 방문한 상태에서 또 계산을 안하도록 하는 방식으로 $O(2^{17})$에 통과 가능

 

Q6

알고리즘 분류 : DP

예상 난이도 : G4-G2

 

BOJ 11660 응용 ㅠㅠ 11660번을 봐도 감이 안오시면 2d update query constant 라고 검색해보세요

 

Q7

알고리즘 분류 : 게임이론, 백트래킹

예상 난이도 : G2-P5

 

맨 처음에는 모든 상태를 다 저장한 후 BFS로 풀릴 줄 알았는데 상태의 수가 $O(2^{25} \cdot 5^4)$일 것으로 보여서 뭔가 이상하다 싶었음. 답의 최대값이 어떻게 될지 모르겠어서 시간복잡도를 가늠하지 못한 상태로 일단 해보자는 생각으로 그냥 가상의 minimax tree 그리면서 재귀적으로 풀어냈는데(게임 이론에 안익숙하면 BOJ 16571가 비슷하게 풀릴것 같으니 참고) 그냥 바로 통과됐음.

 

간단한 총평 : 작년에는 3번부터 난이도가 확 올라갔는데 올해의 경우 1, 2, 3번은 충분히 풀만한 난이도로 출제되었다. 작년에 비해 알고리즘 분류가 그렇게 다양하지는 않았는데 7번은 좀 생소한 유형의 문제였다. 맨날 한 자리 해먹던 투 포인터/이분탐색/최단경로 문제는 등장하지 않았다. 반면 비트마스킹은 뒷쪽 문제에서 여러번 필요했다.

 

응시자의 입장에서 6, 7번은 어려워서 버린다고 해도 1,2,3,4번과 5번의 부분점수는 챙길만했다고 생각한다. 만약 1, 2, 3번에서 오랜 시간이 소모되었거나 세 문제 중에서 풀어내지 못한 문제가 있다면 구현력을 더 올릴 필요가 있어보인다.

 

고생 많으셨습니다!