TL;DR 그래프란 정점(노드)와 간선(엣지)로 이루어진 자료구조로 정점 간의 관계를 나타내는 자료구조다. 구현 : 인접 행렬과 인접 리스트 그래프 탐색 : 하나의 정점으로부터 차례로 모든 정점들을 한 번씩 방문하기 너비 우선 탐색 BFS 깊이 우선 탐색 DFS 그래프 최단 경로 다익스트라 Dijkstra 플로드 와샬 Floyd-Washall 밸만 포드 Bellman-Ford 유니온 파인드 : 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조. union과 find 2개의 연산으로 조작 최소 스패닝 트리 : 그래프의 모든 정점이 사이클 없이 연결된 간선 합이 최소인 스패닝 트리 크루스칼과 프림 알고리즘으로 구현할 수 있다. 그래프 Graph 그래프는 정점(노드)와 간선(엣지)로 이루..

TL;DR 코딩테스트에서는 굉장히 중요한 자료구조지만, 면접에서 단독으로 물어보는 경우는 많지 않다. 스택 Stack 스택은 마지막에 들어온 데이터를 먼저 내보내는 후입선출(LIFO)의 자료구조다. 새로운 원소를 스택의 가장 위에 삽입(push)하고, 가장 위의 원소를 삭제(pop)한다. 장점 : top을 통해 접근하기 때문에 데이터 접근, 삽입, 삭제가 빠르다. 단점 : top 위치 외의 데이터에 접근할 수 없어 탐색이 불가능하다. 활용 예시 : 웹 브라우저 방문기록(뒤로가기), 깊이 우선 탐색(DFS) ✅ 연산과 시간복잡도 top 포인터 1개로 삽입/ 삭제 전부 처리하고, 모든 연산은 $O(1)$ 시간복잡도를 갖는다. push() : 새로운 원소 삽입 pop() : 마지막 원소 삭제 top() : 마..

TL;DR 구현상 어떤 특징이 있는지, 시간복잡도가 어떤지, 어떤 경우에 사용하면 좋은지 3가지 포인트 기억하기! 배열과 링크드 리스트의 가장 큰 차이점은 메모리에 저장되는 방식과 이에 따른 연산 속도다. 배열 Array 배열은 정적 자료구조로 연관된 데이터를 연속된 메모리에 미리 할당된 크기만큼 저장하는 자료구조다. 👆 정적이란? 메모리 공간에 미리 사이즈를 할당한다는 의미 ex) 자바의 경우에는 int[] array = new int[5] 와 같이 선언한다. 여기서 []안의 5가 미리 할당하려는 사이즈를 의미한다. 미리 메모리 공간을 할당받기 때문에 컴파일 단계에서 stack 영역에 메모리 할당이 일어난다. 장점 : 메모리 상에서 연속적으로 저장되어 있기 때문에, 인덱스(index) 접근이 가능해 접..

TL;DR 트리 Tree 트리는 모양이 뒤집힌 나무와 같다고해서 붙은 이름으로 계층적 데이터를 나타내는 노드들의 집합이다. 트리의 가장 중요한 속성은 '루트노드를 제외한 모든 노드는 단 하나의 부모노드를 갖는다'는 것이다. 이 속성 때문에 다음과 같은 성질을 만족한다. 임의 노드에서 다른 노드로 가는 경로(path)는 유일하다. 순환하지 않는다. (cycle이 없다.) 모든 노드는 서로 연결되어 있다. 엣지를 하나 자르면 트리가 두 개로 분리된다. = 트리 안에 또 다른 트리가 있는 재귀적 자료구조다. 엣지의 수 = 노드의 수 - 1 비선형 자료구조다. 👆 선형 자료구조란? 자료들 간의 앞뒤 관계가 1:1인 자료구조로 배열, 링크드리스트, 스택, 큐 등이 있다. 👆 비선형 자료구조란? 자료들 간의 앞뒤 ..