자료구조란 무엇인가

자료와 정보

자료의 정의

• 현실 세계에서 관찰이나 측정을 통해서 수집된 값(value)이나 사실(fact)
• 우리의 생활에서 실제러 만질 수 있거나 볼 수 있는 것  
  (길이, 무게, 부피 등을 측정할 수 있는 대상)에 대해서 물리적인 단위로 표현하여 얻어낼 수 있는 내용

정보의 정의

• 어떤 상황에 대해서 적절한 의사결정을 할 수 있게 하는 지식으로서 자료의 유효한 해설이나 자료 상호 간의 관계를 표현하는 내용
• 어떠한 상황에 적절한 결정이나 판단에 사용될 수 있는 형태로 가공되거나 분류되기 위해 '처리 과정'을 거쳐서 정리되고 정돈된 '자료'의  2차 처리 결과물

 

수학식으로 표현하면 I = P(D)

I = information

P = process

D = data

 

추상화

• 공통적인 개념을 이용하여 같은 종류의 다양한 객체를 정의하는 것
• 추상화를 통해 간결하게 말하는 사람의 의사를 전달할 수 있게 되는 것

자료의 추상화

다양한 대상을 컴퓨터에서 저장하고 처리하기 위해 그 대상들의 의미와 구조에 대해서 공통의 특징만을 뽑아 정의한 것

➡ 컴퓨터 내부의 이진수의 표현 방법, 저장 위치 등은 포함되지 않고 단순하게 개발자의 머릿속에 그림을 그리는 것처럼 개념화하여 개발자들 사이의 의사를 쉽게 전달하기 위해 사용되는 방법

자료구조와 알고리즘

자료구조

• 추상화를 통해 알고리즘에서 사용할 자료의 논리적 관계를 구조화한 것
• 자료의 추상화와 구조화가 적절히 이루어지지 못하면 소프트웨어는 비효율적으로 수행되거나 소프트웨어의 확장성에 문제가 생길 수 있음

알고리즘

• 컴퓨터에게 일을 시키기 위한 (추상화된) 명령어의 연속된 덩어리
• 사람(개발자)이 컴퓨터에게 일을 시키기 위한 사람의 의도와 명령을 전달해 줄 수 있는 방법(언어/글)
• 컴퓨터에게 시킬 일
• 컴퓨터가 수행할 명령어의 유한 집합이 사람의 머릿속에 추상화되어 존재하는 것
• 컴퓨터에게 시킬 일(프로그램)을 머릿속에서 추상화시켜서 대략적으로 상상해 놓은 것

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

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

자료구조와 알고리즘의 추상화/구체화

입력값을 머릿속에서 추상화된 형태(자료구조)로 구조화하고, 수행되어야 할 명령어를 머릿속에서 추상화된 형태(알고리즘)로 체계화됨 ➡ 프로그래밍 언어 : 자료구조와 알고리즘을 구체화하는 방법

알고리즘의 개념과 조건

알고리즘과 프로그램

• 컴퓨터에게 일을 시키기 위한 (추상화된) 명령어의 연속된 덩어리
• 사람(개발자)이 컴퓨터에게 일을 시키기 위한 사람의 의도와 명령을 전달해 줄 수 있는 방법(언어/글)
• 컴퓨터에게 시킬 일
• 컴퓨터가 수행할 명령어의 유한 집합이 사람의 머릿속에 추상화되어 존재하는 것
• 컴퓨터에게 시킬 일(프로그램)을 머릿속에서 추상화시켜서 대략적으로 상상해 놓은 것

알고리즘의 조건

• 출력 : 알고리즘을 수행하고 나면 적어도 한 가지 결과를 생성해야 함
• 유효성 : 반드시 실행 가능해야 함
• 입력 : 외부/내부 입력값은 유한해야 하며, 반드시 입력 형태가 정의될 수 있어야 함
• 명확성 : 각 명령들은 명확하고 애매모호하지 않아야 함
• 유한성 : 반드시 종료가 명확하게 정의되어 있어야 함

알고리즘의 성능

알고리즘의 실행시간 분석

• 알고리즘을 실행하는데 필요한 예측 실행시간을 추정하여 알고리즘의 성능을 분석
• 실행 시간의 예측
  • 알고리즘의 실행 횟수를 O(n)이라고 표현
  • 같은 O(n)을 가진다고 해서 같은 실행 시간을 갖는 것이 아니라 실행 시간의 유사한 증가 경향에 대한 표현 방법

알고리즘의 실행메모리 분석

• 알고리즘을 실행하는데 필요한 공간(메모리)을 추정하여 알고리즘의 성능을 분석함
• 실행 메모리 예측(1)
  • 알고리즘의 공간 복잡도(space complexity)는 프로그램을 실행시켜서 완료하는데 필요한 총 메모리 공간
  • 고정 공간은 프로그램의 크기나 입출력의 횟수에 관계없이 컴파일 시에 결정되어 프로그램의 실행이 끝날 때까지 고정적으로 필요한 메모리 공간
• 실행 메모리 예측(2)
  • 가변 공간은 프로그램의 실행 과정에서 동적으로 할당되어야 하는 자료구조와 변수들을 위해 필요한 메인 메모리 공간
  • Sp = Sc + Se (공간복잡도 = 고정공간 + 가변공간)

알고리즘의 성능 측정

• 컴퓨터가 실제로 프로그램을 실핼하는데 걸리는 시간을 측정하여 알고리즘의 성능을 측정
• 실행 시간의 측정
  • 실제로 실행 시간을 시계로 잰다는 것
  • 실제로 실행될 수 있는 프로그램(실행 파일)이 있어야 함
  • 시스템 시계를 이용