Major class
[ 자료구조 ] 동적 계획법 (dynamic programming)
1. 배낭에 담을 수 있는 보석의 최대 가격 계산 함수 def knapsack(maxWeight, rowCount, weight, money): """ maxWeight: 배낭 최대 무게 rowCount: 보석 개수 weight: 보석 무게 리스트 money: 보석 가격 리스트 출력값: 배낭에 담을 수 있는 보석의 최대 가격 """ print('## 메모이제이션 배열 ##') # 코드 작성 목표: 메모이제이션 배열 생성, 배낭의 담을 수 있는 보석의 최대 가격 return array = [[0 for _ in range(maxWeight + 1)] for _ in range(rowCount + 1)] for row in range(1, rowCount + 1): print(f'{row} 개 --> ', ..
[ 자료구조 ] 검색 알고리즘 (search algorithm)
1. 이진 검색 함수 def book_search(index_array, find_name): pos = -1 start = 0 end = len(index_array) - 1 while start index_array[mid][0]: start = mid + 1 else: end = mid - 1 return pos 위치(pos)를 처음에 -1로 설정한다. start≤end일 경우 계속 반복하고 mid에 start와 end의 중간값을 넣어준다. 만약 찾는 데이터와 중간값이 같을 경우 반환 찾는 데이터가 더 작을경우 end = mid - 1 찾는 데이터가 더 클경우 start = mid + 1 찾는 데이터가 존재하지 않을 경우 초기 설정한 pos값 반환 = -1 퀵 정렬과 비슷한 알고리즘 → pivot을..
[ 자료구조 ] 정렬 알고리즘 (Sorting Algorithms)
1. 선택 정렬(앞부터 i, i+1 비교) O(n^2) def selectionSort(array): n = len(array) for i in range(n-1): minIdx = i for k in range(i + 1, n): if (array[minIdx] > array[k]): minIdx = k array[i], array[minIdx] = array[minIdx], array[i] return array i(0, n-1): min값에 i를 저장, 한 사이클 끝나면 min과 i의 값을 스왑 k(i+1, n): k값과 min값을 비교하면서 min값보다 k값이 작으면 min에 k값 대입 = i와 i+1값을 비교해 값을 바꿔주는 정렬 2. 삽입 정렬(앞부터 범위, 뒤부터 비교) O(n^2) [x] ..
[ 자료구조 ] 재귀 호출 (recursive call)
1. 재귀호출 이용한 카운트다운 함수 def countDown(n): if n==0: print('발사!!') else: print(n) countDown(n-1) 2. 재귀호출 이용한 별 출력 함수 def printStar(n): if n > 0: printStar(n-1) print('★' * n) 3. 단과 곱할 숫자 이용하여 재귀호출로 구구단 출력 함수 def gugu(dan, num): print("%d x %d = %d" %(dan, num, dan*num)) if num
[ 자료구조 ] 그래프 (graph)
1. 그래프 출력 함수 def print_graph(g): for row in range(g.SIZE): for col in range(g.SIZE): print(g.graph[row][col], end = '\\t') print() print() 2. 깊이 우선 탐색 함수 def find_vertex(g, find_vtx): stack = [] visitedAry = [] current = 0 stack.append(current) visitedAry.append(current) while len(stack) > 0: next = None for vertex in range(g.SIZE): if g.graph[current][vertex] != 0: if vertex not in visitedAry: ..
[ 자료구조 ] 이진 트리 (binary tree)
1. 주어진 리스트로 이진 트리 생성 (중복 제거) def generate_book_tree(bookAry): node = TreeNode() node.data = bookAry[0][0] root = node for i in bookAry[1:]: node = TreeNode() node.data= i[0] current = root while True: if current.data > i[0]: if current.left ==None: current.left = node break current = current.left elif current.data < i[0]: if current.right ==None: current.right = node break current = current.righ..
[ 자료구조 ] 큐 (queue)
1. 큐가 꽉 차있는지 확인하는 함수 def is_queue_full(self): if self.size - 1 != self.rear: return False elif self.size -1 == self.rear and self.front == -1: return True else: for i in range(self.front + 1, self.size): self.queue[i - 1] = self.queue[i] self.queue[i] = None self.front -= 1 self.rear -= 1 return False 2. 큐가 비었는지 확인하는 함수 def is_queue_empty(self): if self.front == self.rear: return True else: retu..