[일반] 가까운 두점 찾기 문제 드디어 풀었다 ㅠㅠ

[익명(59.24)]

라인스위핑 문제를 접해보지 못해서 그랬는지

마지막 두점찾기 문제가 이중 가장 어려웠음 ㅠ

그래도 라인 스위핑에 대해서 많은 고민을 해주게 하는 좋은 문제였음.

나머지는 전형적인 분할정복 문제였는데 그 중 기억남는 문제는 피보나치3 였음.

이걸 풀려면 큰 수의 곱셈을 nlogn에 할 수 있어야 했고, 행렬식에 대한 간단한 이해도 있어야 됐는데

풀면서 여러 가지 배울게 많았던 문제였당

[메리체리(mrscherry)]

피보나치수 3 큰 수 곱셈이 필요한 문제가 아닐텐데 ㄷㄷ

[시아닌(kimjg1119)]

띠용 피보나치3 큰수곱셈문제 아닌뎅

[시아닌(kimjg1119)]

그리고 두점찾기 문제는 스위핑 말고 다른 클래시컬한 DnC로도 풀 수 있어용

[익명(59.24)]

행렬 곱셈 알고리즘이 정수의 큰수 곱셈 알고리즘 하고 결이 동일함

[익명(59.24)]

가만 생각해보니깐 완전히 다른말이네요 ㅋㅋㅋㅋ

[익명(59.24)]

아 정수의 큰수 곱셈이라고 해서 헤깔렸나? 동일한 문제가 있는진 모르겠는데 정확히는 정수의 제곱 알고리즘이 맞음

[익명(59.24)]

위에껄 전부 분할정복으로 풀어서 라인스위핑으로 한번 풀어보고 싶어서요 ㅋㅋㅋㅋ

[메리체리(mrscherry)]

그말이구나

[0xrgb(0xrgb)]

아니 저기서 왜 두점이나와?? 난이도 차이가 심각한데