문제 해결력을 높이는 알고리즘과 자료 구조 12장 연습 문제 풀이

GitHub - hijkl2e/drken1215_algorithm_solution: 문제 해결력을 높이는 알고리즘과 자료 구조 연습 문제 풀이

연습 문제 12.5번과 12.6번은 굉장히 어렵다.

 

연습 문제 12.5번은 단순히 quickselect 알고리즘을 구현하는 문제인 줄 알았다.

이 경우 평균 시간 복잡도는 O(N)이 되어 문제의 조건을 만족한다.

자세히 보니 최악 시간 복잡도가 O(N)인 알고리즘을 설계하는 문제였다.

이 문제는 median of medians 알고리즘으로 해결할 수 있다.

위키백과의 의사 코드를 참고하여 열심히 구현하였다.

 

연습 문제 12.6번도 난이도가 미쳤다.

문제 출처는 AtCoder Tenka1 Programmer Contest 2017 F - ModularPowerEquation!!

tourist가 대회 시간 내에 못 푼 문제를 나 혼자서 풀이하는 것은 절대 불가능한 일이다.

문제를 읽자 마자 에디토리얼을 켰다.

 

그리고 에디토리얼을 이해하는 데 이틀이 걸렸다.

솔직히 말하면 에디토리얼을 완전히 이해하지 못해서 내 방식대로 다시 풀었다.

이 문제는 적어도 다음과 같은 배경 지식을 요구한다.

• Euler's phi function
• Euler's theorem
• Chinese remainder theorem

배경 지식이 제로였으니 쉽게 풀 수 있을 리가 없는 문제였다.

아무튼 참교육 제대로 당했다.

 

끝