CS/자료구조 썸네일형 리스트형 [자료구조] 그래프(Graph) 개념 정리 그래프란? 그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조이다. 정확히는 정점(Vertex)간의 관계를 표현하는 조직도라고 볼 수 있다. 이러한 면에서 트리는 그래프의 일종인 셈이다. 하지만 그래프는 트리와는 달리 정점마다 간선이 있을 수도 있고 없을 수도 있으며, 루트노드와 부모와 자식이라는 개념이 존재하지 않는다. 그래프와 트리의 차이점에 대해서는 아래의 표로 좀 더 자세하게 설명하겠다. 그래프와 트리의 차이 그래프와 관련된 용어 정점(Vertex) : 노드(node) 라고도 하며 정점에는 데이터가 저장된다. (0, 1, 2, 3) 간선(Edge) : 정점(노드)를 연결하는 선으로 link, branch 라고도 부른다. 인접 정점(adjacent Vertex) : 간선에 의해 직접.. 더보기 [자료구조] 배열과 연결리스트 (Array & LinkedList) 배열 vs 연결리스트 배열 배열은 입력된 데이터들이 메모리 공간에서 연속적으로 저장되어 있는 자료구조이다. 메모리상에서 연속적으로 저장되어 있는 특징을 갖기때문에, index를 통한 접근이 용이하다. 배열의 크기는 처음 생성할 때 정하며 이후에는 변경할 수 없다. 시간복잡도 탐색: O(1) 단, 접근하고자 하는 인덱스를 알고있어야 한다. 순차적으로 탐색시에는 O(n) 삽입 및 삭제: 배열의 처음 또는 중간에 삽입 및 삭제: O(n) 삽입 지점 이후의 데이터를 옮겨야 하기 때문이다. 배열의 끝에 삽입 및 삭제: O(1) 연결리스트 연결리스트는 여러 개의 노드들이 순차적으로 연결된 형태를 갖는 자료구조이며, 첫번째 노드를 헤드(Head), 마지막 노드를 테일(Tail) 이라고 한다. 각 노드는 데이터와 다음.. 더보기 이전 1 2 다음
