티스토리

나만의 개발 블로그

검색하기

블로그 홈

나만의 개발 블로그

naman-develop.tistory.com/m

내만 님의 블로그입니다.

구독자: 1

방명록 방문하기

728x90

반응형

주요 글 목록

그래프 🙆‍♂️ 그래프 그래프란 노드와 그 노드를 모아놓은 간선을 하나로 모은 자료구조 하나의 객체와 다른 객체가 연결되어 있는 구조 종류 무방향 그래프 > 간선에 방향이 없음 방향 그래프 > 간선에 방향이 있음 가중치 그래프 > 간선에 가중치가 할당된 그래프, 네트워크라고도 부른다. 부분 그래프 > 특정 그래프에서 일부분을 때어낸 그래프 용어 노드, 간선, 인접 정점 차수 > 연결되어 있는 간선 수 무방향 그래프 : 차수의 합 == 간선 * 2 방향 그래프 : 진입차수와 진출차수가 존재함. 모든 진입차수의 합은 간선의 수 단순경로 - 경로 중 반복되는 간선이 없는 경로 사이클 - 시작 정점과 종료 정점이 동일한 경로 연결 그래프 - 모든 정점들 사이에 경로가 존재하는그래프 트리 - 사이클을 가지지 않는 연결 .. 공감수 0 댓글수 0 2022. 12. 20.
[자료구조] 트리 - 탐색 트리 🙆‍♂️ 이진 탐색 트리 탐색트리는 탐색을 위한 트리 기반의 자료 구조입니다. 이진 탐색 트리란 효율적인 탐색을 위한 이진트리 기반의 자료구조. 위와 같이 정렬할 수 있음. 힙트리와 이진탐색트리의 차이점 힙트리 : 최댓값이나 최솟값을 빠르게 검색하기 위한 목적 이진탐색트리 : 특정 값을 빠르게 탐색하기 위한 목적 #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.. 공감수 0 댓글수 0 2022. 12. 20.
[자료구조] 트리 - 일반 트리, 이진 트리, 결정트리, 힙 🙆‍♂️일반 트리 트리 : 계층적인 자료의 표현에 적합한 자료 구조다. 최상위 노드를 루트 노드라 부름. 자식을 갖지 못하는 노드 = 단말 노드 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개의 서브 트리를 갖는 트리 완전 이진트리 : 왼쪽부터 꽉찬 경우 포화 이진트리 : 모든 노드.. 공감수 0 댓글수 0 2022. 12. 20.
[자료구조][파이썬으로 쉽게 풀어쓴 자료구조] 05 큐 문제풀기 🙆‍♂️리스트 """ 리스트 """ 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.. 공감수 0 댓글수 0 2022. 10. 25.
[자료구조] 큐 - 우선순위 큐를 활용한 미로 탐색 🙆‍♂️ 우선순위 큐 """ 우선순위 큐 """ 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.. 공감수 0 댓글수 0 2022. 10. 25.
[자료구조] 큐 - BFS 미로 탐색 🙆‍♂️ 원형 큐 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.. 공감수 0 댓글수 0 2022. 10. 25.
[자료구조] 큐 - 선형 큐, 원형 큐, 덱 🙆‍♂️선형 큐 """ 선형큐 """ 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.. 공감수 0 댓글수 0 2022. 10. 25.
[자료구조][파이썬으로 쉽게 풀어쓴 자료구조] 04 스택 문제풀기 🙆‍♂️연습 문제 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,.. 공감수 0 댓글수 0 2022. 10. 24.
[자료구조] 스택 - 미로 탐색 🙆‍♂️ 미로 탐색 (깊이 우선 탐색) 알고리즘 """ 깊이우선탐색 - 미로 탐색 """ #미로 정의 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.. 공감수 0 댓글수 0 2022. 10. 24.
[자료구조][파이썬으로 쉽게 풀어쓴 자료구조] 03 리스트 문제풀기 🙆‍♂️리스트 """ 리스트 """ 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.. 공감수 4 댓글수 1 2022. 10. 13.
[자료구조] 스택 - 중위표현식 후위표현식으로 변환 🙆‍♂️ 후위표현식으로 변환하기 """ 스택 클래스 Stack def emt : 스택에 값이 없다면 True를 반환 있다면 False를 반환 def size : 스택의 현재 길이를 반환 def clear : 스택 값을 초기화 def push : 입력 요소 ch를 스택에 입력 def pop : 스택의 최상단 값을 삭제 def peek : 스택의 최상단 값 반환 def disply : 스택의 상태를 출력 """ class Stack: def __init__(self): self.stack=[] def emt(self): return len(self.stack)==0 def size(self): return len(self.stack) def clear(self): self.stack=[] def push(s.. 공감수 0 댓글수 0 2022. 10. 6.
[자료구조] 스택 - 괄호 검사 알고리즘 🙆‍♂️ 괄호 검사 알고리즘 """ 괄호 검사 알고리즘 """ def checkB(string): stack = [] for i in string: if i in ['(','{','[']: stack.append(i) elif i in [')','}',']']: if len(stack) == 0: return "Wrong String!" else: if (( stack[-1] == '(' and i==')' or stack[-1] == '{' and i=='}' or stack[-1] == '[' and i==']' )): stack.pop(-1) else: return "Wrong String!" if len(stack) != 0: return "Wrong String!" else: return "Go.. 공감수 0 댓글수 0 2022. 10. 6.
[자료구조] 스택 - 스택 class 구현 🙆‍♂️스택 """ 스택 클래스 Stack def emt : 스택에 값이 없다면 True를 반환 있다면 False를 반환 def size : 스택의 현재 길이를 반환 def clear : 스택 값을 초기화 def push : 입력 요소 ch를 스택에 입력 def pop : 스택의 최상단 값을 삭제 def peek : 스택의 최상단 값 반환 def disply : 스택의 상태를 출력 """ class Stack: def __init__(self): self.stack=[] def emt(self): return len(self.stack)==0 def size(self): return len(self.stack) def clear(self): self.stack=[] def push(self,ch): se.. 공감수 0 댓글수 0 2022. 10. 6.
[자료구조] 리스트 - List 🙆‍♂️ List class ArrayList: def __init__(self): self.items=[] #O(n) def insert(self,pos,elem): self.items.insert(pos,elem) #O(n) def delete(self, pos): self.items.pop(pos) def isEmpty(self): return self.size == 0 #O(1) 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(.. 공감수 0 댓글수 0 2022. 9. 27.
[자료구조] 스택 - Stack 🙆‍♂️Stack First in Last out인 자료구조 입니다. 데이터가 쌓여져 가는 구조인데 PUSH라는 명령어로 데이터를 Stack의 가장 위에 올리고 POP이라는 명령어로 Stack의 가장 위의 명령어를 뺍니다. TOP이라는 명령어는 가장 위의 명령어에 접근합니다. 코딩테스트에서는 배열을 사용하여 스택이라고 가정하여 접근합니다. 🙋‍♂️문제 🚀 valid parentheses 괄호 열리고 닫힌 것을 구분하는 문제들은 stack 문제로 보고 풀 수 있습니다. PUSH를 해서 괄호를 열어주고 POP을 해서 매칭이되면 괄호를 닫아줍니다. 매칭이 안되면 invalid하다는 것을 출력하는 것입니다. >관련 문제 공감수 0 댓글수 0 2022. 8. 23.
[알고리즘][정렬] 계수 정렬 - Counting sort 🙆‍♂️계수 정렬 주어진 배열의 값 범위가 작은 경우 빠른 속도로 정렬하는 알고리즘 입니다. 원소의 개수와 원소 최대 값이 수행시간에 영향을 줍니다. 🙋‍♂️방식 arr = [4,0,6,2,0,6] 이런 배열을 정렬할 때 🚀count 배열 값 2 0 1 0 1 0 2 인덱스 0 1 2 3 4 5 6 먼저 배열의 요소들을 카운팅을 하고 각 인덱스에 카운팅 값들을 갖는 count 배열을 만듭니다. count 배열을 만들 때 0,2,4,6만 있으니 이에 대한 수만 세는 것이 아니라 가장 작은 수(0)부터 가장 큰 수(6)까지의 수를 전부 계수합니다. 🚀누적 count 배열 값 2 2 3 3 4 4 6 인덱스 0 1 2 3 4 5 6 그리고 누적 카운트 배열을 만듭니다. 🚀최종 index 배열 값 1 1 2 2.. 공감수 0 댓글수 0 2022. 7. 19.
[알고리즘][정렬] 병합 정렬 - Merge Sort 🙆‍♂️병합 정렬 병합정렬은 분활하고 정렬하고 합병하는 그런 정렬입니다. 🙋‍♂️방식 먼저 이렇게 배열이 있따면 배열의 길이가 1이 될 때 까지 나눕니다. 그리고 정렬과 합병을 반복하면 됩니다. 시간 복잡도는 O(n log n) 입니다. def merge(arr): if len(arr) == 1: return arr #####나누는 구간##### middle = len(arr)//2 left_arr = arr[:middle] right_arr = arr[middle:] leftArrSort = merge(left_arr) rightArrSort = merge(right_arr) leftIdx = 0 rightIdx = 0 #####합치는 구간##### sortArr = [] while leftIdx < .. 공감수 0 댓글수 0 2022. 7. 18.
[알고리즘][정렬] 선택 정렬 - Selection Sort 🙆‍♂️선택 정렬 각 칸에 들어갈 요소를 선택해서 정렬하는 방법입니다. 🙋‍♂️방식 arr = [6,4,2,8] 이렇게 배열이 있을 때 오름차순으로 선택정렬을 한다면 #level1 arr = [2,4,6,8] 첫 번째 자리에 들어갈 가장 작은 2와 6을 바꿔줍니다. 그러면 정렬이 완성됩니다. 시간 복잡도는 O(n^2)입니다. 그리고 stable하지 않은 정렬입니다. 공감수 0 댓글수 0 2022. 7. 18.
[알고리즘][정렬] 삽입 정렬 - Insertion Sort 🙆‍♂️삽입 정렬 삽입 정렬은 앞에서부터 이미 정렬된 요소와 비교하여 자신의 위치에 삽입하는 정렬입니다. 🙋‍♂️방식 arr = [8,6,2,4] 이 배열을 오름차순으로 삽입정렬하려 하면 #level 1 arr = [6,8,2,4] 01. 8과 6을 비교하여 삽입 #level 2 #first arr = [6,2,8,4] #second arr = [2,6,8,4] 02. 2와 8, 2와 6을 비교하면서 적절한 위치에 삽입 #level 3 #first arr = [2,6,4,8] #second arr = [2,4,6,8] 03. 4와 8, 4와 6 4와 2를 비교해서 적절한 위치에 삽입 시간 복잡도는 O(n^2)입니다. 그리고 stable한 정렬입니다. def select(arr): for i in rang.. 공감수 0 댓글수 0 2022. 7. 18.
[알고리즘][정렬] 버블 정렬 - Bubble Sort 🙆‍♂️버블 정렬 서로 인접한 두 원소의 대소를 비교해서 조건에 따라 교환을 수행하여 정렬하는 방법입니다. 직관적인 정렬 방식입니다. 🙋‍♂️방식 a=[7,3,1,6,2] 이렇게 배열이 있을 때 버블 정렬을 사용해서 오름차순 정렬을 한다고 했을 때 a[0]과 a[1]을 비교해서 a[0]의 크기가 작다면 가만히 있고 크다면 a[1]과 자리를 바꿔줍니다. #1단계의 첫 번째 스위칭 a=[3,7,1,6,2] #1단계의 두 번째 스위칭 a=[3,1,7,6,2] #1단계의 세 번째 스위칭 a=[3,1,6,7,2] #1단계의 네 번째 스위칭 a=[3,1,6,2,7] 첫 번째 단계를 수행하면 이런식으로 수행되어 가장 큰 수인 7이 뒤로 옮겨지고 그 다음 계속적으로 수행하면 큰 수 부터 우측에 쌓이게 됩니다. 버블 정.. 공감수 0 댓글수 0 2022. 7. 16.

728x90

반응형

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.