c++39 [알고리즘] 삽입 정렬(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. [C++/자료구조] 힙(Heap) Heap : 힙 - 특징 1) 완전 이진 트리 형태 2) 부모 노드와 자식 노드 간의 대소관계가 정해진 완전 이진 트리 구조 3) 루트 노드는 항상 최솟값 또는 최대값을 가진다 4) 최소 힙 또는 최대 힙이 있다. - 최소 힙 : 부모 노드의 값이 자식 노드의 값보다 작은 경우 - 최대 힙 : 부모 노드의 값이 자식 노드의 값보다 큰 경우 - 장점 1) 최소값 또는 최대값을 상수시간 O(1)에 찾을 수있다. 2) 정렬, 우선순위 큐 등에서 유용하게 사용 3) 이진 탐색 트리보다 간단하고 빠르게 구현할 수 있다. - 단점 1) 중복된 값의 처리가 어렵다. 2) 삽입, 삭제, 연산에 시간 복잡도가 O(log n)이 소모된다. Heap.h #pragma once void DoHeap(); class Heap .. 2023. 7. 15. [알고리즘] 다익스트라 알고리즘(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. [C++/자료구조] 연결 리스트(Linked List) & 양방향 연결 리스트(Double Linked List) Linked List : 연결 리스트 - 특징 1) 노드와 포인터로 이루어진 선형 자료구조 2) 노드는 데이터와 다음 노드를 가리키는 포인터로 구성된다 3) 크기가 가변적이므로 동적 메모리 할당과 함께 사용되기도 한다 - 장점 1) 삽입, 삭제가 용이하며, 데이터의 크기가 가변적일 경우 유용하다 2) 데이터를 읽는 것보다 데이터를 추가, 삭제하는게 빠르다 - 단점 1) 데이터를 찾는 데 걸리는 시간이 선형적으로 증가하기 때문에 탐색 속도가 느리다 2) 중간에 있는 노드를 삭제하면 메모리 낭비가 발생할 수 있다 Linked List.h #pragma once void DoLinkedList(); void PrintList(); class LLN // Linked List Node { public: stat.. 2023. 7. 8. 이전 1 2 3 4 5 6 7 다음
