뚜sh뚜sh

다익스트라 알고리즘(Dijkstra's algorithm) 그래프에서 두 정점 사이의 최단 경로를 찾는 알고리즘이다. 주로 가중치가 있는 그래프에서 한 정점에서 다른 모든 정점으로의 최단 거리를 찾을 때 사용된다. 가중치는 양수여야 한다. (음수 가중치가 있으면 알고리즘이 올바르게 작동하지 않을 수 있음) 다익스트라 알고리즘 원리 1. 초기화 시작 정점을 제외한 모든 정점의 거리를 무한대로 설정한다. 시작 정점의 거리는 0으로 설정한다. 2. 방문하지 않은 정점 중에서 최소 거리 정점 선택 현재까지 알려진 최단 거리에 있는, 아직 방문하지 않은 정점을 선택한다. 3. 최소 거리 정점을 경유지로 하여 인접 정점의 거리 갱신 선택된 정점을 경유하여 갈 수 있는 인접 정점들의 거리를 확인하고, 새로운 경로가 ..

파라메트릭 서치(Parametric Search) 최적화 문제를 결정 문제(예/아니오로 답할 수 있는 문제)로 변환하여 해결하는 기법 이 방법은 이분 탐색을 사용하여 가능한 해의 범위를 좁혀가며 최적의 해를 찾음 주로, 조건을 만족하는 최댓값 또는 최솟값을 찾을 때 사용됨 알고리즘 과정 범위 설정: 해가 될 수 있는 최솟값과 최댓값을 설정, 이 값들은 문제의 조건에 따라 결정됨 결정 문제 정의: 최적화 문제를 결정 문제로 변환, 이 결정 문제는 "특정 조건을 만족하는 값 X가 존재하는가?"와 같은 형태로 정의될 수 있음 이분 탐색 실행: 중간값 mid를 계산함, mid는 현재 고려 중인 해의 후보임 결정 문제를 mid에 대해 평가함 만약 mid가 조건을 만족한다면, 해의 범위를 mid 이상(또는 이하)으..

이분 탐색(Binary Search) 알고리즘 정렬된 배열에서 특정한 값을 효율적으로 찾는 탐색 기법 이 알고리즘은 '분할 정복' 전략을 사용하여, 탐색 범위를 반으로 줄여가며 원하는 값을 찾음 이분 탐색의 시간 복잡도는 O(log n)으로, 큰 데이터셋을 다룰 때 매우 효과적 알고리즘 과정 초기화: 탐색 범위를 설정, 이 때, left는 배열의 시작 인덱스, right는 배열의 마지막 인덱스로 초기화함 중간점 계산: 현재 탐색 범위의 중간 위치를 찾음, 일반적으로 mid = (left + right) / 2로 계산합니다. 부동 소수점을 사용하지 않고 정수 연산을 사용하기 때문에 오버플로우를 방지하기 위해 mid = left + (right - left) / 2로 계산하는 경우도 있음 탐색 조건 확인: ..