[SWEA] 4. 분할정복

이번 내용은 분할 정복에 관한 내용이었다. 분할 정복의 대표적인 문제로 머지 소트, 퀵 소트, 그리고 이진 탐색을 공부하였다. 특별히 어려운 내용은 없었다. 저번 학기에 알고리즘 수업에서 되게 자세히 배운 내용이라 친숙하였다. 대부분의 내용이 수업 때 배운 내용보다 깊지 않은 내용이었는데 임인성 교수님이 굉장히 잘 가르쳐 주시고 시험 문제도 시간 복잡도와 다양한 코드를 접할 수 있게 출제하셔서인지 기본적인 알고리즘에 대한 이해도가 굉장히 높아졌다는 것을 느낄 수 있었다!

주어진 문제를 보니 바로 vector를 이용한 쉬운 풀이와 오늘 배운 분할정복으로 직접 정렬하여 문제를 풀 수 있겠다. 하지만 두 문제 다 50개의 테스트 케이스 중 0개 성공, 즉 다 실패해버렸다. 2시간을 고민하고 답을 뒤지던 중 정렬하는 순서가 그냥 일반적은 compare를 사용하면 안 됐던 것이었다! compare 함수는 사전에서 처럼 사전 순으로 정렬만 하는데 문제에서는 길이별로 정렬을 먼저 하고 같은 길이에서만 정렬을 하는 것이었다. 분명히 읽은 기억이 있는데 백날 mergesort 코드만 들여다보고 있었다. 예제만 입력해보고 계속 왜 안되냐고 화내고 있었던 것이다. 오늘 백준 포스팅에 문제를 잘 읽자라고 또 썼는데 문제를 또 잘 안 읽어버렸다. 상당히 난감한 하루인 것 같다.