양방향탐색 검색 결과

해당 글 2건
meet in the middle 알고리즘 : 절반씩 쪼개서 생각해 봅시다.

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

bfs는 뎁스가 깊어질수록 생성되는 state 수가 매우 많아집니다. 그러면, depth를 줄일 수만 있다면, 속도가 획기적으로 개선된다는 이야기 또한 됩니다. 시작점과 도착점에서 동시에 bfs를 하는 방식을 양방향 bfs라고 하는데요. 이렇게 하면, s에서 e로 가는 최적해가 2x일 때, s에서 x만큼, e에서 x만큼의 깊이만 탐색하면 됩니다. s에서만 출발하면 2x만큼 탐색하는 것에 비하면 거의 절반 가까이 줄어버린 셈입니다. 일단 어떤 식으로 탐색을 하는지 개략적으로 보고, 입문 문제를 풀어보도록 합시다. 백준에서 흔히 알려진, 루빅의 사각형은 구현이 안 되면 매우 힘든 문제이기 때문에, 입문 문제로 제외하였습니다. branch factor가 b라고 해 봅시다. 즉, 한 상태를 queue에서 뺐을 ..
자료알고/알고리즘 2019. 8. 16. 14:34