BFS2 비선형 자료구조 - 그래프 비선형 자료구조- 순차적으로 나열되는 것이 아닌 앞,뒤의 관계가 1:N, N:N인 자료구조ex. 그래프, 트리 왜 비선형 자료구조를 사용할까?- 더 많은 정보를 담고- 많은 정보를 담은 상태에서 더 빨리 탐색하기 위함 그래프- 노드(정점) + 간선 으로 연결관계를 표현하는 자료구조 그래프 특징 1. 방향성- 간선에 방향성 추가 (기존 A - B, 방향성 추가 A -> B )- 방향성이 추가되면서 한 쪽 방향으로의 접근만 가능해짐- 해당 연결성을 확인하기 위해 Floyd - Warshall 알고리즘 활용 2. 가중치- 간선에 가중치(비용) 추가- 가중치 + 방향 성분이 모두 포함된 그래프 -> 네트워크- 가중치 개념이 추가되면서 기존에 없던 minimum cost 를 확인해야하는 문제 발생 -> 최소 .. 2025. 1. 8. 선형 자료구조 선형 자료구조- 데이터를 순차적으로 저장 (각 데이터가 1:1로 연결되는 방식)- 배열, 링크드 리스트, 스택, 큐배열연속적인 메모리 공간에 순차적으로 저장되는 자료구조 특징- 모든 요소가 같은 타입>>> 연속적인 메모리 공간에 데이터들이 존재하고, 데이터들의 타입이 같으니 O(1)로 시간 복잡도로 랜덤 접근 가능- Sequence와 Collection 프로토콜을 채택하고 있는 컬렉션 타입 Capacity- 새로운 저장공간 없이 배열이 포함할 수 있는 요소의 개수- 초기화 시점에 요소의 개수만큼 capacity 설정- capacity를 넘어가게 되면 기존 capacity의 약 2배 크기의 새로운 공간을 만든 후 기존 배열을 복사하고 요소 추가- reserveCapacity 메서드를 활용하여 불필요한 배열.. 2024. 12. 18. 이전 1 다음
