시간복잡도

알고리즘에서 정렬이란?: 데이터를 특정한 기준에 따라 순서대로 정렬하는 것을 의미한다.  이진검색에서 빠른 알고리즘을 사용하기 위해서는 배열정렬이 필요하고, 다양한 정렬 알고리즘이 중요하다. ps에서는 어떤 정렬방식이 복잡도가 최소화되는지 생각하면서 접근해야 한다.  더보기💡 Tips 1. 정렬의 순서 관계를 정한다2. 첫 번째 조건부터 차례대로 , 같으면 다음 조건으로 넘긴다. 3. 마지막 조건을 바로 리턴한다.   우선, 최악의 경우 O(N^2) 시간복잡도를 깆는 삽입 정렬, 선택 정렬, 버블 정렬에 대해 알아보자 !  1. 삽입정렬 Insert sorting: 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교해 자신의 위치를 찾아 삽입한다. (오름차순)1. 두 번째 원소부..

숫자 카드 성공  시간 제한메모리 제한제출정답맞힌 사람정답 비율2 초256 MB118784503493690542.623%문제숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.입력첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이..

Heap  : 힙은 각 노드의 key값을 저장하고 다음의 특성들을 만족하는 이진트리이다.     Heap's Property   1. Heap-order(순서조건) : 루트를 제외한 모든 internal node에 대해  key(v) >= key(parent(v)) 만족 → sibling node끼리는 상관 없음! 이진'탐색'트리일 필요 없음    2. Complete Binary Tree(구조조건)  - 힙의 마지막 노드는 최대 깊이의 가장 오른쪽 노드이다. → 왼쪽 노드부터 삽입. 오른쪽 노드만 존재하는 노드가 있다면 해당 트리는 완전이진트리가 아님   Height of a Heap : n개의 key를 갖고 있는 힙은 height(O(logn)) 을 갖는다.   ※ 증명 heap 의 높이만큼의 수행횟..

Priority Queue 큐는 먼저 삽입되는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이다. : 우선순위 큐는, 삽입 순서가 아닌, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조로 구현 방식에 따라 running-time이 달라질 수 있다.     Sequeunce-based priority queue(시퀀스 기반 우선순위 큐)1. Selected List(선택정렬) O(n^2): 1.unsorted list와 함께 구현되는 우선순위 큐 방식→ 무순리스트S → 우선순위 큐 P- 우선순위 큐에서 삭제할 때 모든 원소를 비교- 우선순위 큐에 삽입 하는 데 n개의 원소 삽입하므로 O(n)-time- 정렬순서로 삭제하는 데 n + (n-1) + ```  + 1 s..

일반적인 이진탐색트리의 경우, O(log n)의 시간복잡도를 보장하지 않습니다. skewed tree는 검색, 삽입, 삭제 모든 연산에서 O(n)의 수행시간을 갖고, complete tree는 검색은 트리의 높이에 따라 수행시간이 빠를 수 있지만, 삽입과 삭제 연산에서는 트리의 모양을 유지해줘야 하기 때문에 O(n)의 시간복잡도를 가질 수밖에 없기 때문입니다.  이를 보안하기 위해 고안된 이진탐색트리가 바로 ! BST ( Balanced Search Tree) 인데요, 모든 연산에서 O(log n)의 수행복잡도를 갖는다는 것이 장점입니다.  이 글에서는 BST 중 AVL Tree에 대해 다뤄보도록 하겠습니다.   BST는 모든 노드의 좌우 서브트리 높이의 차가 0또는 1인 균형트리입니다. 대표적인 BST..