meet in the middle 알고리즘 : 절반씩 쪼개서 생각해 봅시다.
제가 제대로 된 코딩을 한 지 별로 안 되서 그런지, 백준 1442번 같은 문제를 만나면 당황스럽더라고요. 문제는 다음과 같습니다. 부끄럽게도, 어떻게 Dynamic programing을 해서 트래킹을 해야 할 지 감이 오지 않았습니다. 그러면 어떻게 해야 할까요? 손을 놓고 가만히 있어야 할까요? 아닙니다. 정확하게 문제를 앞쪽, 뒤쪽으로 나누었을 때, 적절한 전처리를 해서, 앞쪽만 보고 접근할 수 있다면, 양방향 탐색과 유사한, 중간에서 만나는 meet in the middle 이라는 기법을 고려해 볼 만 합니다. 코딩 테스트에서 제일 중요한 것은 문제를 어떻게 읽느냐였다고 했습니다. 앞에 15개, 뒤에 16개로 왜 나눌까요? 일단, 그 전에 R - L이 20만 이하인 경우부터 해결해 봅시다. 먼저,..
자료알고/알고리즘
2020. 1. 20. 16:01
최근댓글