알고리즘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. [백준/C++] 1976 여행 가자 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 지난번에이어 이번에도 Union-Find 알고리즘을 이용해야하는 문제 입니다. 아직 Union-Find 알고리즘에 익숙하지않기때문에 참고 합니다. #include #include #include #include #include #define fastio cin.tie(0)->ios::sync_with_stdio(0); cout.tie(0); using namespace std; // 백준 1976번 여행 가자 ( Union - Find 문제 ) int n, m;.. 2023. 5. 30. [백준/C++] 1717 집합의 표현 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 대표적인 Union Find 문제 라고 합니다. 해당 알고리즘에대해서 배운적이 없었기때문에 단순히 구조체 배열 구성후 변수 a는 실행조건으로 b, c 는 단순한 구조체 배열에 속한 변수로 하여 문제를 풀려했으나 실패. 다른 풀이를 참고 하도록 합니다. #include #define fastio cin.tie(0)->ios::sync_with_stdio(0); cout.tie(0); using namespace std; // .. 2023. 5. 24. [알고리즘] 보간 (interpolation) 선형 보간 ( Linear Interpolation ) ( Lerp ) 선형 보간은 1차원 직선상에서 두개의 위치의 값이 주어졌을때 그사이에 있는 값을 찾기 위한 비례식 입니다. 위의 예시를 참고로 합니다. a(2,1), b(7,4) 두개의 위치를 알고있을때 c의 위치를 구하기위해서는 선형 보간법을 사용할 수 있습니다. 이때 c의 정확한 위치를 알수는 없으나 좌표상에서 어느정도의 비율에 위치하였는지는 유추가 가능합니다. 위의 공식은 C++ 내부의 구현해둔 함수로 사용이 가능합니다. 위의 사진의 원본출처에서 좀더 상세한 구현도 볼 수 있습니다. [Algorithm] 선형 보간법 (Linear interpolation) 선형 보간법 (Linear interpolation) 선형 보간법을 구현하는 방법에 대해.. 2023. 5. 22. 이전 1 2 3 다음
