자료구조의 개념

자료와 정보 사이의 관계

자료는 현실 세계에서 관찰이나 측정을 통해 수집된 값이나 사실을 말한다. 정보는 어떤 상황에서 적절한 의사결정을 할 수 있게 하는 지식으로 자료의 유효한 해설이나 상호관계를 표현하는 내용이라고 할수있어서 자료를 적절한 처리과정을 거쳐 정돈된 자료의 2차 결과물을 정보라고 할수있다. 

I=P(D)
I는 정보 P는 처리과정 D는 자료(데이터)
자료 → 처리(컴퓨터) → 정보
요즘에는 많은 데이터를 처리하는 기술이 발전해 원하는 정보를 빠르게 얻을 수 있다 보니 데이터도 가치가 높다.

자료를 좋은것과 나쁜 것에 대한 예시를 들어본다면 색이 다른 펜과 연필을 정리대에 모두 함께 있다면 이것은 정리가 되지 않는 자료지만 각각의 색깔 별로 펜과 연필을 따로따로 묶어 놓는다면 좋은 자료구조라고 할수있다. 더 나아가서 같은 예시로 정보란 이러한 잘 정리된 자료구조를 봐서 남아있는수량과 사용량에 대한 자료를 보고 재구매 예상시기를 예측하는 것을 정보라고 할수 있겠다.

추상화의 개념

추상화를 예로 들면 지하철 노선도를 떠올려보자. 이는 실제 거리와는 무관하게 표시가 되어있다. 실제로 지하철노선도는 역과 역사이의 거리를 나타내는 목적이 아닌 다음역이 어디고 또 원하는 목적지로 가는데 역수등을 알려주는 게 목적이라는 것이다. 추상화란 공통적인 개념을 이용해서 같은 종류의 다양한 객체를 정의하는것이다. 쉽게 공통된 특징만을 모아서 대상을 간략하게 표현한 내용이다. 버스를 탄다라고 했을 때 정확히 어떤 버스를 타는지보다는 버스라는 공통점으로 타고 간다는 목적에 맞는 내용을 간략하게 표현하는 것을 추상화된 특성으로 봐야 할 것이다. 그래서 추상화를 통해 간결하게 말하여 사람의 의사를 전달할수 있다. 

고속버스, 시내버스, 마을버스, 시외버스 = 공통적인 버스라는 개념으로 추상화
말하는 언어 중에도 추상화는 굉장히 많다.

자료의 추상화는 다양한 객체를 컴퓨터에서 표현하고 활용하기 위해 필요한 자료의 구조에 대해서 공통의 특징만을 뽑아 정의한 것으로 단순하게 개발자의 머릿속에서 그리는 것처럼 개념화하는 것을 말한다. (실제 컴퓨터에 내부에서 진행상황이나 저장위치등은 고려하지 않는다.)

자료구조의 개념

자료구조는 추상화를 통해 알고르즘에서 사용할 자료의 논리적 관계를 구조화한 것이다.

이러한 자료의 추상화와 구조화가 적절히 이루어지지 못하면 소프트웨어는 비효율적으로 수행되거나 소프트웨어의 확장에 문제가 생긴다.

 

자료구조는 입력자료에 대한 추상화된 상태라면 알고리즘은 컴퓨터가 수행해야 할 명령의 추상화

 

개발자 → 추상화 → 자료구조 ← 구체화 ← 컴퓨터

 

프로그램 개발자는 입력값을 머릿속에서 추상화된 형태(자료구조)로 구조화하고 수행되어야 할 명령어를 머릿속에서 추상화(알고리즘)된 형태로 체계화한다.  그리고 추상 자료형은 자료구조와 알고리즘의 중간쯤에 있는데 자료의 복잡한 논리적 성격을 정의하는 형식으로 자료값의 집합과 연산 집합에 대한 정의로 이루어진다.

 

자료구조는 입력 자료에 대한 추상화된 상태라면 알고리즘은 컴퓨터가 수행해야 할 명령의 추상화
자료구조 → 컴퓨터 → 출력
                        ↑
                 알고리즘
자료구조와 알고리즘은 개발자가 한다.

 

자료구조의 형태는 프로그래밍 언어에서 제공되는 '미리 정의된 자료구조'와 '사용자 정의 자료구조'로 구분된다.

미리 정의된 자료구조는 정수, 실수, 문자 등과 같은 기본 자료구조와 이들로부터 파생된 배열, 구조체, 포인트등 파생된 자료구조가 있고, 사용자 정의 자료구조는 개발자에 의해 만들어지며 리스트, 스택, 큐, 트리, 그래프 등이 있다.

기본자료 구조는 말 그대로 생활 속에서 쓰는 숫자나 문자 등의 자료를 추상화한 모습이라고 생각하면 된다. 파생 자료구조는 실제 존재하지는 않지만 개발자가 유용한 자료구조라고 판단되는 자료구조이다.

또 미리정의된 자료구조는 프로그래밍 언어 개발자가 프로그램 개발자를 위해 미리 정의하지만, 사용자 정의 자료구조는 프로그램 개발자가 자신의 프로그램 개발을 위해 새롭게 정의하여 사용되는 자료구조이다.

 

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

자료구조는 알고리즘의 기초가 된다. 자료구조를 주춧돌 삼아서 알고리즘이 세워진다고 볼 수 있다. 알고리즘은 컴퓨터에 일을 시키는 명령들의 모음이며 자료구조는 명령어를 수행할 때 필요한 재료를 넣어 두는 창고이다. 거기에 일하는 순서에 맞춰서 창고를 설계하면 효율적으로 일을 할 수 있고 이는 자료구조가 알고리즘 성능에 영향을 주는 밀접한 관계임을 의미한다.

알고리즘은 컴퓨터가 일하는데 필요한 명령어를 사람의 머릿속에서 추상화되는 것을 말하는데 계획할 때에 구체적인 프로그램을 만드는 것은 쉽지 않다. 그래서 이를 머릿속에서 추상화시켜서 대략적으로 순서를 상상해 놓는 것이 알고리즘이다.

알고리즘의 조건

출력 - 알고리즘은 수행하고 나면 적어도 한 가지 결과를 생성해야 한다.

유효성 - 알고리즘은 각 연산이 명확한 것만으론 부족하고 반드시 실행이 가능해야 한다. 또한 명령어를 실행하는 주체가 누구든지 결과값은 같아야 한다.

입력 - 외부에서 제공되는 자료가 있을 수 있다. 다만 유한한 입력이어야 하고 반듯이 입력 형태가 정의되어야 한다. 예를 들면 잘생긴 사람같이 애매모호한 것은 안 된다.

명확성 - 각 명령들은 명확해야 한다. 누가 보더라도 같은 의미로 해석되고 동일한 결과를 생성해야 한다.

유한성- 알고리즘의 명령을 수행하다 보면 언젠가는 멈춰야 한다. 그래야 출력물이 나올 수 있다. 하지만 운영체제처럼 종료되지 않는 것을 목표로 하는 소프트웨어도 있다.

 

알고리즘 성능의 분석과 측정

실행시간 분석

알고리즘을 실행하는데 필요한 예측 실행시간을 추정하여 알고리즘의 성능을 분석하다.

알고리즘 실행 횟수를 O(n)이라고 표현 같은 O(n)을 가진다고 동일한 것은 아니라 실행 시간의 증가 경향이 유사하다는 의미

 

성능 측정

컴퓨터가 실제로 프로그램을 실행하는 데 걸리는 시간을 측정하여 성능을 알아내는 것

실제로 실행시간을 재는 것인데 이는 실제로 시행될 수 있는 프로그램파일이 있어야 한다.

분석과 측정의 차이는 분석은 이론으로 하는 것이고 측정은 실험을 통해서 알아가는 것으로 생각하면 이해하기 쉽다. 그러다 보니 측정에 경우 시간이 많이 걸리는 단점이 있다.