하수하따 록기장

📍 힙 정렬 (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)..

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..

📍알고리즘 분류: DFS, BFSDFS란 Depth First Search, 깊이 우선 탐색. 트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식이다. 재귀호출이나 스택 배열로 구현할 수 있다.📍문제풀이: 재귀호출 방식의 DFS로 문제를 풀었다. dfs가 처음 호출되면 인접한 집들을 다 탐색하여 한 단지를 구성하는 집의 개수를 모두 센다.📍코드#include #include #include #include using namespace std;#define MAX_N 26int map[MAX_N][MAX_N];bool visited[MAX_N][MAX_N];int dx[4] = {-1,1,0,0};int dy[4] = {0,0..

https://www.acmicpc.net/problem/2309📍  풀이 방법: 합이 100이 되는 7명의 난쟁이를 구하는 것이 아니라, 9명의 난쟁이 키 합에서 뺐을 때 100이 되는 2명의 난쟁이를 구하면 된다. 📍 알고리즘 분류: 브루트포스brute force(무식한 힘). 즉 무식하게 가능한 경우의 수를 모두 탐색해보는 완전탐색 알고리즘.📍  소스코드#include #include using namespace std;int main() { int dwarf[9]; int sum = 0; for(int i=0;i> dwarf[i]; sum += dwarf[i]; } sort(dwarf,dwarf+9); for(int i=0;i 처음에 break문으..

이산수학 보강 수업에서 유클리드 알고리즘에 대해 배웠다. 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)이므로..