그래프란? 노드와 간선으로 이루어진 자료구조 그래프의 종류 - 무방향 그래프(Undirected Graph): 방향성이 없고 노드(정점)이 연결된 그래프 - 방향 그래프(Directed Graph): 무방향 그래프에서 방향성이 추가된 그래프 - 완전 그래프(Complete Graph): 각 정점에서 다른 모든 정점을 연결하여 최대 간선 수를 가진 그래프 -> 정점이 n개인 무방향 그래프에서는 최대 간선 수 = n(n-1)/2 -> 정점이 n개인 방향 그래프에서 최대 간선 수 = n(n-1) - 가중(치) 그래프(Weight Graph): 간선에 가중치를 담아서 표현(방향 여부 상관X) - 부분 그래프(Sub Graph): 일부 정점과 간선으로 구성된 그래프(가중치 그래프에서 조금 떼어낸 그래프) 그래프의..
테이블 자료구조란? -> 데이터가 키-값 형태로 저장된 구조 테이블 자료구조의 특징 - key를 이용해 원하는 데이터를 찾을 수 있다. - key는 중복될 수 없고 의미있는 값을 가진다. - 탐색 연산은 O(1)의 시간복잡도를 가지지만 메모리의 효율성이 낮고 적용 범위가 제한적이다. - 사전(dictionary)구조 혹은 맵(map)이라고 함. supermarket = {"bread": 1, "juice": 5, "snack": 18} # key 있는지 검사 if "snack" in supermarket: print("snack!") # value 있는지 검사 if 5 in supermarket.values(): print("juice!") # key 출력 print(supermarket.keys()) ..
우선순위 큐란? -> 우선순위를 근거로 데이터를 뽑는 구조 우선순위 큐의 특징 - 들어간 순서와 나가는 순서가 아무런 상관이 없다. - 데이터를 뽑을 때 우선순위를 근거로 뽑는다. - 우선순위를 판단하고 결정하는 건 프로그래머이다. - 같은 우선순위를 가진다면 먼저 들어온 원소를 처리한다. - 보통 힙을 통해 우선순위 큐를 구현한다. (배열이나 링크드리스트는 best와 worst의 편차가 크기 때문) 힙이란? - 완전 이진 트리(Complete Binary Tree)이다. - 부모 노드의 값이 항상 자식 노드들의 값보다 크거나(Max Heap) 작아야(Min Heap)한다. - 힙으로 우선순위 큐를 구현할 때는 노드에 저장된 값을 우선순위로 본다. - 힙은 루트 노드에 우선순위가 높은(숫자가 큰-Max ..
트리란? -> 계층적 관계를 표현하는 자료구조 -> 하나의 중심을 기점으로 뻗어나가는 구조 트리 용어 - 노드(Node): 트리의 구성 요소(기본 단위) => A, B, C, D, E, F, G, H, I, J - 간선: 노드와 노드를 연결하는 선 - 루트 노드(Root): 트리 구조에서 최상위에 존재하는 노드 => A - 단말 노드(Leaf Node): 아래로 또 다른 노드가 연결되어 있지 않은 노드 => H, I, J, F, G - 내부 노드: 단말 노드를 제외한 모든 노드 => A, B, C, D, E - 서브 트리(Sub-tree): 트리에서 일부를 떼어낸 트리 - 레벨(level): 루트 노드를 기준으로 레벨 0부터 자식 노드로 가면서 레벨이 증가한다. - 높이: 최대 레벨의 값(0부터 셌을 때..
연결리스트란? 연결리스트의 기본구조 - Node: 데이터 + 다음 데이터를 가리키는 주소. 기본 단위 - Pointer: 각 노드에서 다음 데이터를 가리키는 주소값을 저장 - Head: 시작점의 데이터 - Tail: 마지막 데이터 - Next: 다음 데이터. 없을 경우 Null값을 가진다. 연결리스트의 특징(C언어에 해당) 장점: - 미리 데이터 공간을 할당할 필요가 없다. - 유동적으로 데이터 삽입, 삭제 가능. (가리키는 주소값을 자신으로 하면 됨.) - 수정 시 시간복잡도 O(1). 단점: - 각 노드에 별도로 주소 공간을 가져야 함. (저장공간 효율이 떨어짐) - 데이터를 찾는데 시간이 오래걸림. (하나씩 타고 가야 하기 때문) 단방향 연결리스트 삽입: E라는 노드가 있을 경우, A의 Next값으..
큐란? -> 먼저 넣은 데이터가 먼저 나가는 구조이다. -> 놀이동산 줄서기를 생각하면 편하다. 먼저 기다린 사람이 먼저 탑승하는 구조. from collections import deque queue = deque() queue.append(3) # [3] queue.append(5) # [3, 5] queue.append(2) # [3, 5, 2] queue.popleft() # [5, 2] queue.append(8) # [5, 2, 8] queue.popleft() # [2, 8]
스택이란? -> 마지막에 넣은 데이터를 가장 먼저 빼는 구조이다. LIFO(Last-In First-Out)방식이다. 스택의 특징 장점: 구조가 단순하고 구현이 쉽다. 데이터 저장, 불러오는 속도가 빠르다. 단점: 데이터의 최대 개수를 미리 정해주어야 한다. 저장공간의 낭비가 발생할 수 있다. (미리 최대 개수를 지정하기 때문) -> 단점때문에 보통 배열로 대체하여 사용한다. stack = [] stack.append(3) # [3] stack.append(6) # [3, 6] stack.append(4) # [3, 6, 4] stack.pop() # [3, 6] stack.append(7) # [3, 6, 7] stack.pop() # [3, 6]
배열이란? -> 같은 종류의 데이터를 순차적으로 저장하는 자료구조 배열의 특징 -> index를 통해 직접 접근이 가능하다. 장점: 빠른 접근이 가능하다. 조회 시간복잡도 O(1) 단점: 데이터 추가와 삭제에 비용이 많이 든다. 데이터 추가 시 공간이 많이 필요하며, 삭제 시 빈 공간이 생겨 이를 관리해주어야 한다. 길이 조절이 어렵다. (C나 C++의 경우에만 해당) arr = [1, 2, 3, 4, 5] # index 접근(0부터 카운트) print(arr[2]) # 3 # 배열의 길이 출력 print(len(arr)) # 5 # 삽입(맨 끝) arr.append(6) # [1, 2, 3, 4, 5, 6] print(arr) # 삽입(인덱스, 값) arr.insert(1, 9) # [1, 9, 2, ..
