Computer Science/Data Structure6 [자료구조] Graph 개념과 DFS, BFS [자료구조 알고리즘] 그래프(Graph)에 대해서 [자료구조 알고리즘] Graph 검색 DFS, BFS 구현 in Java 본 포스팅은 위의 영상들을 정리한 글로 개인 공부를 목적으로 작성되었습니다. Graph란 정점(vertex)와 edge(정점과 정점을 연결하는 간선)으로 구성된 한정된 자료구조이다. 만약 이전에 배웠던 트리가 루트도 없고 자식도 없고 방향성이 없어진다면 뭐가 될까? 그게 바로 그래프이다. 사실 트리는 그래프의 한 형태로 단지 사이클이 없고 방향이 정해져있다는 조건이 있는 상태인 것이다. Graph의 특성 1. Directed VS Undirected 그래프는 방향이 있을 수도 있고 없을 수도 있다. 방향이 있는 그래프는 Directed Graph, 없는 그래프는 Undirected .. 2022. 9. 20. [자료구조] Binary Tree의 3가지 순회방법 [자료구조 알고리즘] Binary Tree의 3가지 순회방법 구현하기 본 포스팅은 위의 영상을 정리한 글로 개인 공부를 목적으로 작성되었습니다. Binary Tree의 3가지 순회방법 바이너리 트리를 판단하면서 트리의 모든 데이터를 가져오는 방법에는 세 가지가 있다. - Inorder(Left -> Root -> Right) - Preorder(Root -> Left -> Right) - Postorder(Left -> Right -> Root) 예제 Inorder (Left, Root, Right) : 4 2 5 1 3 1. 루트 노드를 시작으로 왼쪽으로 먼저 향한다. 2. 더 이상 차일드 노드가 없는 4를 출력한다. 3. 왼쪽 다음 root인 2을 출력한다. 4. 오른쪽으로 가서 더이상 차일드 노드가.. 2022. 9. 20. [자료구조] Tree의 종류 [자료구조 알고리즘] Tree의 종류 본 포스팅은 위의 영상을 정리한 글로 개인 공부를 목적으로 작성되었습니다. 들어가기 전에 자료구조가 어떻게 분류되는지 먼저 생각하기! Tree란 그동안 우리가 배운 Array, Linked List, Stack, Queue 는 라인처럼 생긴 일직선 데이터 구조(linear)이다. 하지만 트리는 부모, 자식 구조를 가진 구조로 계층이 있고 그룹이 있다. 어떻게 이게 가능한가? 노드가 하나 이상의 차일드를 갖기 때문이다. 트리의 노드 중에는 부모를 아는 경우도 있고 자식만 아는 경우도 있고 어떤 특정한 순서에 의해서 데이터가 관리되는 경우도 있고 데이터가 섞여있는 경우도 있다. 참고로 트리의 맨 끝에 더이상 자식이 없는 노드를 leaf라고 부른다. 종류 1. 이진트리(B.. 2022. 9. 20. [자료구조] Queue 개념과 Java 구현 Queue란? 스택과 마찬가지로 메모리 안 데이터들을 더욱 효율적으로 다루기 위해 만들어진 데이터 참조 방식으로 스택과는 반대로 가장 먼저 들어온 데이터가 먼저 나가는 구조(FIFO, First In First Out)를 가진 자료구조이다. 버스 정류장에서 버스를 타기 위해 줄을 서면 먼저 온 사람이 먼저 버스를 타는 과정을 생각하면 된다. 큐의 예로는 이메일 전달 혹은 푸쉬 알림 기능 그리고 전화 온 순서대로 상담을 처리하는 콜센터를 생각할 수 있다. Java에서 제공하고 있는 Queue는 인터페이스이고 Queue interface를 구현하는 라이브러리는 크게 ArrayDeque, LinkedList, PriorityQueue가 있다. 보통은 자바에서 다음과 같이 사용한다. Queue q = new L.. 2022. 9. 13. [자료구조] Stack 개념과 Java 구현 & 사용법 예제 Stack이란? 메모리 안에 데이터들을 효율적으로 관리하게 도와주는 자료 참조 방식 중 하나이다. 단어의 의미가 '쌓아서 올린다', '더미'인 것처럼 택배 상자가 쌓이는 모습을 상상하면 되는데 제일 마지막에 들어온 데이터가 가장 먼저 나가는 LIFO(Last In First Out) 구조를 가진 자료구조이다. 한 쪽 끝에서만 데이터를 넣거나 뺄 수 있는 선형 구조이다. 스택의 예로는 'Ctrl + Z' 즉, 실행 취소를 들 수 있다. 누를 때마다 최근에 한 작업이 실행 취소된다. 그외에는 웹브라우저 뒤로 가기 기능이나 계산기 등이 있다. Stack의 주요 기능 1. pop() : 스택에서 가장 위에 있는 항목을 꺼낸다. 2. push(item) : item을 스택의 가장 위에 추가한다. 3. peek().. 2022. 9. 12. [자료구조] LinkedList 개념과 Java 구현 & 사용법 예제 LinkedList란 각 노드가 데이터(Data field)와 포인터(Link field)를 가지고 한 줄로 연결되어 있는 방식의 자료구조이다. 데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전 노드와 다음 노드와의 연결을 담당한다. 장점 삭제, 삽입해야 할 경우 노드의 링크를 끊거나 연결하면 되기 때문에 효율적이다. 단점 요소를 검색해야 하는 경우 첫 노드(HEAD)부터 찾으려는 노드가 나올 때까지 연결된 노드들을 모두 찾아봐야 하기 때문에 성능이 떨어진다. ArrayList와의 차이점 1. 데이터를 삽입할 때 ArrayList는 인덱스의 값을 당기거나 미는 행위를 해야 하지만 노드는 링크를 끊고 연결하면 되기 때문에 속도가 빠르다. 2. ArrayList는 Random Access가 .. 2022. 9. 11. 이전 1 다음
