파이썬/자료구조와 알고리즘

그래프의 기본 개념노드 (Node): 그래프의 정점(Vertex)간선 (Edge): 두 노드를 연결하는 선방향 그래프 (Directed Graph): 간선에 방향이 있는 그래프무방향 그래프 (Undirected Graph): 간선에 방향이 없는 그래프가중치 그래프 (Weighted Graph): 간선에 가중치(Weight)가 부여된 그래프인접 행렬 (Adjacency Matrix): 그래프를 2차원 배열로 표현인접 리스트 (Adjacency List): 그래프를 리스트의 리스트로 표현  코드들#그래프 정점 집합V(G1) = {A, B, C, D}V(G2) = {A, B, C, D} #그래프 간선E(G1) = { (A, B), (A, C), (A, D), (B, C), (C, D) }E(G2) = { (A..

이진 트리의 개념트리 자료구조는 나무를 뒤집어 놓은 모양트리의 맨위를 뿌리(root)라고 부름루트를 레벨 0으로 두고 밑으로 내려올 수록 레벨이 1씩 증가트리의 각위치는 노드라고 부름위의 그림은 9개이고 각 노드는 선(edge)로 연결되어 있음위 노드와 아래 노드 사이의 관계는 부모 - 자식 관계자식 노드 개수는 차수(degree)라고 부름자식이 없는 노드는 리프(leaf)라고 부름 이진 트리의 종류이진트리는 포화 이진트리(full binary tree), 완전 이진 트리(complete binary tree), 편향 이진 트리(skewed binary tree)3개로 나뉨 포화 이진 트리노드가 꽉 차 있는 상태의 트리노드 개수가 2 ** (높이+1 - 1) 공식으로 계산예) 높이가 3인 포화 이진트리는..

큐의 개념입구와 출구가 따로 있는 자료구조입구와 출구가 다름선입선출 용어rear = 꼬리front = 머리enqueue = 데이터 삽입dequeue = 데이터 추출코드들#큐 생성 #front = 머리 #rear = 꼬리queue = [None, None, None, None, None]front = rear = -1 #front 와 rear 둘다 데이터가 없어서 -1 로 초기화 #데이터 삽입 : enQueue#1. rear(꼬리) 1증가 시킨 후 #2. rear 위치에 데이터 넣기#큐 생성queue = [None, None, None, None, None]front = rear = -1rear += 1queue[rear] = '화사'rear += 1queue[rear] = '솔라'rear += ..

원형 선형 리스트의 개념 단순 연결 리스트와 비슷원형 연결 리스트의 마지막 노드가 다시 첫 번째 노드를 가르키도록 설정되어 리스트 형태가 원 형태로 구성 단순 연결 리스트의 구조#노드 생성class Node() : #노드 데이터 만들기 def __init__ (self) : #데이터를 생성할 때 자동으로 생성되는 부분 self.data = None self.link - Nonenode1 = Node()node.data = '다현'node1.link = node1 #원형 #노드 연결class Node() : #노드 데이터 만들기 def __init__ (self) : #데이터를 생성할 때 자동..

단순 연결 리스트의 개념 구조원리노드 구조다음 데이터를 가리키는 링크(link)가 필요데이터 뿐만 아니라 링크도 저장 해야함데이터와 링크로 구성된 항목을 노드라 명명 head첫번째 노드를 head 라고 함 #노드 생성class Node() : #Node 라는 데이터 형을 만드는 것 def __init__ (self) : #데이터 형을 생성 할 때 자동으로 실행되는 부분 self.data = None #데이터가 저장되는 부분 self.link = None #링크가 저장되는 부분 #첫번째 노드 생성class Node() : def __init__ (self) : self.data = None se..

그동안 작성했던 코드들을 다시 보면서 복습 했다.처음 코드를 작성 할 때는 책의 도움을 받고 작성했었다.두번째는 책을 보지 않고 작성하려고 노력했다.하지만 응용예제는 어려워 책을 도움을 받고 작성했다. 데이터가 5개인 선형 리스트#데이터가 5개인 선형 리스트 생성katok = ['사나', '쯔위', '다현', '나연', '정연']print(katok)['사나', '쯔위', '다현', '나연', '정연'] 데이터 삽입#데이터 삽입katok = ['사나', '쯔위', '다현', '나연', '정연']katok.append(None) #None 삽입print(katok) katok[5] = '지효' #None 자리에 '지효' 삽입print(katok)['사나', '쯔위', '다현..

큐입구와 출구가 따로 있는 선입선출의 특징을 가지고 있는 자료구조인큐(enQueue)  : 데이터 삽입,  데큐(deQueue)  : 데이터 추출을데이터 추출시 머리(front) 위치의 데이터가 추출 되고 데이터를 삽입시 꼬리(rear) 바로 다음 위치에 삽입머리 : 저장된 데이터 중 첫번찌, 꼬리: 저장된 데이터 중 마지막예) 유명 맛집의 대기줄큐 생성front와 rear 모두 -1이면 초기 상태이고 큐가 비었다는 의미로 해석# 큐 생성queue = [None, None, None, None, None]front = rear = -1 데이터 삽입#1 rear를1 증가 시킨 후 #2 rear 위치에 데이터 삽입#데이터 삽입queue = [None, None, None, None, None]front = ..

스택구조가장 먼저 넣은 것이 가장 나중에 나가는 구조스택 생성stack = [None, None, None, None, None]top = -1 데이터 삽입: pushstack = [None, None, None, None, None]top = -1top += 1stack[top] = '커피'top += 1stack[top] = '녹차'top += 1stack[top] = '꿀물'print('스택 상태')for i in range(len(stack) - 1, -1, -1) : #맨위에서부터 출력 print(stack[i])스택 상태NoneNone꿀물녹차커피 데이터 추출: popstack = ['커피', '녹차', '꿀물', None, None, None]top = 2print('스택 상태')for ..

원형 리스트시작 위치와 다음위치가 계속 이어진 후 마지막에 다시 시작으로 돌아오는 형태 #노드 생성class Node() : def __init__ (self) : self.data = None self.link = Nonenode1 = Node()node1.data = '다현'nodeq.link = node1 노드 두개 생성#노드 두개class Node() : def __init__ (self) : self.data = None self.link = Nonenode1 = Node()node1.data = '다현'node2 = Node()node2.data = '정연'node1.link = node2node2.link = node1 데이터가 5..

노드단순 연결 리스트는 데이터 뿐만 아니라 다음 데이터를 가르키는 링크(link)가 필요하다.노드 삽입새로운 노드를 생성 후 순서에 맞게 링크를 수정한다노드 삭제링크를 먼저 수정 후 노드를 삭제 한다노드 생성클래스라는 문법을 사용하여 노드 데이터형을 정의한다class Node() : def __init__ (self) : self.data = None self.data = None 빈 노드 생성 후 데이터 삽입###노드 생성class Node() : def __init__ (self) : self.data = None self.data = Nonenode1 = Node()node1.data = '다현'print(node1.data, end = ..