☑️ C++로 이해하는 다익스트라(Dijkstra)다익스트라 알고리즘은 최단 경로를 구하는 알고리즘이다. 한 정점에서 모든 정점까지의 최단 경로를 구하면서 각 정점까지의 최단 경로를 모두 찾는다. 오래된 알고리즘이라서 이를 개선하거나 영향을 받은 알고리즘도 많은데, 각각 A* 알고리즘, 벨만-포드 알고리즘, 플로이드-워셜 알고리즘 등이 있다. ☑️ 다익스트라 알고리즘 프로세스각 노드의 거리를 무한대로 초기화한다.시작노드의 거리는 0으로 설정한다.이전 노드를 저장할 공간을 Null로 설정한다.방문하지 않은 노드 집합 Q에 모든 노드를 추가한다.노드 집합 Q가 비어있지 않다면 반복한다Q에서 Dist가 가장 작은 노드를 선택한다.Q에서 선택한 노드를 제거한다.선택 노드의 인접 노드를 순회한다.새로운 거리를 확..

참고 : Do it! 자료구조와 함께 배우는 알고리즘 입문 (파이썬 편)☑️ C++로 이해하는 단순 선택 정렬☑️ 단순 선택 정렬(Selection Sort)이란 무엇일까?간단하게 사용할 수 있는 정렬 중 하나로, 기본 원리는 배열에서 가장 작은 원소를 찾아서 맨 앞으로 이동시키는 과정을 반복시키면서 정렬한다. ☑️ 단순 선택 정렬 의사코드1. 전체 배열의 최솟값을 찾는다.2. 맨 앞 원소와 교환한다.3. 정렬된 부분을 제외한 나머지 부분에서 다시 최솟값을 찾는다.4. 모든 원소가 정렬될 때까지 반복한다. ☑️ 단순 선택 정렬의 시각화 ☑️ 단순 선택 정렬 코드#include #include #include #include #include using namespace std;int main() { ve..

참고 : Do it! 자료구조와 함께 배우는 알고리즘 입문 (파이썬 편)☑️ C++로 이해하는 버블 정렬정렬 알고리즘은 데이터를 다루는 모든 프로그램에서 필수적인 요소로 사용된다. 정렬을 구사할 수 있는 다양한 알고리즘 중에서 버블 알고리즘은 간단한 알고리즘에 속하면서 개념을 이해하기가 쉽고 구현이 직관적이다. 하지만 효율성 문제로 실제 프로젝트에서는 많이 사용되지 않는다. ☑️ 버블 정렬이란 무엇일까?버블 정렬은 인접한 두 원소를 비교하여 필요에 따라 위치를 교환한다. 이 과정을 반복하면 큰 값이 배열의 끝으로 천천히 이동하는데, 이러한 모습이 거품이 수면 위로 떠오르는 것과 비슷해서 버블 정렬이라는 이름을 가진다. 1️⃣ 버블 정렬 의사코드1. 배열의 첫 번째 원소부터 시작해서 인접 원소와 비교한다...

참고 : Introduction to Algorithm참고 : https://www.geeksforgeeks.org/what-is-minimum-spanning-tree-mst/☑️ C++로 이해하는 MST전자 회로는 여러 전자 부품들로 구성되는데, 이 중에서 '핀'이란 이름의 금속 연결부가 있다. 핀들을 서로 연결하여 전기가 흐를 수 있는 경로를 만드는 것이 회로 설계의 기본인데, N개의 핀을 연결하기 위해서는 최소 N-1개의 전선을 사용한다. 전선 연결 문제를 해결하기 위해서 최소 신장 트리(Minimum Spanning Tree)를 사용할 수 있다. 핀은 그래프의 Node에 해당하고 전선은 그래프의 Edge에 해당하기 때문이다. 1️⃣ 신장 트리(Spanning Tree) ?신장 트리는 순환이 존재..

참고 : https://www.geeksforgeeks.org/greedy-algorithms/☑️ C++로 이해하는 그리디📌 이론과 알고리즘은 다르다.그리디, 부르트포스, 위상정렬 등 다양한 알고리즘 이론들이 존재한다. 이 방법들은 '제안된 이론'을 의미한다. 이론을 어떤 방식으로 구현하냐에 따라서 알고리즘이 갈린다. 예를 들어 '정렬'은 어떠한 기준대로 배치를 바꾸는 것을 의미한다. 정렬이란 이론을 실행하기 위해서 버블 정렬, 힙 정렬, 퀵 정렬 등 다양한 정렬 알고리즘들이 존재한다. ☑️ 그리디 알고리즘(Greedy)프로그래밍 용어는 있는 단어에서 가져온 것들이 많다. 네트워크(Network)는 그물 'Net'와 'Work'의 합성어로 그물처럼 얽혀 연결되어 있는 것을 의미한다. 그리디 알고리즘의..

참고 : Do it! 자료구조와 함께 배우는 알고리즘 입문 (파이썬 편)☑️ C++로 이해하는 부르트포스부르트포스(Brute Force)는 검색하는 방법 중에서 기초적이고 쉬운 알고리즘이다. 이 알고리즘은 확인이 가능한 모든 경우의 수를 하나씩 확인한다. 선형 검색에서 단순하게 확장한 알고리즘이라서 단순법으로도 부른다. 단어부터 알고리즘의 성격을 볼 수 있는데 Brute는 짐승, Force는 힘을 의미한다. 이 두 단어를 합쳐서 직역하면 짐승같은 힘을 말한다. 무차별적인 힘으로 풀어낸다는 알고리즘의 성격을 그대로 담고 있다. 1️⃣ 왜 부르트포스를 사용할까?부르트포스가 단순하고 직관적이기 때문이다. 시간과 기회가 무한하다고 가정한다면 부르트포스가 풀어내지 못할 문제는 없다. 모든 가능성을 시도하기 때문에..