본 문서는 어서와! 자료구조와 알고리즘은 처음이지? 강의를 보고 제 주관대로 정리한 글입니다. 힙 (Heap) 이진 트리의 한 종류 루트(Root) 노드가 언제나 최댓값 또는 최솟값을 가짐 최대 힙(Max Heap), 최소 힙(Min Heap) 완전 이진 트리여야 함 이진 탐색 트리와의 비교 원소들은 완전히 크기 순으로 정렬되어 있는가? 이진 탐색 트리는 그렇지만 힙은 아님 특정 키 값을 가지는 원소를 빠르게 검색할 수 있는가? 이진 탐색 트리에서는 가능하지만 힙은 아님 부가의 제약 조건은 어떤 것인가? 힙은 완전 이진 트리여야 함 최대 힙(Max Heap) 재귀적으로 정의할 수 있음 어느 노드를 루트로 하는 서브트리도 모두 최대 힙 연산의 정의 __init__() - 빈 최대 힙을 생성 insert(i..

본 문서는 어서와! 자료구조와 알고리즘은 처음이지? 강의를 보고 제 주관대로 정리한 글입니다. 트리 (Tree) 정점(Node)과 간선(Edge)을 이용해서 데이터의 배치 형태를 추상화한 자료 구조 트리 용어 제일 위가 루트 (Root) 노드 제일 아래가 리프 (Leaf) 노드 루트도 리프도 아닌 내부 (Internal) 노드 바로 위는 부모 (Parent) 노드 바로 아래는 자식 (Child) 노드 같은 부모를 두면 형제 (Sibling) 노드 부모와 그 부모 노드들은 조상 (Ancestor) 노드 자식과 그 자식 노드들은 후손 (Descendant) 노드 수준 (Level) 루트 노드의 Level은 0 또는 1부터 시작할 수 있는데 여기서는 0부터 시작함 루트 노드의 Level이 0, 아래로 내려갈 ..

본 문서는 어서와! 자료구조와 알고리즘은 처음이지? 강의를 보고 제 주관대로 정리한 글입니다. 큐 (Queue) 자료를 보관할 수 있는 선형 구조 넣을 때는 한쪽 끝에서 밀어 넣어야 하고 -> Enqueue 연산 꺼낼 때는 반대쪽에서 뽑아 꺼내야 한다 -> Dequeue 연산 선입선출 (FIFO - First In, First Out) e.g., 경기장 입장을 기다리는 대기열 큐의 구현 연산의 정의 size() - 현재 큐에 들어 있는 데이터 원소의 수를 구함 isEmpty() - 현재 큐가 비어 있는지를 판단 enqueue(x) - 데이터 원소 x를 큐에 추가 dequeue() - 큐의 맨 앞에 저장된 데이터 원소를 제거 및 반환 peek() - 큐의 맨 앞에 저장된 데이터 원소를 반환 (제거하지 않음..

본 문서는 어서와! 자료구조와 알고리즘은 처음이지? 강의를 보고 제 주관대로 정리한 글입니다. 스택 (Stack) 자료를 보관할 수 있는 선형 구조 넣을 때는 한쪽 끝에서 밀어 넣어야 하고 - Push 연산 꺼낼 때는 같은 쪽에서 뽑아 꺼내야 한다 - Pop 연산 후입선출 (LIFO - Last In, First Out) 스택에서 발생할 수 있는 오류 비어있는 스택에서 데이터를 꺼내려고 할 때 - 스택 언더플로우 (Stack Underflow) 꽉 찬 스택에 데이터를 넣으려 할 때 - 스택 오버플로우 (Stack Overflow) 스택의 구현 연산의 정의 size() - 현재 스택에 들어있는 데이터 원소의 수를 구함 isEmpty() - 현재 스택이 비어 있는지 판단 push(x) - 데이터 원소 x를 ..

본 문서는 어서와! 자료구조와 알고리즘은 처음이지? 강의를 보고 제 주관대로 정리한 글입니다. 추상 자료형 (Abstract Data Type) Data e.g., 정수, 문자열, 레코드 등 Operations 삽입, 삭제, 순회 등 정렬, 탐색 등 단일 연결 리스트 (Singly Linked List) Node Data e.g., 문자열, 레코드, 또 다른 연결 리스트 등 Link (next) class Node: def __init__(self, item): self.data = item self.next = None SinglyLinkedList Properties 첫 노드를 가리키는 head 마지막 노드를 가리키는 tail 총 노드의 수 예시에서 첫 인덱스는 0이 아닌 1 class SinglyL..

본 문서는 어서와! 자료구조와 알고리즘은 처음이지? 강의를 보고 제 주관대로 정리한 글입니다. 재귀 함수 (Recursive Function) 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것 종결 조건이 매우 중요 1부터 n까지 모든 자연수의 합 구하기 예제 def recursive_sum(n): if n = 0: result += n n -= 1 return result Recursive Iterative O(n) O(n) 직관적이지만 함수 호출과 같은 추가 비용이 들기 때문에 비효율적임 재귀함수에 비해 효율적임 팩토리얼 예시 def factorial(n): if n

본 문서는 어서와! 자료구조와 알고리즘은 처음이지? 강의를 보고 제 주관대로 정리한 글입니다. 선형 배열 (Linear Array) 같은 종류의 데이터 줄지어 늘어놓은 것 각각의 원소는 인덱스라는 번호가 있는데, 일반적으로 0부터 시작함 파이썬에서는 리스트(list)라는 데이터 타입으로 배열 사용 일반적인 배열보다 여러 추가 기능이 있음 일반적인 배열과 달리 여러 데이터 타입 사용 가능 파이썬 리스트의 연산들 리스트의 길이와 무관하게 상수 시간 O(1)에 실행할 수 있는 연산 원소 덧붙이기 .append() 끝에서 꺼내기 .pop() 리스트 길이에 비례하는 선형 시간 O(n)이 걸리는 연산 원소 삽입하기 .insert() 원소 삭제하기 .del() 원소 탐색하기 .index() 정렬 sorted() 파이..