목록Computer Science/알고리즘 (10)
DNF LOVE
https://dnf-lover.tistory.com/2 이전에 우리는 '시간복잡도'의 개념에 대해 배웠다.그렇다면 이 시간복잡도 즉, 연산량을 줄이는 방법은 무엇이 있을까? 1. 시간 복잡도의 한계실제 연산량을 계산할 때, 함수의 계수와 낮은 랭크의 항을 무시하게 되기 때문에 실제 연산량과 시간 복잡도를 통해 계산한 연산량의 차이가 클 수 있다. 또, 함수들은 값의 범위에 따라 대소 관계가 다르다는 점때문에 낮은 랭크의 시간 복잡도가 항상 높은 랭크의 시간 복잡도보다 적은 연산량을 보장하지 않는다.위의 그래프를 보면, 길게 보았을 때에는 제곱근들에 비해 Y = X가 더 퍼포먼스가 좋지만, X축이 1이하일 때 퍼포먼스는 y = X 보다 y = X^2 혹은 X^3의 퍼포먼스가 더 좋다는 것을 확인할 수 있..
[Dynamic Programming] * 정의 : 특정 범위까지의 값을 구하기 위해서 그것과 다른 번위까지의 값을 이용하여 효율적으로값을 구하는 알고리즘 설계기법이다. 큰 문제를 작은 문제로 나눠서 푸는 알고리즘이다. 한글로 풀어 쓰면 ‘동적 계획법’이고, 약어는 DP라 한다 [DP의 특징] - Optimal~ 에 의하여 같은 문제는 구할 때마다 정답이 같아지기에 정답을 한 번 구하면 정답을 어딘가에 메모해둔다.(Memorization) 코드에선 자료구조에 저장한다. - 각 문제는 한 번만 풀어야 한다. [DP의 두 속성] 1. Overlapping Subproblem : 겹치는 부분문제. 문제를 작은 문제로 쪼갤 수 있다. 2. Optimal Substructure : 문제의 정답을 작은 문제의 부분..
4. 정렬 알고리즘(Sorting Algorithm)의 모든 것 - 힙 정렬(Heap Sort) : 힙 정렬이란, 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최대 힙을 구성하고, 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다. ** 잠깐의 자료구조 지식, Heap이란? -> 힙이란, 최소값이나 최대값을 빠르게 찾아내기 위해(우선순위 큐) 완전 이진 트리를 기반으로 하는 트리 구조를 갖는 자료구조이다. >1. n개의 노드에 대한 완전 이진 트리를 구성한다. 이때 루트 노드부터 부모 노드, 왼쪽 자식 노드, 오른쪽 자식 노드 순으로 구성한다.2. 최대 힙을 구성한다. 최대 힙이란 부노드가 자식 노드보다 큰 트리를 말하는데, 단말 노드를 자식 노드로 가진 부모..