HappyTomatoLife

학점교류로 듣는 숙명여대 자료구조 day 9. 2022.1.3. 월요일 1. Introduction 2. Binary Trees 3. Threaded Binary Trees 4. Heaps Tree def) A hierarchical data structure that consists of one or more nodes 계층적 자료 구조 root / sub trees 트리는 그래프의 부분 집합 다 그래프인데, 루트가 독립되어있어서.. 노드들이 연결된 것을 그래프라고 한다. Huffman Coding Tree Text compression method based on the frequency example : "time and tide wait for no man" 단말 노드를 만들어준다. 자식 노드를 ..

필자는 숙명여대 자료구조 수업을 국내 학점교류를 통해 2021년 겨울 계절학기에 수강하였다. 중간고사는 비대면 퀴즈로 진행되었으며, 1시간 동안 16문제가 주어졌다. 시험은 코딩으로 문제를 해결하는 실력을 확인한다기보다는, 자료구조 개념을 기억하고 있는지, 해당 개념을 적용하여 답을 구해낼 수 있는지에 더 초점을 맞추고 있었다. 기억에서 사라지기 전에, 숙명여대 자료구조 중간고사 시험의 유형과 문제들을 기록해두려고 한다. 부디 도움이 되길 바란다. 1. 숙명여대 자료구조 중간고사의 유형 객관식과 주관식으로 구성되어있었다. 1) 알고리즘의 조건 2) 코드를 보고 고르시오 스택, 큐, 순환 큐, NQueens problem 개념이 다음과 같은 형태로 나왔다. - 밑줄 친 부분에 들어갈 [코드]를 고르시오 -..

WHY 다른 탐색 방법은 n이 증가할수록 필연적으로 탐색 시간이 오래 걸림 WHAT hashing search는 탐색키간에 비교를 수행하는 것이 아니라, 키에 산술적인 연산을 수행해서 정보에 접근한다. 적용 사례에는 사전이 있다. identifier, hash function, hash table, hash code를 알아두자 HASH TABLE identifier가 저장된 고정된 크기의 표 (고정되지 않은 경우 dynamic hashing이라고 한다.) dynamic hashing이란, reconfigure the hash table size flexibly according to the frequency of key collision row는 bucket col는 slot이라고 부른다. Identif..

doubly linked list 기존 SLL Singly Linked List는 단방향으로 연결되어있기에 뒷 노드에서 앞으로 탐색하는 것이 불가능하다. 이 문제를 해결하기 위해 doubly linked list가 제안되었다. DLL는 각 노드가 link를 left link, right link로 두 가지 가지고 있는 리스트를 의미한다. 연결은 양방향으로 해줌으로써 삭제와 삽입이 용이해진다. 각 노드는 data field, left link, right link로 구성되며 DLL은 Binary tree와 같은 구조에서 쓰인다 스켈레톤 코드 class Node: def __init(self, data): pass class DLL: def __init__(self): pass def insert(self,..

Backtracking 가능성을 탐색하는 알고리즘 candidate가 제거되는 캐이스를 체크한다. Permutation 겹치지 않는 알파벳이 주어졌을 때 [a, b, c]를 어떻게 순열 계산을 해줄 것인가? n!, abc, acb, bac, bca, cab, cba a b c가 주어지면, 세 개의 빈 공간 _ _ _이 생기는 것과 같다. 첫 자리에는 무엇이 올까? 다음 자리에는? 그 다음 자리에는 무엇이 오게 될까? 이 부분을 결정해주어야 한다. a가 온 경우, b, c가 올 수 있다. b가 온 경우, a, c가 올 수 있다. c가 온 경우, a, b가 올 수 있다. 하나씩 탐색 구조가 만들어진다. sudo code def BT(level, letters[]) // 종료 조건 if leve == lett..

학점교류로 듣는 숙명여대 자료구조 day 7. 중간고사 전날.. 1. 반복문과 비교한 재귀문의 장단점은? + 구현이 편리하다 - frequent function call overhead : 자주 불려서 비효율적임 2. n개의 정렬된 정수에 대하여 반복문과 재귀 호출 함수를 각각 사용하여 이진 탐색하는 프로그램을 작성하시오. 재귀 호출 함수가 몇 번 호출되는지 변수를 추가하여 확인하시오. * 구현 def recursive(lst, item, left, right, cnt): if left > right: print("cnt = ", cnt) return -1 else: mid = (left + right) // 2 if lst[mid] == item: print("Cnt = ", cnt) return mi..

숙명여대 학점교류로 듣는 자료구조 day 7. 2021.12.30 overflow handling open addressing - address is not fixed linear probing : 선형 탐색법 quadratic probing : 2차 rehashing : 재해싱 원래 들어가야 하는 버킷인 home bucket이 아니라, 다른 주소에 저장하는 것을 허용하는 방식이다. chaining * linear probing : 선형 조사법 버킷에 오버플로우가 발생하면, 다음 번 빈 버킷을 찾아 저장한다. suppose a hash table is represented in one-dimensional array h = hashing(26) * initialization of the hash tabl..

Binary Search def binary(lst, item, left, right): pass def binary(lst, item, left, right): while True: if left > right: break mid = (left + right) // 2 if lst[mid] == item: return mid elif lst[mid] > item: right = mid - 1 else: left = mid + 1 return -1 lst = [1,2,3,34,55,67,89,100] print(binary(lst, 100, 0, len(lst)-1))

순차 탐색 def sequential(lst, num): for i in range(len(lst)): if lst[i] == num: return i return -1

자료구조 | Singly Linked List | Linked List (tistory.com) 자료구조 | Singly Linked List | Linked List singly Linked List가 동작하기 위해 필요한 클래스 링크드 리스트는 노드로 구성된다. 노드는 노드 자신의 data와 다른 노드와 연결되는 link로 구성된다. 단방향으로만 연결해주는 리스트 형태를 Singl tomatolife.tistory.com 위 글에서 Singly Linked List 클래스 내부 함수를 활용하였다. Double Ended Queue • add_front • add_rear • pop_front • pop_rear import random class Node: def __init__(self, item)..