[자료구조] 자료구조와 알고리즘

자료구조와 알고리즘

---

1. 자료구조(Data Structure)

자료구조란 자료(데이터)를 컴퓨터에 효율적으로 저장하는 방식을 의미합니다. 자료구조가 필요한 이유는 메모리의 효율적인 관리와 프로그램 실행시간의 단축입니다. 자료구조는 데이터 저장 형태에 따라 크게 선형 구조와 비선형 구조로 분류됩니다.

 

1.1. 선형 구조(Linear data structure)

선형 구조는 자료가 선형적으로 연결되어 있는 구조를 의미합니다. 즉, 첫 번째 자료와 마지막 자료를 제외한 모든 자료들은 앞뒤로 자료가 1개씩 존재하는 1:1 구조가 됩니다. 선형 구조에는 리스트(list), 스택(stack), 큐(queue) 등이 포함됩니다.

 

1.2. 비선형 구조(Non-linear data structure)

비선형 구조는 자료들이 계층적이거나 분기로 연결된 구조를 의미합니다. 비선형 구조에는 트리(tree), 그래프(graph) 등이 포함됩니다.

 

2. 알고리즘(Algorithm)

알고리즘이란 어떤 문제를 효율적으로 해결하기 위한 절차나 방법을 의미합니다. 문제를 효율적으로 해결하기 위해서는 효율적인 자료구조가 기반이 되어야 합니다. 이 때문에 자료구조와 알고리즘은 밀접한 관계를 가지고 있습니다.

 

2.1. 알고리즘의 표현

알고리즘을 표현하는 방식은 여러가지가 있습니다. 대표적으로 사람의 언어로 표현한 자연어(natural language), 그림으로 도식화한 순서도(flow chart), 특정 프로그래밍 언어의 문법을 따르지는 않는 코드인 의사 코드(peseudo code)가 있습니다.

 

2.2. 알고리즘 성능 평가

알고리즘의 성능은 크게 공간 복잡도(space complexity)와 시간 복잡도(time complexity)를 통해 비교합니다. 공간 복잡도는 알고리즘 수행에 필요한 저장 공간량이고, 시간 복잡도는 알고리즘 수행에 걸리는 시간을 나타냅니다.

 

시간 복잡도를 조금 더 자세히 알아보면, 실제로 연산이 수행되는 횟수를 의미합니다. 그리고 알고리즘 내에서 사용자의 정의에 따라 바뀔 수 있는 반복문의 연산 횟수 등 요소를 변수로 표현한 것이 시간 복잡도 함수입니다. 이때 시간 복잡도 함수는 중첩되는 반복문 등으로 인해 다항식 함수로 표현이 될 수 있는데, n이 한없이 커질 때 가장 영향도가 큰 차항으로 간소화하는 표기가 빅-오 표기법(Big O notation)이라고 하며 표기는 "O(계수를 1로 바꾼 최고 차항 n)"으로 합니다.

 

아래 예시를 참고하면 시간 복잡도 함수는 1 + 1 + 1 + (n * (1 + (n * 1))) = n2 + n + 3이 됩니다. 그리고 이때 빅-오는 O(n2)가 됩니다.

#include <stdio.h>

int main(void) {
	int n = 10;							// 1
	int chk = 0;						// 1
	int sum = 0;						// 1

	for (int i = 0; i < n; i++) {		// n
		chk += 1;						// 1
		for (int j = 0; j < n; j++) {	// n
			sum += 1;					// 1
		}
	}
}

---

연관 게시글

---

참조

•