최근접 점 쌍의 분할 정복
점을 x·y 좌표 순서로 나누어 재귀적으로 최소 거리를 계산하고, 분할 경계 주변의 strip 후보를 비교하는 구조를 구현했습니다. 작은 입력에는 직접 비교를 사용했습니다.
프로젝트 목록
알고리즘 구현 프로젝트 · 2024 가을 · CS330
C++ Algorithms
최근접 점 쌍, 제약이 있는 경로 탐색, 배낭·정렬·순열 문제를 C++ 자료구조와 알고리즘으로 해결한 과제 모음입니다.
C++Graph SearchDivide and ConquerDynamic Programming
OVERVIEW
프로젝트 소개
최근접 점 쌍, 배터리와 충전 횟수가 제한된 경로, 배낭·순열·정렬 문제를 C++로 풀었습니다. 문제의 제약을 상태로 표현하고 그 상태를 탐색하거나 갱신하는 방식을 구현했습니다.
Convex hull, maximum subarray, TSP, closest pair, 그래프 도달 가능성, knapsack, merge sort와 heap을 다룬 과제 중 최근접 점 쌍과 제한 조건이 있는 그래프 탐색을 중심으로 소개합니다.
MY CONTRIBUTION
담당한 구현
충전 횟수와 잔량을 포함한 탐색
현재 위치만으로 상태를 표현하지 않고 위치·남은 충전 횟수·배터리를 함께 관리했습니다. 큐에서 다음 간선을 탐색하고 같은 상태에 더 좋은 잔량으로 도달하면 갱신하는 방식으로 도달 가능성을 확인했습니다.
문제별 자료구조 선택
그래프의 인접 리스트와 큐, 정렬된 점 배열과 재귀, 배낭과 순열 등 각 문제에 맞는 상태 및 반복 구조를 구현한 제출물을 정리했습니다.
DELIVERED WORK
구현 결과
- Closest Pair · Divide and Conquer
- 자원 제한을 포함한 그래프 상태 탐색
- 정렬·힙·순열·배낭 문제의 개별 제출 코드
DigiPen 알고리즘 수업에서 작성한 개별 과제입니다. 그래프 문제의 구현은 위치·충전 횟수·배터리 상태를 사용하는 큐 기반 탐색입니다.