▶배열(array)
같은 자료형을 갖는 여러 데이터를 하나의 변수 이름으로 모아놓은 데이터의 집합
또는 (인덱스,값) 쌍의 집합
▶연결 리스트(linked list)
노드(하나 이상의 데이터 필드와 하나 이상의 링크 필드로 구성)라는 저장구조를 연결해서 선형 리스트를 구현하는 방법
▶스택(stack)
한쪽 끝에서만 데이터의 삽입과 삭제가 수행되는 선형 리스트. 후입선출(LIFO) 리스트라고도 함
▶트리(tree)
노드라는 정보 항목이 간선으로 연결되어 계층적인 구조를 표현하는 비선형 자료구조
▶그래프(graph)
그래프 G=(V,E)는 도형으로 표현되는 비선형 자료구조로서, 연결할 객체를 나타내는 정점의
집합 V와 정점을 연결하는 간선의 집합 E로 구성됨
[ 알고리즘의 필요성 ]
▶컴퓨터를 이용해서 주어진 문제를 해결하기 위해서는, 문제 해결에 필요한 절차와 방법이 반드시 필요하고, 이를 간단히 알고리즘
[ 배열과 연결 리스트 ]
▶배열: 같은 자료형을 갖는 여러 데이터를 하나의 변수 이름으로 모아놓은 데이터의 집합체 → “논리적 순서 = 물리적 순서” → 인덱스를 통한 직접적인 원소 접근, 삽입/삭제 시 자료의 이동에 따른 오버헤드 발생으로 빈번한 삽입/삭제 연산이 필요한 응용에는 부적합
▶연결 리스트: 노드(하나 이상의 데이터 필드와 하나 이상의 링크 필드로 구성)라는 저장구조를 이용해서 선형 리스트를 표현하는 방법 → “논리적 순서 ≠ 물리적 순서” → 링크 필드의 조정을 통한 비교적 간단한 삽입/삭제 연산, 순차 접근
[ 스택과 큐 ]
▶스택: 한쪽 끝에서만 데이터의 삽입과 삭제가 수행되는 선형 리스트 → LIFO, push 연산, pop 연산, top
▶큐: 한쪽 끝에서는 데이터의 삽입만 수행되고 다른 한쪽 끝에서는 삭제만 수행되는 선형 리스트 → FIFO, front, rear
[ 트리와 그래프 ]
▶트리: 노드라는 정보 항목이 간선으로 연결되어 계층적인 구조를 표현하는 비선형 자료구조 → 용어(노드의 차수, 트리의 차수, 리프 노드 또는 단말 노드, 비단말노드, 부모 노드, 자식 노드, 형제 노드, 후손, 조상, 레벨, 높이/깊이, 숲)
▶이진 트리: 각 노드의 차수가 2 이하인 순서 트리 → 특징(레벨i에서의 최대 노드 개수: 2i, 높이 h인 트리의 최대 노드 개수: 2h-1, n0=n2+1) → 종류(포화 이진 트리, 완전 이진 트리, 전 이진 트리 등)
▶그래프: G=(V,E) → 용어(인접, 부수, 부분 그래프, 경로, 경로의 길이, 차수, 단순 경로, 사이클, 루프, 연결, 강력 연결, 약하게 연결) → 종류(무방향 그래프, 방향 그래프, 가중 그래프) → 구현 방법(인접 행렬, 인접 리스트)
