본문 바로가기
반응형

그래프3

[Data Structure] 자료구조란? 기본 자료 구조 - 배열(Array), 링크드리스트(LinkedList), 스택(Stack), 큐(Queue), 해시 테이블(Hash Table), 그래프(Graph), 트리(Tree) 자료구조란? - 대량의 데이터를 효율적으로 관리할 수 있는 데이터 구조 - 프로그래밍에서 데이터 특정에따라 어떤 데이터 구조를 사용하느냐에 따라 코드 효율이 달라진다. 배열(Array) - 같은 종류의 데이터를 순차적으로 연결된 공간에 나열하는 자료 구조 - 각 데이터를 인덱스에 대응하도록 구성한다. 장점 첫 데이터의 위치에서 상대적인 위치(인덱스 번호)로 데이터를 접근하므로, 빠른 접근이 가능하다. - 인덱스 위치를 안다면, 상수 시간으로 접근 가능하다 O(1) 단점 데이터의 길이가 정해져있으므로, 크기 이상의 데이터를 저장할 때 새로운 배열을 만들어야한다. 링크드리스트( LinkedList) - 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조 배열, 순차적으로 연결된 공간에 데이.. 2021. 12. 29.
[Algorithm] 그래프 이론: 트리, 서로소, 신장 트리, 크루스칼 알고리즘, 위상 정렬 학습 목표 · 그래프(Graph)란? · 트리(Tree)란? · 서로소 집합 - 서로소 집합 자료구조 - 문제점 - find 함수 개선: 경로 압축 기법 - 서로소 집합을 활용한 사이클 판별 · 신장 트리(Spanning Tree) - 최소 신장 트리 알고리즘 - 크루스칼 알고리즘 · 위상 정렬 · DFS/BFS, 최단 경로 알고리즘은 그래프 알고리즘의 한 유형 · 크루스칼 알고리즘 - 그리디 알고리즘, 위상 정렬 알고리즘 - 큐 자료 구조 or 스택 자료구조를 활용하여 구현 그래프(Graph)란? · 노드(Node)와 노드 사이에 연결된 간선(Edge)의 정보를 가지고 있는 자료구조 · 그래프를 구현하는 2가지 방식: 1. 인접 행렬(Adjacency Matrix): 2차원 배열을 사용하는 방식 ex).. 2021. 11. 3.
[Algorithm] DFS와 BFS를 이해하기 위한 기본 지식들 - 탐색, 스택(Stack)과 큐(Stack), 재귀 함수, 그래프(Graph) DFS와 BFS를 이해하기 위한 기본 지식들 - 탐색, 스택과 큐, 재귀 함수 '이것이 취업을 위한 코딩 테스트다 with 파이썬'을 공부 중입니다. 이 글은 해당 서적을 통해 DFS와 BFS를 이해하기 위한 기본 지식을 공부한 내용입니다. 또한 책의 코드를 모두 자바로 변환하여 글을 작성했습니다. 학습 목표 ㆍ탐색(Search) ㆍ자료구조 - 스택과 큐 ㆍ재귀 함수 ㆍ그래프 탐색(Search) 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘으로 DFS, BFS가 있다. 자료구조 - 스택과 큐 자료구조는 ‘데이터를 표현하고 관리하고 처리하기 위한 구조’를 의미한다. 그중 .. 2021. 1. 24.
반응형

티스토리툴바