데굴데굴

공부자료: 신찬수 교수님 '자료구조' 재생목록 자료구조 - 트리구조 소개 - YouTube 자료구조 - 힙 (heap) 정의 - YouTube 자료구조 힙 (heap) make_heap 연산 - YouTube 자료구조 힙 (heap) - insert와 delete_max 연산 - YouTube *별도로 출처가 표기되지 않은 이미지는 직접 제작한 것 트리(tree): 부모-자식 관계를 계층적으로 표현한 자료구조 이진트리(binary tree): 부모 노드에 자식 노드가 최대 2개까지만 존재하는 자료구조, 두 개 이상의 노드가 올 수도 있지만 이진트리가 가장 많이 쓰임. 힙(heap): 특정 조건을 만족하는 이진트리 Tree Data Structures by C.Barkin Ozer | Medium 노드와 ..

공부자료: 신찬수 교수님 유튜브 '자료구조' 재생목록 자료구조 연결리스트 소개 - YouTube 자료구조 한방향연결리스트 - 삽입, 삭제 연산 - YouTube 자료구조 한방향연결리스트 - 탐색 연산 - YouTube 배열과는 달리 메모리상에서 흩어져 있음. 실제 데이터값(key)과 값이 저장된 곳의 주소(link)로 구성된 쌍(key, link), 즉 하나의 노드 node를 갖고 있어야 함. 가장 앞에 있는 노드는 헤드노드 head node 배열은 인덱스가 주어지면 상수시간 O(1) 내에 인덱스에 있는 값을 바로 알 수 있다는 것이 장점 연결리스트는 그렇지 않음. 하지만 배열은 값을 삽입하거나 삭제할 때 나머지 값에서 인덱스의 이동이 발생함. 최악의 경우에는 O(n)이 듦. 연결리스트에서는 link만 ..

디큐 Dequeue / deque dequeue는 Stack과 Queue를 합친 자료구조로, 왼쪽과 오른쪽에서의 삽입과 삭제가 모두 가능하다. 파이썬에는 collections 모듈에 deque 클래스로 구현되어 있다. from collections import deque 오른쪽에 값 넣을 때 = append / 왼쪽에 값 넣을 때 = appendleft 가장 오른쪽 값을 삭제할 때 = pop / 가장 왼쪽 값 삭제할 때 = popleft 디큐 활용 예: Palindrome 문자열 s와 s를 거꾸로 뒤집은 문자열이 서로 같다면 Palindrome ex) 기러기, salsa, 다시합창합시다 (디큐를 쓰지 않고도 Palindrome 판별 코드를 작성할 수 있음.) 디큐를 쓰지 않은 코드 s = input('단..

공부자료: 신찬수 교수님 유튜브 '자료구조' 재생목록 https://www.youtube.com/watch?v=nqCNk_DmPio&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=11 앞서 배운 스택이 후입선출의 구조였다면, 큐는 선입선출(First-in First-Out)의 구조이다. 먼저 들어온 것이 먼저 나간다. 그래서 선착순 자료구조라고도 한다. 파이썬 리스트로 큐 구현하기 1 enqueue(value): 큐의 가장 오른쪽 끝에 값을 삽입 dequeue(): 큐의 가장 왼쪽 값을 삭제 후 리턴 front(): 큐의 가장 왼쪽 값을 리턴 len(): 큐의 저장된 값의 개수 isEmpty(): 큐가 비었는지 알려줌 class Queue: def __init__(se..

* Stack 클래스를 정의하여 코드를 작성했다. 입력 1 2 3 + 4 / + 출력 2.2500 Stack 클래스 정의 push(value): 스택에 값을 넣음 pop(): 스택의 가장 위에 있는 값을 삭제 후 리턴, 스택이 비어있으면 "Stack is empty"를 출력 top(): 스택의 가장 위에 있는 값을 리턴, pop()과 마찬가지로 스택이 비어있으면 "Stack is empty"를 출력 __len__(): 스택의 길이 출력 isEmpty(): 스택이 비어있는지 아닌지 판단 class Stack: def __init__(self): self.items = [] def push(self, val): self.items.append(val) def pop(self): try: return self..

* class로 Stack을 정의한 후 코드를 작성했다. * 수식에는 이항연산자만 사용한다고 가정한다. 어설프지만 infix와 postfix 그리고 스택은 아래 링크에 정리해두었다. 순차적 자료구조 & 스택 (stack) 순차적 자료구조 (Sequential data structures) 1. 배열, 리스트 - index로 임의의 원소에 접근 - 연산자 [ ] - 삽입 (append, insert) - 삭제 (pop, remove) 2. stack, queue, dequeue - 제한된 접근(삽입, 삭제).. haruisshort.tistory.com 입력 1 + ( 2 + 3 ) / 4 출력 1 2 3 + 4 / + Stack 클래스 정의 push(value): 스택에 값을 넣음 pop(): 스택의 가..

공부자료: 신찬수 교수님 유튜브 '자료구조' 재생목록 https://www.youtube.com/watch?v=OzFXiukhv8o&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=8 순차적 자료구조 (Sequential data structures) 1. 배열, 리스트 - index로 임의의 원소에 접근 - 연산자 [ ] - 삽입 (append, insert) - 삭제 (pop, remove) 2. stack, queue, dequeue - 제한된 접근(삽입, 삭제)만 허용 - 실제로 이런 자료구조가 많이 쓰임. stack : LIFO (Last In First Out) 밑에서부터 차곡차곡. push. 중간 삽입 불가. queue : FIFO (FIrst In Firs..

공부자료: 신찬수 교수님 유튜브 '자료구조' 재생목록 https://www.youtube.com/watch?v=Lqd8o7vL2Z8&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=6 배열 (array) vs. 리스트(list) 파이썬 - 가장 기본적인 순차적인(sequential) 자료구조 C언어의 배열 A[2] = A[2] + 1은 기본연산만 포함하기 때문에 O(1) A[2]의 주소: RAM A[0] 주소 + 2 * 4bytes 100 + 8 = 108 배열은 읽기와 쓰기를 연산으로 제공. 기본시간 내에 다 수행할 수 있다. 파이썬의 리스트 A = [2, 4, 0, 5] 결정적인 차이: 객체가 다른 메모리에 저장됨 A[2] = A[2] + 1 0이 1로 바뀌는 것이 ..