[Data Structure] 1. 자료구조의 개념

자료구조란

프로그래밍에서 데이터를 효율적인 접근 및 수정을 가능하게 하는 자료의 조직, 관리, 저장을 의미합니다.
데이터 값의 모임, 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미합니다.

컴퓨터의 연산 과정에서 메모리 자원은 한정적인데 반해 처리해야 할 데이터는 무수히 많을 수 있습니다. 그러한 상황에 자료구조를 통해 메모리를 효율적으로 사용할 수 있습니다.

하지만 모든 목적에 맞는 자료구조는 없기 때문에 각 자료구조가 갖는 장점과 한계를 알고 사용할 필요가 있습니다.

자료구조의 형태

• 선형 구조 : 자료들을 구성하는 원소들을 하나씩 순차적으로 나열시킨 상태.
  자료 간 관계가 1대1인 구조, 대표적으로 스택과 큐가 이에 해당됩니다.

• 비선형 구조 : 하나의 자료 뒤에 여러 개의 자료가 존재할 수 있는 형태. 자료 간 관계가 1대다 혹은 다대다인 구조입니다. 대표적으로 트리나 그래프가 있으며 계층적인 구조를 나타내기 적합합니다.

선형구조 : 이진 탐색, 선형 탐색이 가능하다.
비선형구조 : 이진 탐색, 선형 탐색이 불가하며 DFS, BFS와 같은 그래프 탐색이 필요하다.

자료구조와 알고리즘의 관계

알고리즘(Algorithm)이란 문제를 해결하기 위한 정해진 진행절차나 방법으로 컴퓨터에서 알고리즘은 어떠한 행동을 하기 위해 만들어진 프로그램 명령어들의 집합입니다. 문제 풀이에 필요한 진행 절차나 처리 과정이라고도 할 수 있습니다.

프로그램 : 특정 문제를 해결하기 위한 처리 방법과 순서를 기록한 명령어들의 모음

보통 사용할 자료 구조가 선택되면 효율적인 알고리즘은 정해져 있습니다. 즉, 자료 구조를 통해 효율적인 알고리즘을 선택할 수 있으므로 자료구조와 알고리즘은 매우 밀접한 관계를 가질 수 밖에 없습니다.

넓은 의미에서 자료구조 + 알고리즘 == 프로그램 이라고 할 수 있습니다.

하지만 알고리즘은 늘 같은 결과를 내지만 프로그램은 그렇지 않다..

알고리즘의 조건 및 성능

<알고리즘의 조건>

1. 입출력(input) : 정해진 입력과 출력이 정해져야 함.
2. 명확성(definiteness) : 각 단계마다 단순하고 모호하지 않아야 함.
3. 유한성(finitness) : 단계들을 반드시 유한한 횟수를 거친 후 종료해야 함.
4. 효과성(effectiveness) : 모든 과정은 충분히 단순하게 수행 가능해야함.

<알고리즘의 성능>

1. 정확성 : 정확하게 동작하는가?
2. 단순성 : 얼마나 단순한가?
3. 최적성 : 더 이상 개선할 여지가 없을 만큼 최적화되어 있는가?
4. 작업량 : 얼마나 적은 연산을 수행하는가?
5. 메모리 사용량 : 얼마나 적은 메모리를 사용하는가?

틀린 내용이나 추가적인 내용에 관한 의견 주시면 감사하겠습니다. (_ _)