나만의 개발 블로그

🙆‍♂️ 그래프 그래프란 노드와 그 노드를 모아놓은 간선을 하나로 모은 자료구조 하나의 객체와 다른 객체가 연결되어 있는 구조 종류 무방향 그래프 > 간선에 방향이 없음 방향 그래프 > 간선에 방향이 있음 가중치 그래프 > 간선에 가중치가 할당된 그래프, 네트워크라고도 부른다. 부분 그래프 > 특정 그래프에서 일부분을 때어낸 그래프 용어 노드, 간선, 인접 정점 차수 > 연결되어 있는 간선 수 무방향 그래프 : 차수의 합 == 간선 * 2 방향 그래프 : 진입차수와 진출차수가 존재함. 모든 진입차수의 합은 간선의 수 단순경로 - 경로 중 반복되는 간선이 없는 경로 사이클 - 시작 정점과 종료 정점이 동일한 경로 연결 그래프 - 모든 정점들 사이에 경로가 존재하는그래프 트리 - 사이클을 가지지 않는 연결 ..

🙆‍♂️ 이진 탐색 트리 탐색트리는 탐색을 위한 트리 기반의 자료 구조입니다. 이진 탐색 트리란 효율적인 탐색을 위한 이진트리 기반의 자료구조. 위와 같이 정렬할 수 있음. 힙트리와 이진탐색트리의 차이점 힙트리 : 최댓값이나 최솟값을 빠르게 검색하기 위한 목적 이진탐색트리 : 특정 값을 빠르게 탐색하기 위한 목적 #binary search tree class BSTNode: def __init__(self, key, value): self.key=key self.value=value self.left=None self.right=None 연산 탐색연산 logn의 연산속도를 갖음. def search(n,key): if n==None: return None elif n.key == key: return n..

🙆‍♂️일반 트리 트리 : 계층적인 자료의 표현에 적합한 자료 구조다. 최상위 노드를 루트 노드라 부름. 자식을 갖지 못하는 노드 = 단말 노드 class TNode: def __init__(self,data, left, right): self.data = data self.left = left self.right = right d = TNode('D',None,None) e = TNode('E',None,None) f = TNode('F',None,None) b = TNode('B',d,e) c = TNode('C',f,None) a = TNode('A',b,c) 🙆‍♂️이진 트리 이진 트리 : 모든 노드가 2개의 서브 트리를 갖는 트리 완전 이진트리 : 왼쪽부터 꽉찬 경우 포화 이진트리 : 모든 노드..

🙆‍♂️리스트 """ 리스트 """ class ArrayList: def __init__(self): self.items=[] def insert(self,pos,elem): self.items.insert(pos,elem) def delete(self,pos): return self.items.pop(pos) def isEmpty(self): return self.size()==0 def getEntry(self,pos): return self.items[pos] def size(self): return len(self.items) def clear(self): self.items=[] def find(self,item): return self.items.index(item) def replace(se..

🙆‍♂️ 우선순위 큐 """ 우선순위 큐 """ class PQueue: def __init__(self): self.items = [] def emt(self): return len(self.items)==0 def size(self): return len(self.items) def enqueue(self, item): self.items.append(item) def dequeue(self): if not self.emt(): maxI = 0 high = self.items[maxI][2] for i in range(1,self.size()): if self.items[i][2] > high: high = self.items[i][2] maxI = i return self.items.pop(maxI..

🙆‍♂️ 원형 큐 class """ 원형 큐 클래스 CQueue def emt : 큐에 값이 없다면 True를 반환 있다면 False를 반환 def full : 큐가 포화상태라면 True를 반환 아니라면 False를 반환 def clear : 큐 초기화 def enqueue : 포화상태가 아니면서 알파벳 값(ch)만 추가 def dequeue : 공백상태가 아니라면 최전단값 반환하고 제거 def peek : 큐의 최전단값 반환 def size : 큐의 길이 반환 def display : 현재 큐 상태 출력 """ MAX_SIZE = 100 class CQueue: def __init__(self): self.front=0 self.rear=0 self.items=[None] * MAX_SIZE def e..

🙆‍♂️선형 큐 """ 선형큐 """ MAX_LQSIZE = 10 class LQueue: def __init__(self): self.items=[] def display(self): for item in self.items: print(f'{item} =>',end = " ") print() def full(self): return len(self.items)==MAX_LQSIZE def emt(self): return len(self.items)==0 def enqueue(self,item): if self.full(): print("It is Full!") else: self.items.append(item) def dequeue(self): if not self.emt(): return self..

🙆‍♂️연습 문제 4.1 스택에서 사용되는 정보의 입출력 방법은 무엇인가? 1. LIFO 2. FIFO 3.FILO 4.LILO 답 : 1번 후입선출이다. 4.2 스택의 응용분야로 거리가 먼 것은? 1. 미로 찾기 2. 수식 계산 및 수식 표기법 3. 운영체제의 작업 스케줄링 4. 서브루틴의 복귀번지 저장 답 : 3번 운영체제의 작업 스케줄링이다. 4.3 다음 중 스택에 대한 설명을 모두 골라라. 1) 입출력이 한쪽 끝으로만 제한된 리스트이다. 2) head(front)와 tail(rear)의 2개 포인터를 갖고 있다. 3) FIFO(First-In-First-Out)방식으로 동작한다. 4) 배열 구조와 연결된 구조로 구현이 가능하다. 5) 함수 호출 시 복귀 주소를 저장하는데 사용된다. 답 : 1,4,..

🙆‍♂️ 미로 탐색 (깊이 우선 탐색) 알고리즘 """ 깊이우선탐색 - 미로 탐색 """ #미로 정의 maze = [[1,1,1,1,1,1], ['H',0,0,0,0,1], [1,0,1,0,1,1], [1,1,1,0,0,'X'], [1,1,1,0,1,1], [1,1,1,1,1,1]] #미로 출력 def print_maze(maze): print("=====MAZE=====") for r in maze: for p in r: print(p, end=" ") print() print("==============") #탐색 알고리즘 def DFS(maze): s = Stack() x,y = 0,1 s.push( (x,y) ) #시작점 while maze[y][x] != 'X': if not s.emt(): m..

🙆‍♂️리스트 """ 리스트 """ class ArrayList: def __init__(self): self.items=[] def insert(self,pos,elem): self.items.insert(pos,elem) def delete(self,pos): return self.items.pop(pos) def isEmpty(self): return self.size()==0 def getEntry(self,pos): return self.items[pos] def size(self): return len(self.items) def clear(self): self.items=[] def find(self,item): return self.items.index(item) def replace(se..