Algorithm4 [알고리즘] 이진 탐색(Binary Search) 이진 탐색(Binary Search) 정렬된 배열에서 특정 값을 찾는 알고리즘입니다.(필수조건!) 특징 반복 또는 재귀적 구현: 이진 탐색은 반복문이나 재귀 함수를 사용하여 구현할 수 있습니다. 정렬된 배열에서 사용: 이진 탐색은 정렬된 배열에서만 사용할 수 있습니다. 배열의 중간 값을 기준으로 탐색 범위를 좁혀가며 값을 찾습니다. 시간 복잡도: 이진 탐색의 시간 복잡도는 O(log n)입니다. 배열을 반으로 분할하면서 탐색 범위를 절반으로 줄여나가기 때문에 탐색 시간이 로그 시간에 비례합니다. 알고리즘 동작 방식 탐색 범위의 시작 인덱스와 끝 인덱스를 설정합니다. 탐색 범위의 중간 인덱스를 찾습니다. 중간 값과 찾고자 하는 값을 비교합니다. 중간 값이 찾고자 하는 값과 일치하면 탐색 성공입니다. 중간 .. 2023. 7. 16. [알고리즘] 병합 정렬(Merge Sort) 병합 정렬(Merge Sort) 특징 안정 정렬(Stable Sort): 동일한 값에 대해 상대적인 순서가 유지됩니다. 즉, 동일한 값의 원소들은 입력 배열에서의 순서와 동일한 순서로 정렬됩니다. 분할 정복(Divide and Conquer): 큰 문제를 작은 문제로 분할하여 해결하는 방식을 사용합니다. 추가적인 메모리 사용: 임시 배열을 사용하여 원소들을 병합하는 과정에서 추가적인 메모리가 필요합니다. 평균적으로 빠른 속도: 평균 시간 복잡도가 O(n log n)으로 매우 효율적입니다. 비교 기반 정렬(Comparison Sort): 원소들의 상대적인 크기를 비교하여 정렬합니다. 알고리즘 동작 방식 주어진 배열을 반으로 분할합니다. 분할된 부분 배열에 대해 재귀적으로 병합 정렬을 수행합니다. 분할된 부.. 2023. 7. 16. [알고리즘] 다익스트라 알고리즘(Dijkstra Algorithm) Dijkstra Algorithm ? 다이나믹 프로그래밍을 활용한 최단경로 탐색(Shortest Path Search)알고리즘 입니다. 특정한 하나의 시작지점에서 다른 모든 지점으로 가는 최단 경로를 탐색 합니다. 그래프의 방향의 유무는 상관이 없으나, 간선들중 단 하나라도 가중치가 음수(-)일 경우 다익스트라 알고리즘은 사용할 수 없습니다. 그래프 내에 가중치의 합이 음인 사이클이 존재한다면 무한하게 음의 사이클을 도는 경우 경로의 합이 음수의 무한대가 되기 때문에 최단 경로를 구성할 수 없게 되기 때문입니다. 다익스트라 알고리즘의 원리 1. 출발 노드를 설정 2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장 3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택 4. 해당 노드를 통하여 .. 2023. 7. 12. [알고리즘] A*알고리즘(Astar Algorithm) Astar(A*) Algorithm ? A* 알고리즘은 그래프 탐색 알고리즘 종류의 하나 입니다. 최단 경로 문제를 해결하는데 주로 사용되며 A*알고리즘은 효율적으로 경로를 찾습니다. 다른 탐색(Search)알고리즘보다 빠르고 정확한 결과를 얻을 수 있습니다. A*알고리즘은 *휴리스틱(heuristic)함수를 사용하여 탐색 중 경로의 우선순위(비용)를 결정합니다. 주어진 출발 노드(node)에서부터 목표의 노드(node)까지 가는 최단 경로(최저비용)를 찾아냅니다. *휴리스틱 함수 현재 상태에서 목표 상태까지의 예상 비용 또는 예측 값을 제공하는 함수입니다. 보통 경로 탐색에서 비용 함수로 사용됩니다. A* 알고리즘의 간단한 예제 #include #include #include #include using.. 2023. 7. 12. 이전 1 다음
