비선형 자료 구조 비선형 자료 구조는 데이터 요소들이 선형적으로 나열되어 있지 않고 계층적인 구조를 의미한다. 그래프 정점(Vertex)과 간선(Edge)으로 이루어진 자료 구조를 의미한다. 그래프 저장 방법 1. 인접 행렬 : 정점과 간선의 관계를 2차원 행렬로 표현, 공간 복잡도 : O(V^2) 2. 인접 리스트 : 정점과 간선이 주어졌을 때 2차원 ArrayList로 표현, 공간 복잡도 : O(E) 트리 정점들이 계층적인 구조를 가지고 있는 비선형 자료 구조이다. 하나의 루트 노드 에서 시작하여, 부모-자식 관계를 가지는 노드들로 구성되어 있다. 반드시 노드가 N인 트리는 항상 N-1개의 간선을 가진다. 노드의 종류 루트 노드 : 최상단에 있는 노드 내부 노드 : 루트 노드와 리프 노드 사이에 있는..
선형 자료 구조 선형 자료 구조는 데이터 요소들이 선형적으로 나열되어 있는 자료 구조로, 각 요소들이 순서에 따라 배치되어 있는 것을 의미한다. 연결 리스트(Linked List) 각 요소가 데이터와 다음 요소를 가르키는 포인터로 이루아진 선형 자료 구조이다. 메모리 상에 불연속적으로 저장되며, 삽입과 삭제가 O(1)으로 빠르지만, 특정 위치 요소에 접근하는데는 순차적으로 탐색해야 하기 때문에 검색 O(n)으로 느리다. 배열(Array) 동일한 데이터 타입의 요소들이 메모리 상에 연속적으로 저장되는 선형 자료 구조이다. 인덱스를 이용하여 특정 위치 접근이 가능하여 빠른 검색이 가능하다. 메모리 할당이 연속적이기 때문에 빠른 데이터 접근이 가능하다. 크기가 고정되어 있기 때문에 크기 변경이 어렵고, 요소를..
자료구조 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합을 의미한다. 시간복잡도 "문제를 해결하는 데 걸리는 시간과 입력의 함수 관계" 를 가르킨다. 로직이 얼마나 오랜 시간이 걸리는지를 나타내는 데 사용한다. 보통 빅오 표기법으로 나타낸다. 빅오 표기법 O(n) 기호로 표기 입력 범위 n을 기준으로 로직이 몇 번 반복되는지 나타낸다. 시간 복잡도의 존재 이유 효율적인 코드로 개선하는 데 쓰이는 척도가 된다. O(n^2) = 9초를 개선하여 O(n) = 3초가 걸리게 할 수 있다. 시간 복잡도 비교 O(n^2) > O(n) > O(logN) > O(1) 공간복잡도 프로그래밍을 실행시켰을 때 필요로 하는 자원 공간의 양을 의미한다. 정적 변수로 선언된 것 말고도 동적으로 재귀..
