CS 전공지식/자료 구조3 3. 비선형 자료 구조 ✨비선형 자료 구조 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조를 말함 1. 그래프 정점과 간선으로 이루어진 자료 구조 정점과 간선 A에서 B로 C를 통해 간다고 했을 때 ‘B’는 정점(vertex)이 되고 ‘C’는 간선(edge)이다. 단방향 간선 : 한쪽으로만 이동 가능 양방향 간선 : 양쪽으로 이동 가능 정점으로 나가는 간선 : 해당 정점의 outdegree 들어오는 간선 : 해당 정점의 indegree 정점은 약자로 V 또는 U라고 하며, 보통 “U에서부터 V로 간다.”라고 표현 정점과 간선으로 이루어진 집합을 ‘그래프(graph)’라고 한다. 가중치 가중치는 간선과 정점 사이에 드는 비용 1번 노드와 2번 노드까지 가는 비용이 한 칸이라면 1번 노드에서 2번 노드까지의 가중치는 한 칸 .. 2023. 8. 23. 2. 선형 자료 구조 ✨ 선형 자료 구조 요소가 일렬로 나열되어 있는 자료 구조를 말함 1. 연결 리스트 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조 앞의 그림처럼 prev 포인터와 next 포인터로 앞과 뒤의 노드를 연결시킨 것이 연결 리스트이며, 연결 리스트는 싱글 연결 리스트, 이중 연결 리스트, 원형 이중 연결 리스트 등이 있다. 참고로 맨 앞에 있는 노드를 헤드(head)라고 한다. • 싱글 연결 리스트: next 포인터만 가짐 • 이중 연결 리스트: next 포인터와 prev 포인터를 가짐 • 원형 이중 연결 리스트: 이중 연결 리스트와 같지만 마지막 노드의 next 포인터가 헤드 노드를 가리키는 것 이 책에서는 이중 연결 리스트를 기반으로 설명하겠습니다. 이중 연결 리스트는 앞에.. 2023. 8. 23. 1. 복잡도 ⭐자료 구조(data structure) 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합 복잡도 종류 1. 시간 복잡도 2. 공간 복잡도 1. 시간 복잡도 (Time Complexity) ‘문제를 해결하는 데 걸리는 시간과 입력의 함수 관계’ 어떠한 알고리즘의 로직이 ‘얼마나 오랜 시간’이 걸리는지를 나타내는 데 쓰이며, 보통 빅오 표기법으로 나타낸다. 빅오 표기법 인도의 왕이 지혜로운 사람에게 상을 내리고 싶어 했는데, 이 사람은 체스판을 가득 채울 만큼의 밀알을 원했다. 조건은 체스판의 1알의 밀알을, 두번째 칸에는 2알의 밀알을, 세 번째 칸에는 4알의 밀알을... 이런 식으로 체스 판의 각 칸의 바로 이전 칸에 있는 밀알의 제곱한 양으로 채워지기를 바랐다. 왕은 흔쾌.. 2023. 8. 23. 이전 1 다음
