자료구조&알고리즘4 [자료구조] Graph의 검색, DFS, BFS 💡그래프의 검색 DFS(Depth First Search) 깊이 우선 검색 BFS(Breadth First Search) 넓이 우선 검색 ✨ DFS, BFS의 차이 DFS(Depth First Search)는 하단의 Child Node까지 방문한다 BFS(Breadth First Search)는 같은 레벨의 노드들을 방문한다 DFS 는 스택(Stack)으로 구현, BFS는 큐(Queue)로 구현한다 DFS 를 이용할 때 재귀호출을 이용하면 코드가 훨씬 간결해진다 -> 실제로 재귀함수 자주 구현한다 2023. 4. 6. [자료구조] 그래프(Graph) ✨ 그래프(Graph)의 개념 트리의 한 형태이다 트리는 위에서 아래로 접근하지만 그래프는 여기저기 자기들끼리 연결한다 정점(Vertex)과 간선(Edge)로 이루어진 자료구조이다 방향성 있는 그래프를 Directed Graph, 없는 그래프를 Undirected Graph 트리는 Directed Graph이다, 트리도 위 -> 아래로 화살표 그려줘야 하는데 편의상 생략한다 써클이 하나라도 있으면 Cyclic Graph, 없으면 Acyclic 그래프 ⚡️Graph를 표현하는 방법 Adjancency Matrix Adjancency List ❗️Adjancency Matrix, 2차원 배열에 표현 2차원 배열로 표현 후 서로 연결되어 있으면 1, 없으면 0으로 채움 ❗️Adjancency List, 배열.. 2023. 4. 6. [자료구조] 최소힙과 최대힙(Min-Heaps and Max-Heaps) ⚡️힙(Heap) 우선순위 큐(Priority Que)를 위하여 만들어진 완전 이진트리 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크거나 작은 이진트리를 말한다 최대값이나 최소값을 빠르게 구하기 위한 자료구조 힙은 일종의 반정렬 상태(느슨한 상태)를 유지한다 힙에서는 중복값을 허용한다 (이진 탐색 트리에서는 중복 값을 허용X) 최소 힙(Min Heap) : 부모 노드가 자신보다 작은 값을 갖는다 최대 힙(Max Heap) : 부모 노드가 자신보다 큰 값을 갖는다 시간 복잡도 O(log N) : 자식 노드로 접근할 때마다 시간이 절반씩 떨어진다 ✨ ROOT 노드를 출력한다면 ? 최소값 또는 최대값 출력이 된다 가장 마지막 노드가(leaf) 가 ROOT에 올라가고 자식 노드와 비교하면서 내려온다 2023. 4. 6. [자료구조] 트리의 종류(이진트리) 💡트리 부모와 자식간의 관계 계층이고 그룹이다 자식이 더 이상 없는 노드를 leaf라고 부름 💡트리의 종류 🎄 삼항트리(Ternary Tree) : 자식 노드가 3개 이상인 트리 🎄이진트리(Binary Tree) 이진트리(Binary Tree) : 노드가 최대 2개가 붙는 트리 이진탐색트리(Binary Search Tree) 왼쪽 자식 노드와 그 이하의 노드는 현재 노드보다 작아야 함 오른쪽 노드와 그 이상의 노드는 현재 노트보다 커야함 해당 노드보다 큰 값을 찾고 싶으면 오른쪽으로, 해당 노드보다 작은 값을 찾고 싶으면 왼쪽으로 이동 한단계 올라갈때마다 절반이 줄어들기 때문에, 시간복잡도는 O(log n)이다. 중복된 값 허용하지 않는다 🎄(밸런스) Balance 무조건 균형이 맞아야 하는게 아니라 어.. 2023. 4. 6. 이전 1 다음
