Algorithm/개념 (Concept)4 <Algorithm,C++> Merge Sort (병합 정렬, 합병 정렬) 개념, 구현예제 Merge Sort 는 유명한 정렬 알고리즘 중에 하나입니다. 최악의 시간복잡도가 O(n log n)라는 점 때문에 실제 알고리즘 문제에서도 많이 사용됩니다. stable sort(안정 정렬, 같은 우선순위의 값에 대해 정렬 전후 순서 동일) , 메모리가 2배로 든다는 점이 특징입니다. 다른 개념적인 설명은 뒤로하고 여기선 오로지 외워서 사용하기 편한 방법을 하나 소개합니다. 톱다운으로 구현한 방법입니다. #include #define MAX 10 int tmp[MAX]; using namespace std; void mergeSort(int arr[], int s, int e) { //base condition if (s >= e) return; //divide int m = (s + e) / 2; /.. 2021. 2. 16. 최소 신장 트리 (MST , Minium Spanning Tree) 최소 신장 트리(MST, Minium Spanning Tree) 신장 트리 중에서 간선의 가중치의 합이 최소인 것 신장 트리(Spanning Tree) 그래프 내의 모든 정점을 연결한 트리 신장 트리의 특징 모든 노드는 서로 연결되어 있다. 간선(edge)의 수 E는 노드의 수 V에서 1을 뺀 것과 같다. 트리(Tree) 그래프의 일종으로 사이클이 없는 연결그래프이다. 트리의 특징 root node를 제외한 모든 node는 단 하나의 부모 node만 가진다. 임의의 노드에서 다른 노드로 가는 경로는 유일하다. 회로(cycle)가 존재하지 않는다. 간선(edge)를 하나 자르면 트리가 두 개로 분리된다. 최소 신장 트리 구현 방법 Kruskal 알고리즘 탐욕적인 방법(greedy method)을 이용해 M.. 2020. 5. 25. 빅-오 표기법 (Big-Oh Natation), 시간 복잡도(Time Complexity) 시간 복잡도란?문제를 해결하는데 걸리는 시간과 입력의 함수 관계해당 알고리즘이 얼마나 효율적인지 정량화해 나타내는 지표빅-오 표기법이란?입력값에 따른 알고리즘의 실행 시간 성장률(시간 복잡도)을 점근적 상한선으로 나타낸 수학적 표기법 해당 알고리즘의 성능을 나타내기 위해선 입력값의 크기에 따른 알고리즘의 실행 시간을 알아야 합니다.입력값의 크기에 따라 이 함수가 얼마나 빨리 커지는지 알아볼 필요성이 있습니다. 이것을 실행 시간의 성장률(rate of growth)이라 합니다.성장률에서 상수 계수와 중요하지 않은 항목을 제거한 것을 점근적 표기법(asymptotic notation)이라 합니다.big-Θ중요한 것은 선형 검색의 최악의 경우의 실행 시간은 배열 크기인 n에 따라 커진다는 것입니다. 여기서 실.. 2020. 5. 14. [C++,DP] 백준 1463번 1로 만들기 문제풀이, DP와 분할정복의 특징 문제링크 백준 1463번 1로 만들기 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 다시 복습하는 DP문제이다. 다시 DP 개념부터 집고 넘어가야겠다. DP(Dynanic Programing)란? 주어진 문제를 여러 개의 부분 문제들로 나누어 푼 다음, 그 결과들로 큰 문제를 푸는 방법을 말하며 여기서 DP의 Dynanic은 개발자가 아무 의미없이 붙인 거라고 한다... 큰 문제를 해결하기 쉽게 여러 개의 쉬운 부분 문제들을 풀어 해결하는 방법 정도로만 이해하면 될 것 같다. 분할정복이랑 비슷한 개념이기는 하나 분할정복은 문제를 분할했을 때 겹치는 문제가 발생하지 않지만, DP는 겹치는 문제가 발생하기 때문에 메모이제이션.. 2019. 2. 26. 이전 1 다음
