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