공부한 내용 기록하기 공부한 내용 기록하기

1. 최근접 점 쌍 문제란?최근접 점 쌍 문제(Closest Pair of Points Problem)는 2차원 평면에 주어진 여러 개의 점들 중 가장 가까운 두 점을 찾는 문제이다. 단순한 브루트포스(Brute Force) 방법은 모든 점 쌍을 비교하는 방식으로 O(n²)의 시간 복잡도를 가지지만, 분할 정복(Divide and Conquer) 알고리즘을 사용하면 O(n log n)의 시간 복잡도로 해결할 수 있다.1.1 문제 정의입력: n개의 점이 주어진다 (각 점은 (x, y) 좌표를 가짐)출력: 두 점 (p1, p2)의 최소 거리 d를 찾는다.목표: **최소 거리 ****d**를 O(n log n) 시간 내에 계산1.2 최근접 점 쌍 문제의 특징브루트포스 접근법은 O(n²)로 비효율적분할 정복 알..

1. 분할 정복 알고리즘이란?분할 정복 알고리즘(Divide and Conquer Algorithm)은 큰 문제를 작은 부분 문제로 나누어 해결한 후, 이를 결합하여 최종 해결책을 도출하는 알고리즘 기법이다. 이 방식은 재귀를 기반으로 하며, 복잡한 문제를 효율적으로 해결하는 데 널리 사용된다.1.1 분할 정복 알고리즘의 특징분할(Divide): 문제를 더 작은 부분 문제로 나눈다.정복(Conquer): 나눈 부분 문제를 각각 해결한다.결합(Combine): 해결된 부분 문제를 합쳐 원래 문제의 해결책을 도출한다.재귀적 접근: 대부분의 분할 정복 알고리즘은 재귀를 활용하여 구현된다.2. 분할 정복 알고리즘의 분류분할 정복 알고리즘은 여러 유형으로 분류되며, 대표적인 알고리즘은 다음과 같다.정렬 알고리즘:..