#1 자료구조와 알고리즘이란?

일상생활에서 우리는 무언가를 정리하는 방법이 많이 존재한다.

그릇을 쌓아서 보관하거나, 사전에는 단어들이 정리되어있고, 마트 계산대에서는 줄을 서는 것과 같이 우린 어떤 사물들을 매번 정리하는 많은 방법들을 이용한다.

 

이와 마찬가지로 프로그램 내에서도 자료(data)를 정리하여 보관하는 많은 구조가 있다.

그 구조를 우린 "자료구조(data structure)"라고 한다.

 

자료를 저장했으면, 그 자료를 통해 주어진 문제를 해결해야 한다.

사전을 통해 우리는 모르는 단어를 찾듯이 프로그램에서도 자료를 통해 어떤 문제를 해결하는 절차가 존재한다.

그 절차를 알고리즘(algorithm)이라고 부른다.

즉, 프로그램은 자료구조와 알고리즘으로 이루어져있다.

그렇다면 프로그램 내부의 모든 명령어는 알고리즘이라고 할 수 있을까?

정답은 X이다.

그 이유는 알고리즘의 정확한 정의를 보며 알아보자.

알고리즘(algorithm)이란, "어떤 문제를 해결하기 위해 만든 명령어들의 유한 개의 집합"이다.

따라서, 다음과 같은 조건을 만족해야만 알고리즘으로 정의된다.

 

-알고리즘의 조건-

1. 입력: 0개 이상의 입력이 존재해야 한다.

2. 출력: 1개 이상의 출력이 존재해야 한다.

3. 명백성: 각 명령어의 의미는 모호하지 않고 명확해야 한다.

4. 유한성: 한정된 수의 단계 후에는 반드시 종료해야 한다.

5. 유효성(효율성): 각 명령어들은 실행가능한 효율적 연산이어야 한다.

 

 

여기서 유한성을 주목해보면, 알고리즘은 프로그램과 달리 일정 단계가 후에 반드시 종료된다는 것을 알 수 있다.

 

자료구조와 알고리즘은 밀접한 관계를 가지기 때문에 자료구조가 정해지면 그 자료구조를 사용할 수 있는 알고리즘들이 정해지게 된다. 따라서 우리는 어떤 상황에 대해 적절한 자료구조를 알 필요성이 있다.

자료구조의 예시로 배열, 구조체, 스택(stack), 연결 리스트(linked list), 큐(queue), 트리(tree) 등 많은 종류가 있으며, 우리는 이것들을 나중에 하나씩 알아볼 것이다.