HappyTomatoLife

학점교류로 듣는 숙명여대 자료구조 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)..

자료구조 | Singly Linked List | Linked List (tistory.com) 자료구조 | Singly Linked List | Linked List singly Linked List가 동작하기 위해 필요한 클래스 링크드 리스트는 노드로 구성된다. 노드는 노드 자신의 data와 다른 노드와 연결되는 link로 구성된다. 단방향으로만 연결해주는 리스트 형태를 Singl tomatolife.tistory.com Linked Queue Singly Linked List에 미리 구현해둔 함수 중 몇 개를 가져오면 된다. isEmtpy add_rear pop_front import random class Node: def __init__(self, item): self.data = item se..

singly Linked List가 동작하기 위해 필요한 클래스 링크드 리스트는 노드로 구성된다. 노드는 노드 자신의 data와 다른 노드와 연결되는 link로 구성된다. 단방향으로만 연결해주는 리스트 형태를 Singly linked list라고 한다. DLL Doubly linked list의 경우, left link와 right link를 모두 제공한다. 스켈레톤 코드 : 함수가.. 많기도 하다. class Node: def __init__(self): pass class SLL: def __init__(self): pass def isEmpty(self): pass def addFront(self, node): pass def addRear(self, node): pass def addSort(se..

미로 탈출하기 문제 : 입구로부터 출구로 나가는 길을 찾아라! 조건 : 0은 움직일 수 있는 길, 1은 불가능한 길이다. 방향 : 상하좌우, 대각선으로 움직일 수 있다. 추가적인 안내 미로는 2차원 배열에 구현되어 있다. 입구는 maze[0][0]이고, 출구는 maze[row-1][col-1]이다. 나가는 길을 찾기 위해 move[0] move[1] move[2] move[3] 을 사용할 수 있다. maze[next_row][next_col] = ? mark라는 배열을 만들어 지나온 길을 기록해둔다. mark = [[0]*10 for i in range(10)] mark=[[0]*10 for i in range(10)] print(mark) path stack backtracking을 위한 stack으로..

숙명여대 학점교류로 듣는 자료구조 day 6. 2021.12.29. 수요일 Search Sequential search binary search interpolation search hashing search Sequential search a search key is searched sequentially from the first item of a list with unordered items average # of comparisons : (n+1)/2 def seqsearch(num, item, n): for i in range(n): if item == num[i]: return i return -1 레코드에서 아무런 가공을 하지 않고 탐색을 시작한다. 계속 반복적으로 + 순서대로 비교한다. b..

숙명여대 학점교류로 듣는 자료구조 day 6. 2021.12.29. 수요일 Doubly linked list problem of SLL when deleting a node, it should know a prior node to connect the list DLL each node had both before and after nodes easy to delete / insert a node fields data left link right link applications binary tree DLL Insert class Node: def __init__(self, data): self.data = data self.llink = None self.rlink = None def insert(self..