자료구조란?

자료구조란 다수의 자료(data)를 담기 위한 구조다. 데이터가 많아질수록 더 효율적인 구조가 필요하다. 컴퓨터는 각각의 정보를 문자열과 같은 형태로 기록하는데, 그 수가 많아지면 효율적인 구조로 저장하지 않는다면 많은 메모리 낭비가 있을 수 있다.

자료구조의 필요성

성능 비교

• 자료구조/알고리즘의 성능 측정 방법에 대해 이해할 필요가 있다.
• 만약 A 자료구조는 삽입과 추출이 적당한 속도이고 B 자료구조는 삽입은 느리지만 추출이 빠르다면?
• 데이터를 효과적으로 저장하고 처리하는 방법에 대해 이해할 필요가 있다.
• 그렇지 않는다면 불필요하게 메모리와 계산을 낭비할 수 있다.

자료구조의 종류

1. 선형 구조
   선형 자료구조는 하나의 데이터 뒤에 다른 데이터가 하나 존재하는 구조이다. 데이터가 일렬로 연속적으로(순차적으로) 연결되어 있다.

• 배열 - Array
• 연결 리스트 - Linked List
• 스택
• 큐

2. 비선형 구조
   하나의 데이터 뒤에 다른 데이터가 여러개 올 수 있는 자료구조다. 데이터가 일직선상으로 연결되어 있지 않아도 된다.

• 트리
• 그래프

프로그램의 성능 측정 방법

1. 시간 복잡도 - 알고리즘에 연산되는 연산 횟수를 측정

2. 공간 복잡도 - 알고리즘에 사용되는 메모리의 양을 측정

보통 공간을 많이 사용하는 대신 시간을 줄이는 방법을 많이 사용한다.