데굴데굴

공부자료: 신찬수 교수님 유튜브 '자료구조' 재생목록 자료구조 해시테이블 - 소개, 해시 함수 - YouTube 자료구조 해시테이블 - open addressing (linear probing) - YouTube 해시테이블은 데이터를 읽고 쓰는데 훨씬 빠른 속도를 자랑한다. CS50에서 배웠던 내용을 살짝 정리해보면 이렇다. 해시 (CS50 강의 참고) 해시는 '연결 리스트의 배열'. 여러 값들을 바구니에 나눠 담는다고 가정할 때, 각 값들은 '해시 함수'를 통해서 어떤 바구니에 담길지 결정된다. 그럼 이 해시 함수는 무슨 기준으로 값을 분류하는가? 이는 명확하지 않다. 맨 첫 글자일수도 있고, 앞에 두 글자일수도 있고.. 값이 어떠느냐에 따라 다른 해시 함수를 선택한다. 이상적인 해시 함수는 각 바구니..

공부자료: 신찬수 교수님 유튜브 '자료구조' 재생목록 자료구조 양방향연결리스트 삽입-삭제-탐색 연산 - YouTube 양 끝이 연결된 원형 양방향 연결리스트 Circularly Doubly Linked List로 관리하면 편하다. 빈 노드 = 더미노드 dummy node를 head 노드로 설정한다. (더미노드의 key 값은 None) 즉 양방향 연결리스트의 초기 상태에서 더미노드는 자기 자신을 가리킨다. splice 연산 splice(a, b, x): a부터 b까지를 잘라 x 다음에 넣는다. splice 연산을 위한 전제조건 1. a -> ... -> b 2. a와 b 사이에 head node가 있으면 안 됨. 3. a와 b 사이에 x 노드가 있으면 안 됨. def splice(self, a, b, x)..

공부자료: 신찬수 교수님 유튜브 '자료구조' 재생목록 자료구조 연결리스트 소개 - 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..