우선순위 큐 힙의 응용분야로 우선순위의 개념을 큐에 도입한 자료 구조로 데이터들이 우선순위를 가지고 있고, 우선순위가 높은 데이터가 먼저 나간다. 배열, 연결리스트, 힙으로 구현가능하며 이중에서 힙이 삽입/삭제시 O(logN)으로 가장 효율적이다. 운영 체제에서의 작업 스케쥴링등에 사용된다. 최대 우선순위 큐 최소 우선순위 큐는 최대 우선순위 큐의 반대이다. 두 가지 연산을 만족한다. Insert(x) :...

힙(heap) Complete Binary Tree의 일종이면서 Heap의 특성을 만족해야한다. Max Heap Property : 부모는 자식보다 크거나 같다. Min Heap Property : 부모는 자식보다 작거나 같다. 우선순위 큐에서 사용되는 자료구조이다. 여러 개의 값들 중에서 최대값이나 최소값을 빠르게 찾아내도록 만들어진 자료구조이다. 힙 트리는 중복된 값을 허용한다. 힙은 느슨한 정렬 상태를 유지한다. 큰 값이...

수학 알고리즘 문제 풀이에 많이 등장하는 수학 문제들과 유용하게 사용할 수 있는 몇 가지 수학들입니다. 확률 AnB의 확률 A에 속해있으면서도 B에 속해 있을 확률 P(AnB) = P(B|A)P(A) 예) 1~10까지의 수 중 5이하 이면서, 짝수일 확률 5이하일 확률 = 50%, 5이하 숫자 중 짝수일 확률 = 40% 1/2 * 2/5 =...

비트 연산자 NOT NOT 연산은 각 자릿수의 값을 반대로 바꾸는 연산이다. NOT 0111 = 1000 x = ~y; OR OR 연산은 두 값의 각 자릿수를 비교해, 둘 중 하나라도 1이 있다면 1을, 아니면 0을 계산한다. 0101 OR 0011 = 0111 x = y | z; XOR XOR 연산은 두 값의...

Big-O 알고리즘의 효율성을 나타내는 지표로 알고리즘이 빨라젔는지, 메모리를 많이 잡아먹지는 않는지 알고리즘의 성능을 판단할 때 사용합니다. 시간에 대한 개념인 시간복잡도와 공간에 대한 개념인 공간복잡도가 있습니다. 시간 복잡도 Big-O에 대한 시간 개념으로 알고리즘의 수행시간이 얼마인지 나타냅니다. 수행되는 연산의 수를 가지고 계산하며 알고리즘에서 중요하지 않은 부분은 최대한 무시합니다. 알고리즘 계산에 속하는 연산...