CS 지식/자료구조_알고리즘4

• MST - Kruskal MST Kruskal MST MST란, Minimum Spanning Tree의 약자로, 최소 신장 트리라는 뜻을 가진 알고리즘을 의미한다. 해당 그래프에서 모든 point들이 edge들로 연결된다고 가정했을 때, 가중치가 가장 짧은 방법을 구하는 알고리즘이다. ex) Kruskal(크루스칼) 알고리즘, Prim(프림) 알고리즘 Kruskal(크루스칼) Kruskal이란, MST의 종류 중 하나로, 모든 정점을 최소 비용으로 연결하는 방법을 구하는 알고리즘이다. 그래프의 간선들의 가중치를 오름차순으로 정렬한다. 정렬된 간선 리스트에서 사이클을 형성하지 않는 간선을 선택한다. 해당 간선을 MST의 집합에 추가한다.ex) 백준의 1197번, 1922번, 1647번... 자바로 구현한 Kruskal 알고리즘 .. CS 지식/자료구조_알고리즘 2022. 7. 4.

• Tree Tree Tree(트리) 데이터들을 나무를 뒤집은 형태로 저장한다. 부모와 자식 노드들로 이루어진다. 차수 : 어떠한 노드가 가지고 있는 자식 노드들의 개수 이진 트리 : 차수가 2인 트리 ex) 인덱스 트리 : 자식 노드들의 구간 합이 부모 노드에 저장된 값 정렬 상태를 유지할 수 있다. Heap 구조의 트리이다. (저장된 값 중 최소/최대 값을 리턴하고, 나머지를 정렬하여 저장한다.) 시간복잡도 : 트리의 높이만큼 걸린다. O(Log(N)) KEY WORD : 이진 트리, 노드, 부모 노드, 자식 노드, O(Log(N)) CS 지식/자료구조_알고리즘 2022. 6. 24.

• Stack vs Queue Stack vs Queue Stack(스택) FILO(First In Last Out) 구조로 이루어진 자료구조이다. 데이터를 삽입(push) 할 때, 자료구조의 맨 뒤에 붙게 되고, 데이터를 호출(pop) 할 때, 자료구조의 맨 뒤의 값이 빠져나오게 된다. ex) 웹 브라우저의 방문기록 KEY WORD : FILO Queue(큐) FIFO(First In First Out) 구조로 이루어진 자료구조이다. 데이터를 삽입(add) 할 때, 자료구조의 맨 뒤에 붙게 되고, 데이터를 호출(poll) 할 때, 자료구조의 맨 앞의 값이 빠져나오게 된다. ex) 선착순 시스템 KEY WORD : FIFO CS 지식/자료구조_알고리즘 2022. 6. 24.

• Array vs LinkedList Array vs LinkedList Array(배열) 데이터들을 옆으로 나란하게 저장한다. 메모리 내의 연속된 주소에 저장한다. 사용하기 전 미리 할당을 받아 사용한다. -> 할당된 공간 사용하지 않는 경우, 메모리 자원 부족할 수 있다. -> 할당된 공간보다 더 필요한 경우, 새로 만들어 복사해야 한다. 값의 입출력 용이, 중간에 값 삽입/삭제 불편 속도가 빠르다. ex) 한 학급의 학생들의 키 (학급에 학생을 삽입/삭제 할 경우가 많지 않기 때문이다.) KEY WORD : 정적 할당, 연속 저장 LinkedList(연결리스트) 저장된 값과 다음 값을 연결하면서 값들을 저장한다. 필요한 만큼 할당 받아서 연결한다. 데이터 중간에 삽입/삭제가 용이하다. 물리적 속도가 느리다. ex) 도서관리 프로그램 (.. CS 지식/자료구조_알고리즘 2022. 6. 24.