참고 : 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️⃣ 왜 부르트포스를 사용할까?부르트포스가 단순하고 직관적이기 때문이다. 시간과 기회가 무한하다고 가정한다면 부르트포스가 풀어내지 못할 문제는 없다. 모든 가능성을 시도하기 때문에..

참고 : https://www.geeksforgeeks.org/topological-sorting/?ref=gcse_outind☑️ C++로 이해하는 위상정렬위상정렬(Topological Sort)은 방향 그래프에서 정점들을 선형으로 정렬하는 알고리즘이다. 풀어서 설명하면 그래프에서 순서가 있는 노드들을 순서대로 나열하는 행동을 한다. 우리가 출근을 하는 과정을 살펴보자.1. 아침에 기상한다.2. 씻는다.3. 옷을 입는다.4. 아침 식사를 한다.5. 필요한 물건을 다 챙겼는지 확인한다.6. 집 밖으로 나선다.이런 과정들을 거쳐서 우리는 회사에 출근할 수 있다. 아침에 기상하는 것을 시작으로 집 밖으로 나서는 과정은 모두 순서대로 이루어진다. 아침에 기상하지 않고 식사를 하거나 집 밖으로 나설 수 없다. ..

참고 : 알고리즘 문제 해결 전략☑️ C++로 이해하는 동적 프로그래밍동적 프로그래밍(Dynamic Programming)을 부르는 정확한 언어는 동적 계획법이다. 단어는 최적화 문제를 연구하는 수학 이론에서 왔기에 전산학에서 말하는 Dynamic, 혹은 Programming과는 연관이 없다. 하지만 블로그에 작성할 때는 나에게 익숙한 동적 프로그래밍으로 올린다.동적 프로그래밍은 복잡한 문제를 작은 하위 문제로 분할하여 해결하는 알고리즘 설계 방법을 의미한다. 이 방법은 분할 정복과 같은 접근 방식을 가진다. 하위 문제의 해결책을 저장하고 재사용함으로서 계산의 효율성을 높인다. 이때 이미 계산한 값을 저장해 두는 메모리의 장소를 캐시(cache)라고 부르며, 두 번 이상 계산하는 부분 문제를 중복되는 부..

참고 : Do it! 자료구조와 함께 배우는 알고리즘 입문 (파이썬 편)☑️ C++로 이해하는 검색 알고리즘검색 알고리즘은 데이터 집합에서 특정 항목이나 값을 찾기 위해 사용하는 알고리즘이다. 모든 프로그래밍 분야에서 기본적이고 필수적인 알고리즘으로, C++에서는 find 함수를 통해서 검색 알고리즘을 제공하고 있다.  검색 알고리즘은 다양한 방법이 있는데 데이터 집합의 성격에 따라서 알고리즘을 선택하는 것이 중요하다. 1️⃣ 선형 검색 (Linear Search)가장 기본적인 알고리즘은 선형 검색이다. 선형 검색은 배열이나 리스트의 처음부터 끝까지 순차적으로 데이터를 검사하여 원하는 값을 찾는다. 구현이 간단하고 정렬되지 않은 데이터에서도 사용 가능하므로, 많은 분야에서 사용된다. 다만, 큰 데이터 집..