알고리즘15 [알고리즘] 삽입 정렬(Insertion Sort) 삽입 정렬(Insertion Sort) 특징 안정 정렬(Stable Sort): 동일한 값에 대해 상대적인 순서가 유지됩니다. 즉, 동일한 값의 원소들은 입력 배열에서의 순서와 동일한 순서로 정렬됩니다. 제자리 정렬(In-place Sort): 입력 배열 이외에 추가적인 메모리를 사용하지 않습니다. 입력 배열 내에서 정렬이 수행됩니다. 비교 기반 정렬(Comparison Sort): 원소들의 상대적인 크기를 비교하여 정렬합니다. 알고리즘 동작 방식 삽입 정렬은 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누어 처리합니다. 정렬되지 않은 부분의 첫 번째 원소를 정렬된 부분에 삽입하는 과정을 반복하여 전체 배열이 정렬될 때까지 진행합니다. 정렬되지 않은 부분에서 첫 번째 원소를 선택합니다. 이 원소를 정렬.. 2023. 7. 16. [알고리즘] 선택 정렬(Selection Sort) 선택 정렬(Selection Sort) 간단하지만 비효율적인 정렬 알고리즘입니다. 특징 불안정 정렬(Unstable Sort): 동일한 값에 대해 상대적인 순서가 유지되지 않을 수 있습니다. 제자리 정렬(In-place Sort): 입력 배열 이외에 추가적인 메모리를 사용하지 않습니다. 입력 배열 내에서 정렬이 수행됩니다. 비교 기반 정렬(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. [알고리즘] 보간 (interpolation) 선형 보간 ( Linear Interpolation ) ( Lerp ) 선형 보간은 1차원 직선상에서 두개의 위치의 값이 주어졌을때 그사이에 있는 값을 찾기 위한 비례식 입니다. 위의 예시를 참고로 합니다. a(2,1), b(7,4) 두개의 위치를 알고있을때 c의 위치를 구하기위해서는 선형 보간법을 사용할 수 있습니다. 이때 c의 정확한 위치를 알수는 없으나 좌표상에서 어느정도의 비율에 위치하였는지는 유추가 가능합니다. 위의 공식은 C++ 내부의 구현해둔 함수로 사용이 가능합니다. 위의 사진의 원본출처에서 좀더 상세한 구현도 볼 수 있습니다. [Algorithm] 선형 보간법 (Linear interpolation) 선형 보간법 (Linear interpolation) 선형 보간법을 구현하는 방법에 대해.. 2023. 5. 22. [알고리즘] 이진탐색트리 이진탐색트리? 이진 방식의 탐색을 하기 위한 구조 입니다. 이진탐색트리에서 모든 노드는 아래의 규칙을 가지고 있습니다. 모든 노드의 key는 중복이 되지않습니다. 왼쪽방향의 자식 노드는 부모값보다 작다. 오른쪽방향의 자식 노드는 부모값보다 크다. 각각의 노드들이 중앙 요소가 되며 임의의 어떤 노드의 왼쪽 서브트리에는 해당 노드보다 작은 값들만, 반대로 어떤 노드의 오른쪽 서브트리에는 해당 노드보다 큰 값들만 있습니다. 이진탐색트리의 특징 장점? 1. 일반 적으로 이진 탐색의 중앙 요소를 알아야 왼쪽과 오른쪽 두곳의 트리를 나눌 수 있기 때문에 "배열"에서만 사용할 수 있습니다. 즉, 배열구조가아닌 연결리스트 혹은 동적으로 크기가 변하는 배열은 사용할 수 없습니다! 2. 배열을 사용하여 탐색할 때 보다 시.. 2023. 4. 27. 이전 1 2 3 다음
