하수하따 록기장

더보기목차1. Greedy 알고리즘이란2. MST란3. Kruskal 알고리즘- 이론, 구현4. Prim 알고리즘- 이론, 구현1. Greedy 알고리즘이란Greedy 알고리즘이란 욕심장이 기법으로 당장 이 순간에서 최적이 되는 해를 구하는 것에, 즉 현재에 집중하는 알고리즘입니다. 과거와 미래는 전혀 신경쓰지 않습니다. Greedy 알고리즘의 핵심 단계는 다음과 같습니다.  1) Selection Procedure (선택)현재를 기준으로 가장 최적이 되는 해를 선택하는 단계입니다. 최적 해를 선택하여 집합에 추가합니다. 이 과정을 위해 선행되는 핵심은 어떤 값을 먼저 볼 것인지에 대한 우선순위 결정입니다. 2) Feasibility Check (유효성 검사)앞에서 선택한 해를 포함한 집합이 문제를 해결..

📍 힙 정렬 (Heap Sort)힙 소트는 힙 구조를 이용해 정렬하는 알고리즘이다.힙 구조란 완전 이진 트리의 일종인 자료구조로 MaxHeap과 MinHeap이 있다. MaxHeap은 루트노드가 가진 값은 자식 노드가 가진 값보다 크거나 같다. MinHeap은 반대로 루트노드가 자식노드보다 작거나 같다. 힙 소트에서는 MaxHeap을 사용한다.1) 정렬되지 않은 배열을 힙 구조로 바꾼다. (construct heap)2) 최상위 루트 노드를 뽑아 가장 마지막 원소와 교체한다. (extract)3) 루트노드부터 마지막 원소 전까지 heap구조로 만든다. (heapify / fixheap)4) 2)로 돌아가 모든 노드를 추출할 때까지 반복한다. 📍 C++ 구현 코드class Solution {public..

📍 퀵 정렬 (Quick Sort)퀵 정렬은 빠르다고 해서 퀵 정렬이다. 먼저 퀵 소트의 기본 흐름은 아래와 같다.1) 가장 왼쪽 원소를 pivot으로 선정 (pivot 선정 방식은 바꿀 수 있음)2) 배열 내 원소들을 pivot보다 작은 것 / pivot보다 큰 것 이렇게 두 개로 분류3) 각각의 배열 내에서 다시 1)부터 반복 (recursive) 📍 C++ 구현 코드퀵소트를 구현하는 방식에는 Romuto의 방식, Hoare의 방식 두 개가 있다. 각 방식의 코드가 아래에 순서대로 있다. // Romutoclass Solution {public: void quicksort(vector& nums, int start, int end){ if(start sortArray(vector..

📍 합병정렬 (Merge Sort)합병 정렬은 Divide & Conquer (분할정복) 방식을 기반으로 한 정렬이다. 배열을 쪼개고 쪼갠 뒤 합치는(merge) 과정에서 정렬이 된다. 그래서 Merge Sort이다. 📍 C++ 구현 코드class Solution {public: void merge(vector& nums, int start, int mid, int end){ int n = nums.size(); vector tmp(n+1); for(int i=0;i& nums, int start, int end){ if(start sortArray(vector& nums) { mergesort(nums,0,nums.size()-1)..

📍 버블정렬 (Bubble Sort) 🫧버블 정렬은 정렬되는 모습이 버블버블하다.앞에서부터 계속 바로 이웃한 원소와 스왑스왑스왑스왑해서 맨 뒤에 가장 큰 원소를 넣어둔다. 그 다음엔 다시 처음부터 스왑스왑스왑스왑해서 n-2에도 가장 큰 원소를 넣는다. 계속 이웃한 원소에서 swap을 진행하면서 나아가기 때문에 전반적으로 앞에서부터 뒤까지 정렬이 조금씩 조금씩 진행되고, 정확한 정렬은 맨 뒤에서부터 하나씩 진행된다. 전반적으로 정렬이 되기 때문에 버블버블하게 거품이 올라오는 듯하다. 📍 C++ 구현 코드class Solution {public: vector sortArray(vector& nums) { int n = nums.size(); for(int i=n-2;i>=..

📍 선택정렬 (Selection Sort)가장 작은 값을 찾아 선택한다. 정렬되지 않은 배열의 첫 번째 원소부터 현재 원소이고, 그 뒤의 모든 원소를 비교해가며 가장 작은 원소를 찾는다. 가장 작은 원소를 현재 원소와 교체한다. 그러면 점점 앞에서부터(가장 작은 수부터) 순서대로 정렬되어간다.우리가 실제로 실물 카드를 정렬한다고 했을 때, 선택정렬을 사용할 사람은 없을 것 같다. 가장 작은 수를 찾아서 앞에다가 놓아가며 정렬하는 원리이지만 가장 작은 수를 맨 첫 번째 원소와 교체하기 때문이다. 우리가 실물 카드를 가지고 있다면 교체가 아니라 그냥 작은 수를 앞에다가 놓았을 것이다. 하지만 프로그램으로 구현하려면 원소의 자리를 채워주기 위해 교체가 필요했다. 실제 세상에서 사용되지는 않지만 프로그램으로 ..

📍 삽입 정렬 (Insertion Sort)삽입 정렬은 실제로 내가 카드를 가지고 있다고 생각하면 더 이해가 쉬운 것 같다. 정렬되지 않고 나열된 카드 중 두 번째 카드를 들어 손에 쥔다. 그러면 내가 두 번째 카드를 들고 있으므로 두 번째 칸이 빌 것이다. 바로 앞의 카드와 비교하여 내가 들고 있는 카드보다 크다면 앞 카드를 한 칸 뒤로 민다. 해당 카드 바로 뒤는 비어있다. 카드를 밀어서 빈 공간을 채워주면 된다. 이를 반복하다가 내가 들고 있는 카드보다 큰 카드가 나오면 지금 빈 공간에 내가 들고 있는 카드를 내려놓는다.우리가 실제로 숫자카드를 가지고 정렬하고자 할 때 사용하곤 하는 직관적인 방법이라고 생각할 수 있다. 📍 C++ 구현 코드class Solution {public: vect..

Maximum Contiguous Subsequence Sumn개의 정수 a1, a2, ..., an이 주어졌을 때 연속적인 부분수열의 합이 최대가 되는 구간의 합을 계산하시오.리트코드 사이트의 문항을 이용해 코드로 연습해보았다.https://leetcode.com/problems/maximum-subarray/📍 [방법1] Brute-force가능한 모든 부분 수열에 대해서 계산을 하고 이 중 가장 큰 합을 찾는다. index i는 부분 수열의 시작 인덱스를, j는 마지막 인덱스를 의미한다. 단순하지만 O(n^3)만큼의 시간복잡도를 가진다. 매우 효율적이지 않다.class Solution {public: int maxSubArray(vector& nums) { int n = nums..

이산수학 보강 수업에서 유클리드 알고리즘에 대해 배웠다. 1학년 때부터 계속 배웠던건데 이번으로 3번째 정도 들으니까 좀 알겠더라.. 유클리드 알고리즘(유클리드 호제법)이란 2개의 자연수의 최대공약수를 쉽게 알아낼 수 있는 알고리즘이다. 최대공약수란 두 정수를 나누어 떨어지게 하는 수 중 가장 큰 정수를 의미한다. 두 정수 A, B의 최대공약수 k를 구해보자 (A > B) A = B * q + r 이라고 할 수 있다. (q는 몫, r은 나머지) A와 B의 최대 공약수는 k이므로 A = k·A', B = k·B' 라고 하자. (A'과 B'은 서로소) 그러면 k·A' = ( k·B') * q + r 이다. 이때, r = k·A' - ( k·B') * q 라고 쓸 수 있다. r = k(A' - B'·q)이므로..