브루트포스로 풀기에는 N이 약간만 너무 클때,
분할정복처럼 절반씩 나누고 연산한다음 합치는 연산을 하는걸 meet in the middle이라고 한다.
분할정복처럼 반복적으로 나누고 합치고 하지는 않고 1회성으로만 하는거 같다.
합치는 연산은 문제마다 다르며, 투포인터가 사용될때도 있다.
샘플 문제는 여기를 참고하자.
아직 정확히 모르는점들
meet in the middle을 반복하면 계속해서 복잡도를 줄일 수 있는가? 만약 가능하다면 분할정복과의 차이점은?
합치는 연산에서 투포인터 말고 다른게 쓰는 예는 어떤게 있는가?
- 요건 이분탐색이 있는데, 이분탐색도 직접구현 기준으로 보면 left, right 포인터를 쓰는거라 투포인터의 일종으로 볼 수는 있을듯?
반응형
'Programming > Algorithm' 카테고리의 다른 글
| LIS(Longest Increasing Subsequence) - 가장 긴 증가하는 부분 수열 (0) | 2023.08.13 |
|---|---|
| 기하 - 2선분의 교차점 구하기 (0) | 2023.07.25 |
| 투 포인터 (0) | 2022.03.01 |
| 이분 그래프(Bipartite Graph) (0) | 2022.02.22 |
| 세그먼트 트리(Segment Tree, 구간트리) (0) | 2020.05.23 |