자료구조

자료구조

자료구조는 다수의 데이터를 효율적으로 담기 위한 구조입니다.

데이터의 수가 많아질수록 효율적인 자료구조가 필요하게 됩니다.

ex) 학생 수가 1만 명 이상인 학생 관리 프로그램에서는 효율적인 자료구조가 필수

 

자료구조의 필요성

• 효율성
  • 데이터가 많아질수록 적절한 자료구조를 사용하지 않으면 메모리와 자원의 낭비가 될 수 있습니다.
  • 효율적인 자료구조는 데이터의 저장, 검색, 삽입, 삭제 등의 작업을 빠르고 효율적으로 수행할 수 있게 합니다.
• 성능 측정
  • 자료구조와 알고리즘의 성능을 측정하고 이해하는 것은 중요합니다.
  • 성능 측정 기준에는 시간 복잡도와 공간 복잡도가 있으며, 이를 통해 알고리즘의 효율성을 평가할 수 있습니다.

 

자료 구조의 종류

• 선형 자료 구조(linear data structure)
  • 배열(array)
  • 연결리스트(linked list)
  • 스택(stack)
  • 큐(queue)
• 비선형 자료 구조(non-linear data structure)
  • 트리(tree)
  • 그래프(garaph)

 

선형 자료 구조

• 하나의 데이터 뒤에 다른 데이터가 하나 존재하는 자료 구조
• 데이터가 일렬로 연속적으로(순차적으로) 연결

비선형 자료 구조

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

 

프로그램 성능 측정 방법

시간 복잡도(time complexity)

알고리즘 사용되는 연산 횟수 측정

 

공간 복잡도(space comolexity)

알고리즘에 사용되는 메모리의 양을 측정

공간을 많이 사용하는 대신을 단축하는 방법이 흔히 사용된다.

 

Big-O 표기법

복잡한 표현할 때는 Big-O표기법을 사용

특정한 알고리즘이 얼만 ㅏ효율적인지 수치적으로 표현

가장 빠르게 증가하는 항만을 고려하는 표기법

 

프로그램 성능 측정 소요 시간

일반적으로 연산 횟수가 10억을 넘어가면 1초 이상의 시간이 소요

ex) n = 1000 일때 n² n³ n⁴ ... 갈수록 연산 횟수가 급수적으로 증가를 합니다.

 

현실적으로 동작 시간 1초 이내인 알고리즘을 설계한 필요성이 있습니다.