코드네임 :

들어가기전.. 알아두면 좋을 것 [ 이진트리 ] [ 레벨 순회 ] - 동일한 깊이를 가지는 노드를 좌측부터 차례로 방문 후, - 모두 순회한 경우 아래로 한단계씩 내려가는 방식 - FIFO (선입선출) 구조이므로 Queue 로 구현!! [ 우선 탐색 ] 너비 우선 탐색 - 인접한 노드를 우선 방문 - Level-order 레벨 순회 ⬆️ - Queue 를 이용하여 구현 깊이 우선 탐색 (DFS) - 갈 수 있는 가장 깊은 곳 까지 - 전위, 중위, 후위 순회 - 재귀 혹은 스택을 이용하여 구현 [ 서브트리 ] 자식을 새로운 루트 노드로 하는 또 다른 트리 (걍 내 자식의 트리) [ 전위 순회 / 중위 순회 / 후위순회 ]

우선 순위 큐 : 들어운 순서와 무관하게 우선순위가 높은 원소부터 나감 (일반 큐는 FIFO) 데이터 삽입의 경우 : 새로운 원소가 들어올 떄마다 append하면 되므로 O(1) 소요 데이터 삭제의 경우 : 우선 순위의 최댓값을 직접 찾아야 하므로, 순차 탐색 기준 최악의 경우 O(N) 소요 ㄴ 우선 순위에 따라 append 하더라도 그저 정렬된 배열이 될 뿐, 삽입할 때 또한 우선 순위 탐색에 O(N)의 시간이 걸리게 됨

완전 이진 트리 기반의 자료구조 (왼쪽부터 채워지는 트리) 최대 힙 (Max Heap) : 주어진 트리는 완전 이진 트리 : 모든 부모 노드는 자기 자식보다 큰 값 최소 힙 (Min Heap) : 주어진 트리는 완전 이진 트리 : 모든 부모 노드는 자기 자식보다 작은 값 Up-Heap : 새로운 원소 주가 - 힙은 완전 이진 트리 기반으로, 최초 삽입 위치는 고정되어있음 - 최대 힙의 원리를 깨지 않게끔 삽입된 노드를 움직임 Down-Heap : 루트 노드 제거 - 최하단 최우측 노드를 루트 노드로 대체 (완전 이진 트리의 규칙을 깨지 않기 위해) - 이후 위치 조정 [ Heap의 구현 ] Index를 이용 - 힙은 완전 이진 트리이므로 트리에 노드가 추가되더라도 기존의 노드 번호는 변하지 X - 동적배..

선형 자료구조 - Linked List, Stack, Queue 비선형 자료구조 - Tree, Graph [ Graph ] 연결되어 있는 대상(정점) 간의 관계를 표현하는 자료구조 - 정점(vertices)과 간선(edge)로 이루어짐 보행(Walk) 특정한 정점에서 다른 특정한 정점으로 갈때 거치는 정점과 간선의 나열 (그냥 모든 그래프) 닫힌 보행 (Closed Walk) : 시작 정점과 종료 정점이 동일한 walk A - B - C - D - E - C - B - A 열린 보행 (Open Walk) : 시작 정점과 종로 정점이 다른 walk A - B- C - D - E - D 경로 (Path) : 같은 정점 및 간선이 중복되지 않은 walk A - B - C - D - E 순환 (Cycle) 시작..

Deque ( Double ended queue ) - front와 rear (전단과 후단)에서 모두 삽입과 삭제 가능 - 스텍과 큐를 합친 형태의 자료구조

Queue is FIFO (선입선출)! (스택은 LIFO) enqueue(items) : 큐의 최하단에 append dequeue() : 맨 앞 원소를 끄집어냄 isEmpty(), isFull(), peek() 큐의 문제점 : 큐에서 원소를 제거할 때 최상단 데이터들을 제거하고 뒤쪽 남은 데이터들을 앞으로 밀어야함 -> 따라서 최악의 경우 O(n)의 시간복잡도를 가짐 ➡️ 해결책 : Circular Queue (원형 큐) rear는 enqueue를 front는 dequeue를 따라감 원형 큐에서 dequeue를 하면 데이터를 앞쪽으로 미는 대신 None의 값과 바꿔치기 한다네요 (Cirqueue는 코드 너무 길어서 깃허브 코드로 볼것!!!) https://github.com/codenameVien/Dat..

[ Stack ] LIFO!!!!!!! (후입선출) 재귀적 순회 : 내가 나를 부른다! ( 함수의 정의부에서 자기 자신을 재귀적으로 호출할 수 있음 ) stack = list() : 비어있는 리스트를 생성함으로써 빈 스택 생성 push() : stack.append() - 리스트의 맨끝에 원소 삽입 pop() : 가장 마지막에 삽입된 원소 삭제하며 반환 peek() : stack[-1] , 스택의 맨 뒤에 있는 항목을 삭제하지 않고 반환 { 스텍 응용 } 괄호검가.. 여는 괄호 is push, 닫는 괄호 is pop 괄호 조건 1. 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 같아야 함 2. 같은 타입의 괄호에서 왼쪽 괄호가 오른쪽 괄호보다 먼저 나와야 함 3. 서로 다른 타입의 괄호 쌍이 서로를 교차하면 ..

아이패드로 필기하면 걍 휘갈기고 낙서하길래 모든 과목을 맥북 필기로 하기류햇다 [ 빅오 표기법 ] (21p~22p) ⭐️ 증가폭이 크다 = 시간복잡도가 크다 = 효율성이 낮다 ⭐️ { 빅오 표기 찾는 간단한 방법 } - n이 한없이 커질때 - 최고차항만을 선택 -> 그 항의 계수 제거 -> 그게 g(n)이야 e.g. 복잡도 함수 O(n) = 2n^2 + 3n +5 -> 최고차항 is 2n^2 -> 계수제거시 n^2 -> 따라서 g(n) = n^2 { 증가폭을 찾을 때 n에 숫자 대입하는 거 생각할 시에 뭐가 가장 중요할까요? } - n이 엄~~청 클 때가 중요하다!!!! -n이 1,2 처럼 작을 때는 필요없긔요 [ 빅오메가 표기법 ] [빅세타표기법] 알고리즘분석 하는 경우 : 최악의 경우(worst ca..