우선 순위 큐(Priority Queue)가장 우선 순위가 높은 원소가 가장 먼저 제거되는 큐연산과 성능연산설명시간 복잡도추가(Push)큐에 새로운 원소를 삽입하는 연산으로, 새로운 원소의 위치는 그 중요도에 따라서 결정된다.O(n)제거(Pop) 큐에서 가장 우선 순위가 높은 원소(가장 앞에 있는 원소)를 삭제한다.O(n)탑(Top)큐에서 가장 우선 순위가 높은 원소를 조회한다.O(1) 탑의 성능은 좋지만…추가와 제거의 성능을 향상시킬 수 있는 방법은? 힙(Heap)이진 트리를 기반으로 구현된 우선 순위 큐 — 완전 이진 트리최대 힙(Max heap): 모든 노드의 값 > 자식 노드의 값 — 큰 숫자가 우선최소 힙(Min heap): 모든 노드의 값 힙은 (1)포인터나 (2)배열을 기반으로 구현할 수 ..

배경: 이진 탐색과 이진 트리의 유사점↩️ 이진 탐색배열의 중앙값(mid)를 찾아 배열을 반으로 분할하는 과정을 재귀적으로 반복하며 key를 검색한다.예: search(6)[1, 3, 4, 5, 6, 7, 8, 9] → mid 3: arr[0-2], arr[4-7] ⇒ mid 6 → 왼쪽 탐색→ 왼쪽 배열은 원소가 하나 ⇒ mid 4: mid == 6 [검색 완료] 이진 탐색은 배열이 2개의 부분 배열로 재귀적으로 분할된다는 점에서 이진 트리와 유사성이 존재한다. 분할 구조 배열왼쪽 부분 배열중앙오른쪽 부분 배열이진 트리왼쪽 부분 트리부모 노드오른쪽 부분 트리재귀 구조배열 각 부분 배열이 또다시 분할이진 트리각 부분 트리가 또다시 분할이러한 이진 탐색 과정을 통해 만들어진 부분 배열 구조를 트리 형..

정렬은 자바 코드로 구현하면서 복습

지금까지 공부한 자료구조는 공통적으로 리스트형 자료 구조로, 선형 자료 구조였기 때문에 모든 원소는 인덱스에 대응된다.[prev] (i-1)번째 원소 → [curr] i번째 원소 → [next] (i+)번째 원소 개요선형 자료구조의 한계모든 원소들 사이에서 관계 비교가 가능하지만, 이 때 선후 관계는 a[i] 동일한 관계만 표현한다.8, 19, 23, 24, 48, 90 //오름차순으로 정렬된 리스트가가가, 라라라, 하하하 //사전순으로 정렬된 리스트 🤔 2개 이상의 관계를 표현할 수 있을까?가가가(엄마), 라라라(딸), 하하하(동생)//가가가 - 라라라: 모녀관계 //라라라 - 하하하: 자매관계위의 경우, 동일한 리스트에 있는 원소들이지만 원소들 사이의 관계가 ..

\(O(nlogn)\)정렬 알고리즘⚠️ 원소들 사이의 비교를 지양하자는 아이디어로부터 등장한 알고리즘이다.분할 정복 방식 (divide & conquer) 추구: 합병 정렬, 쾌속 정렬트리 구조 이용: 힙 정렬 분할 정복 방식➡️ 분할 정복의 3단계1. 분할(Divide): 주어진 집합의 데이터를 적절한 크기의 부분 집합으로 나누고,2. 정복(Conquer): 부분 집합에서 문제를 해결하여3. 결합(Combine): 해결된 부분 해를 합쳐서 ⇒ 주어진 집합의 해를 구한다.🚨 분할 정복 방식의 3가지 구성 요소1. 같은 형식으로 문제를 해결할 것2. 분할될 때마다 문제의 크기가 감소할 것3. 예외적인 경우를 처리할 것 1. 합병 정렬(Merge Sort)합병 정렬의 근거💡Q. 두 개의 정렬된 리스트를..

정렬지금까지 ‘정렬된 리스트’에서의 연산을 이야기해왔음그렇다면 정렬되지 않은 리스트의 경우에는 → 정렬이 필요하다💡 정렬(Sorting)데이터를 정해진 키에 따라서 크기 순으로 배열하는 것[예] 오름차순 (Ascending Order), 내림차순 (Descending Order)정렬 알고리즘의 성능정렬할 데이터의 개수가 n개 있다고 할 때, \(O(f(n))\) 으로 성능을 표시하게 되면:\(O(n^2)\) 정렬 알고리즘삽입 정렬: 원소의 이동 기반버블 정렬: 원소의 교환 기반선택 정렬: 원소의 교환 기반\(O(nlogn)\) 정렬 알고리즘합병 절렬쾌속 정렬 O(n^2) 정렬1. 삽입 정렬(Insertion Sort)추가(Insert) 연산에 기반한 정렬 알고리즘으로, 정렬되지 않은 리스트의 원소들을 ..

05-1. 스택과 연산스택스택에서는 원소를 도착한 시간의 반대 순서로 리스트에 저장한다. 이 때 리스트에서 원소의 추가/제거는 탑(top)이라고 불리는 한 끝에서만 발생하게 된다.Last-In First-Out (LIFO or FILO)원소 추가: `push`원소 제거: `pop`정의class Stack { int size; //스택에 저장할 수 있는 원소 개수 DataType *Items; //원소를 저장하는 리스트 int top; //top의 위치를 나타내는 값} 연산📌 특이점: 스택은 검색 연산이 허용되지 않는다.스택은 이 스택의 탑(top)에 해당하는 원소만 확인할 수 있기 때문이다. 탑 외에 스택 내부의 다른 원소를 확인하는 것은 허용되지 않는다. 생..

04-1. 연결 리스트 연결 리스트의 원소는 데이터(data)와 다음 원소의 위치에 대한 포인터(link)로 구성된 노드(node)로 지칭한다. 이 때 노드는 배열과 달리 메모리의 랜덤한 위치에 배치되며, 각 노드는 다음 노드를 가리키는 link를 포함한다. 배열연결 리스트메모리 공간연속된 메모리 주소이산된 메모리 주소(이점)공간 할당정적 할당 또는 동적 할당동적 할당접근 경로첫 번째 원소의 주소를 통해 접근첫 번째 원소의 주소를 통해 접근접근 방법인덱스 (`a[i]`)포인터 (`a` → link)접근 방식Random access(이점) 원소의 위치와 접근 시간 간 연관성 없음 (배열의 첫 번째 원소와 배열의 마지막 원소 각각에 대한 접근 시간은 같음)Sequential access 원소에 접근하는 시..

03-1. 리스트와 배열리스트는 가장 기초적이고 오랫동안 사용된 자료구조로, 가장 널리 사용되는 구현 방법으로 배열이 있다. 리스트원소를 한 줄로 나열한 구조유한한 원소들의 나열 — a finite sequence of elements각 원소들은 인덱스에 대응된다. ⇒ 그래서 `(인덱스, 원소)`의 쌍으로 나타낼 수 있다. 리스트 구현 방법배열(Array) - 인덱스 기반- 연속된 기억 공간에 원소를 저장한다. 따라서 인접한 원소는 인접한 주소에 저장한다.⇒ 그래서 배열은 메모리에 배열 크기보다 더 큰 연속된 공간이 있을 때만 사용할 수 있다.연결 리스트(Linked List) - 포인터 기반- 메모리에 배열 크기보다 더 큰 연속된 공간이 없을 때 사용한다.⇒ 그래서 어떤 원소를 저장할 때, 그 원소는 ..

02-1. 성능과 점근적 분석법성능(Performance)성능(Performance/Efficiency) = 결과(Solution) / 자원(Resource)동일한 결과라도 소요된 자원에 따라 효율에서 차이가 발생하게 된다. 자원복잡도의미장치시간시간복잡도 (time-complexity)수행 시간CPU공간공간복잡도 (space-complexity)메모리 사용량메모리실제 성능 논의에서는 공간보다 시간이 더 중요하다. (CPU가 더 비싸고 늘리기 어려움 ⇒ 성능에 보다 직접 영향)성능 측정 기준경우설명 최선빠를 때 기준과장: 1000번 테스트 하면 딱 1번평균보통의 상황 평균값과장: 반반 확률최악절대 보장되는 최악 기준보장: 사용자가 어떤 경우라도 기대한 시간보다 빠르므로 만족할 수 있음성능을 이야기할 때는 ..