key를 가지고 탐색을 진행, 동일한 key를 가지는 원소가 있을 수 있음. => 중복 가능 List - Based Dict log file / audit trail : unsorted sequence insert : O(1) find && erase : O(n) log file -> insert는 빠르지만, 나머지 탐색, 삭제는 느림 Search Table search table == lookup table, table = 배열 / sorted array 정렬된 배열 -> 이진 탐색 떠올리기 이진 탐색 -> sorted array떠올리기 find : O(log(n)), 이진 탐색을 이용 insert : O(n), 원소 재배치 remove : O(n), 원소 재배치 search table은 size가 작..
분류 전체보기
Binary Search Tree 아래 그림과 같이 한 쪽으로 편향될 수 있다. 그렇기에 insert, delete, find 함수의 시간 복잡도는 최악의 경우 O(n), 가장 효율적으로는 O(log(n))이 된다. 즉, 높이 h에 따른다는 것을 알 수 있다. Insert root부터 해당 value 값보다 작으면 left, 크면 right로 내려가 NULL이 아닐때 까지 탐색 Delete 1. child 중 NULL이 있는 경우 -> external이 아닌 노드를 그대로 이어 붙이면 해결된다. 아래 그림은 child에 NULL이 있는 경우인 빨간색 노드를 삭제하는 경우이다. 2. 하지만 만약 child 모두 internal 이라면, 얘기가 달라진다. 아래 그림은 internal node인 빨간색을 삭제..
key, value 두 가지 entry로 구성 key값이 작을수록 우선순위가 높다 -> min_priority_queue key값이 클 수록 우선순위가 높다 -> max_priority_queue PQ sorting unsorted list - selection sort sorted list - insertion sort heap sort Unsorted List - Selection Sort 원소를 주어지는 순서대로 삽입 -> O(1) 삽입된 원소를 하나하나 비교해가며 찾아서 반환 -> O(n) 그러므로 n개의 원소 삽입 -> O(n) 최솟값 / 최댓값을 찾아 반환 -> O(n^2) => worst-case 가 곧 average-case Sorted List - Insertion Sort -> 사이즈가..
이진트리란 자식 노드의 수가 0 ~ 2개인 트리를 말한다. 이를 재귀적으로 표현할 수 있는데, 단일 노드이거나 해당 노드의 자식 노드가 모두 이진 트리라면 해당 노드를 이진트리라고 부른다. 완전이진트리란 이진트리를 채워나갈 때 마지막 노드가 왼쪽부터 차례대로 채워진 트리의 형태이다. 위 그림에서 볼 수 있듯이, internal 노드의 수는 3, external 노드의 수는 3, 높이 h는 2이다. external 노드가 왼쪽부터 차례대로 채워졌으므로 위의 트리는 완전이진트리가 된다. 만약 왼쪽부터 채우다가 오른쪽 끝까지, 즉 external 노드의 수가 2^h개라면 이를 포화이진트리라고 부른다. internal 노드의 수는 3, external 노드의 수는 4, 높이 h는 2이다. external 노드가..
https://www.acmicpc.net/problem/27728 27728번: 개구리와 쿼리 $N \times N$ 크기의 $2$차원 배열로 이루어진 연못에 $Q$마리의 개구리들이 모여있다. 각 개구리들은 초기 위치 $\left(S_{x},S_{y}\right)$에서 배열의 오른쪽 끝$\left(X,N+1\right)$에 있는 육지에 도착해야 한 www.acmicpc.net 문제는 누가봐도 dp + 누적 합으로 해결하는 문제이다. 나도 처음에는 간단하다고 생각했는데, 막상 머릿속으로 시간을 계산해보니까 x좌표 N개, y좌표 N개, 개구리 Q마리 ->O(N^2*Q)가 걸렸다. 이는 당연히 시간초과이고, 시간을 줄일 방법을 찾아야했다. 먼저 dp[i][j]에 dp[i][n]까지 가기 위해 남은 시간을 저..
