[자료구조] 자료구조란?

  자료구조(Data Structure)는 일련의 동일한 타입의 데이터를 정돈하여 저장한 구성체입니다. 데이터를 정돈하는 목적은 프로그램에서 저장하는 데이터에 대해 접근, 탐색, 삽입, 삭제 등의 연산을 효율적으로 수행하기 위해서이며, 자료구조를 설계할 때는 데이터와 데이터와 관련된 연산을 함께 고려하여 설계해야 합니다.

  자료구조의 효율성은 자료구조에 저장된 데이터에 대해 수행되는 연산의 수행 시간으로 측정합니다. 자료구조에 대한 연산 수행 시간 측정 방식은 알고리즘의 성능을 측정하는 방식과 동일합니다. 알고리즘의 성능은 수행 시간을 나타내는 시간 복잡도(Time Complexity)와 알고리즘이 수행되는 동안 사용되는 메모리 공간의 크기를 나타내는 공간 복잡도(Space Complexity)에 기반하여 분석합니다. 알고리즘의 수행 시간은 다음과 같이 네 가지의 방법으로 분석할 수 있습니다.

• 최악 경우 분석(Worst-case Analysis)
• 평균 경우 분석(Average-case Analysis)
• 최선 경우 분석(Best-case Analysis)
• 상각 분석(Amortized Analysis)

 

  수행 시간은 알고리즘(또는 자료구조 연산)이 수행하는 기본 연산 횟수를 입력 크기에 대한 함수로 표현합니다. 이를 간단히 표현하기 위해 점근 표기법(Asymptotic Notation)을 사용합니다. O(Big-Oh: nₒ과 같거나 큰 모든 n에 대해서 f(n)이 cg(n)보다 크지 않다는 것을 의미), Ω(Big-Omega: nₒ보다 큰 모든 n에 대해서 f(n)이 cg(n)보다 작지 않다는 의미), Θ(Theta: 수행 시간의 O─표기와 Ω─표기가 동일한 경우)로 표기할 수 있습니다. 알고리즘의 수행 시간은 주로 O─표기를 사용하며, 표기와 이름은 다음과 같습니다.

표기	이름	알고리즘 예시
O(1)	상수 시간 (Constant Time)	정수(이진수로 표현되는)가 짝수이거나 홀수인지 결정
O(log n)	로그(대수) 시간 (Logarithmic Time)	이진탐색
O(n)	선형 시간 (Linear Time)	정렬되지 않은 배열에서 가장 작은 수 또는 가장 큰 수를 탐색
O(n log n)	로그 선형 시간 (Log-linear Time)	가장 빠른 비교정렬
O(n^2)	이차 시간 (Quadratic Time)	버블 정렬, 삽입 정렬
O(n^3)	삼차 시간 (Cubic Time)	n x n 행렬 두 개의 곱셈
O(2^n)	지수 시간 (Exponential Time)	브루트 포스 탐색을 통한 연쇄 행렬 곱셈

 

  재귀 호출이라고도 하는 순환(Recursion)은 메소드의 실행 과정 중 메소드 자신을 호출하는 것이다. 순환은 팩토라얼, 조합을 계산하기 위한 식의 표현, 무한한 길이의 숫자 스트림 만들기, 분기하여 자라나는 트리 자료구조를 만드는 데 사용되며, 프랙털 등 기본 개념으로도 사용됩니다.

  메소드가 자기 자신을 호출하려면 무한 호출을 방지해야 합니다. 순환으로 구현된 메소드는 두 부분으로 구성됩니다. 하나는 기본(Base) case이고, 다른 하나는 순환 case입니다. 기본 case는 스스로를 더 이상 호출하지 않는 부분이고, 순환 case는 스스로를 호출하는 부분입니다. 무한 호출을 방지하기 위해 선언한 변수 또는 수식의 값이 호출이 일어날 때마다 순환 case에서 감소되어 최종적으로 if-문의 조건식에서 기본 case를 실행하도록 제어해야 합니다.

  일반적으로 순환은 프로그램(알고리즘)의 가독성을 높일 수 있지만 시스템 스택을 사용하기 때문에 메모리 사용 측면에서 비효율적입니다. 그러나 반복문으로 변환하기 어려운 순환도 존재하며, 반복문으로 변환된 프로그램의 수행 속도가 순환으로 구현된 프로그램보다 항상 빠르다는 보장도 없습니다.

 

  ※ "자바와 함께하는 자료구조의 이해"라는 책을 참고하여 쓴 게시글입니다. 문제가 되거나 부정확한 부분이 있다면 알려주시면 감사하겠습니다.

  ※ 책은 게시글보다 정확한 내용을 담고 있으며 코드, 그림, 예제를 이용하여 개념을 자세히 설명합니다.