1. 자료구조란?
자료구조(data structure)란 자료(데이터) 처리를 위한 자료의 표현, 저장, 관계, 관리 및 이용에 관한 방법을 이해하여 자료가 프로그램에 사용되고 컴퓨터에 의해 처리될 때 어떻게 적절한 알고리즘을 사용하여 자료를 표현하고 구성하고, 저장할 지를 배우는 학문입니다. 자료구조론은 크게 이론분야와 응용분야로 나눌 수 있는데, 이론 분야에서는 여러 수학적인 이론(이산수학, 확률 등)을 바탕으로 하여 자료구조 혹은 알고리즘 분석을 수학적으로 행하고 그 결과를 검색 및 정렬 작업 그리고 저장 공간 및 수행시간 단축 등의 분야에 이용합니다. 반면 응용분아에서는 리스트, 제한된 리스트, 트리, 그래프, 파일 등과 같은 실제적인 자료구조를 연구하고 알고리즘을 개발하여 프로그래밍, 파일 설계, 메모리 관리, 고급 언어 및 운영체제의 설계 등에 이용합니다.
2. 자료구조의 형태 분류
물건을 정리해놓으면 깔끔하여 필요한 물건을 찾기도 쉽습니다. 컴퓨터도 마찬가지입니다. 컴퓨터가 효율적으로 문제를 처리하기 위해서는 자료를 보관하고 정리하는 기술이 필요한데 컴퓨터는 자료의 특성에 따라 다양한 자료구조 기법을 사용합니다. 자료구조에는 단순구조, 선형구조, 비선형구조, 파일구조가 있습니다.
단순구조는 정수, 실수, 문자, 문자열 등 자료의 형태를 말합니다. 선형 구조는 자료 간의 연결 관계가 [1:1] 관계를 가지는 형태로 자료들이 기다란 선처럼 연결되어 있는 구조입니다. 비선형구조는 자료 간의 연결 관계가 [하나 : 여러 개] 또는 [여러 개 : 여러 개] 의 관계를 가지는 형태로, 나뭇가지 모양이나 그물 모양처럼 얽혀 있는 구조입니다. 예를 들어, 엑셀로 각 과목 점수를 정리하는 표를 만들 때 사용하는 자료구조는 선형구조 중에서 '리스트'라는 구조입니다. 리스트는 순서가 정해져있는 목록의 자료구조 입니다. 지하철 노선도를 정리할 때 사용하는 자료구조는 비선형 구조의 '그래프'라는 구조입니다. 다양하고 복잡한 연결 구조들을 표현할 때 사용합니다.
대부분의 컴퓨터 프로그램은 알고리즘 + 자료구조의 형태로 이루어집니다. 알고리즘이 특정한 목적을 달성하기 위한 절차라고 한다면 자료구조는 알고리즘에 필요한 데이터의 집합입니다. 동일한 알고리즘이라도 자료구조가 달라지면 전혀 다른 프로그램이 될 수 있기 때문에 자료에 알맞은 자료구조를 만드는 것이 매우 중요합니다.
출처 : [네이버 지식백과] 자료구조 [data structure]
위 지식백과에서 볼 수 있듯이 컴퓨터 내의 자료구조의 형태는 다음과 같이 단순구조/선형구조/비선형구조/파일구조와 제한된자료구조/추상자료구조로 나눌 수 있습니다.
- 단순구조(simple structure) : 문자(character), 문자열(string), 논리형(logical), 포인터(pointer), 정수(integer), 실수(real)
- 선형구조(linear structure) : 배열(array), 단순 연결 리스트(single linked list), 원형 연결 리스트(circular linked list), 이중 연결 리스트(doubly linked list), 이중 원형 연결 리스트(doubly circular linked list), 스택(stack), 큐(queue), 데크(deque)
- 비선형구조(non-linear structure) : 트리(tree), 그래프(graph)
- 파일구조(file structure) : 순차파일(sequential file), 색인파일(indexed file), 직접파일(direct file)
자료 추상화는 불필요한 정보는 숨기고 중요한 정보만을 표현함으로써 프로그램을 간단히 만드는 것입니다. 자료 추상화를 통해 정의된 자료형을 추상 자료형이라고 합니다. 추상 자료형은 자료형의 자료 표현과 자료형의 연산을 캡슐화한 것으로 접근 제어를 통해서 자료형의 정보를 은닉할 수 있습니다. 객체 지향 프로그래밍에서 일반적으로 추상 자료형을 클래스, 추상 자료형의 인스턴스를 객체, 추상 자료형에서 정의된 연산을 메소드(함수), 메소드의 호출을 생성자라고 한다.
좋은 자료구조와 좋은 알고리즘의 전제하에 좋은 프로그램이 구현 가능합니다. 그렇다면 좋은 자료구조와 좋은 알고리즘은 무엇일까요? 무엇이 적절한 자료구조의 선택 기준이 될까요?
3. 시간 복잡도
적절한 자료구조의 선택 여부가 프로그램이나 시스템 성능 향상에 깊이 관여하므로, 다음과 같은 선택 기준을 고려해야 합니다.
- 자료의 양
- 자료의 활용 빈도
- 자료의 갱신 정도
- 사용 가능한 기억 용량(메모리)
- 처리 시간의 제한성
- 프로그래밍의 용이성
결과적으로 자료구조론에서 다루는 여러 가지 응용문제는 간단히 프로그램 수행시간의 길이와 그 수행 시 요구 되는 메모리 크기의 절충작업으로 간주할 수 있습니다. 알고리즘에서 시간 복잡도는 명령문의 실행 빈도수를 기반으로 계산합니다. 자료구조와 알고리즘은 밀접한 관련이 있으므로, 명령문의 실행 빈도수를 계산하는 시간 복잡도는 좋은 자료구조를 판단하는 중요한 기준이 됩니다. 시간 복잡도는 3가지 표시 방법(빅-오 표기법/빅-오메가 표기법/빅-세타 표기법)으로 나타낼 수 있습니다. 일반적으로 빅-오 표기법을 많이 사용하지만 자료구조 in C 포스팅에서는 빅-세타 표기법을 사용할 것입니다.
1) 빅-오(Big-O) 표기법
If \(f(n) = O(g(n))\) then \(f(n) \le \alpha g(n)\) when \(n>n_0\) for some value \(\alpha, n_0 >0\).
(Because people mostly care about the upper bound, there is no lower bound when we talk about Big-O)
2) 빅-오메가(Big-\(\Omega\)) 표기법
If \(f(n) = \Omega(g(n))\) then \(f(n) \ge \alpha g(n)\) when \(n>n_0\) for some values \(\alpha, n_0>0\).
3) 빅-세타(Big-\(\Theta\)) 표기법
If \(f(n) = \Theta(g(n))\) then \(\alpha g(n) \ge f(n) \ge \beta g(n)\) when \(n > n_0\) for some values \(\alpha , \beta, n_0 > 0\).
→ If \(f(n) = O(g(n))\) and \(f(n) = \Omega(g(n))\), then \(f(n) = \Theta(g(n))\).
→ If \(f(n) = \Theta(g(n))\) then \(f(n) = O(g(n))\) and \(f(n) = \Omega(g(n))\).
→ In a polynomial, \(\Theta\) only considers the largest term.
ex) \(f(n) = 5n^3 + 2n^2 + 100n + 4 = \Theta(n^3)\)
→ \(\Theta\) always disregards any coefficient
ex) \(f(n) = 1000000n^2 = \Theta(n^2)\)
→ Inside \(\Theta\), we can disregard the base of a logarithm.
ex) \(log_{2} n \simeq \Theta(3.33log_{10} n) = \Theta(log n)\)
참고자료 : 고응남, 「C로 배우는 알기 쉬운 자료구조」, 인피니티북스, 2021
학교 수업 (Data structures)
'프로그래밍 > 자료구조 in C' 카테고리의 다른 글
| 0. C프로그래밍 개발 환경(비주얼 스튜디오 다운 및 설치 방법, C시작하기) (0) | 2021.07.13 |
|---|