[DS] 자료구조 개요

# 소프트웨어와 자료구조

- 자료: 측정되거나 수집된 값의 모음 → 한 가지 데이터로 다양한 문제 해결 가능

- 정보: 수집된 데이터를 분석하여 새롭게 알아낸 사실

- 알고리즘: 주어진 문제 해결에 필요한 절차를 체계적으로 구성해 놓은 명령어

- 프로그래밍: 프로그램을 설계, 구현하는 작업

- 컴퓨터 과학: 컴퓨터 하드웨어만을 다루지 않으며 컴퓨터를 활용하여 주어진 문제를 해결하기 위한 소프트웨어 이론과 방법에 대해 연구하는 학문

> 목표: 주어진 문제를 해결하기 위한 절차인 알고리즘을 개발하는 것

- 자료구조: 프로그램을 통해 다량의 데이터를 효과적으로 저장, 관리, 처리하기 위해 사용되는 구조체 및 방법론

 

Linear Data structures	Array, Stack, Queue
Non-Linear Data Structure	Tree, Graph
Advanced DS	BST, Weight Networks
Searching and Sorting algorithms

 

 

 

# 알고리즘의 정의

- 알고리즘: 특정 작업을 완료하는데 필요한 명령어

- 조건

  ① 입력: 명시적 입력은 없어도 된다

  ② 출력: 하나 이상의 출력이 있어야 한다

  ③ 명확성: 모호하지 않은 명령문으로 표현되어야 한다

  ④ 유한성: 유한한 수의 명령어 실행 이후에 종료되어야 한다

  ⑤ 유효성: 실행 가능한 명령어로 구성되어야 한다

- 기술(description)

  > pseudo code

  > flow chart

- 유형

  ① Search

  ② Sort

  ③ Compute

  ④ Decision

- 예제

  > 소수 찾기

  > 허프만 코딩 트리

 

 

# 소프트웨어와 개발주기

 

소프트웨어의 개발 주기

① 요구 사항 명세 (requirement specification)

- 프로젝트의 목표를 정의하는 명세서가 만들어짐

- 목표 프로그램의 사용 환경(platform), 주요 기능(function), 입출력 정보(input/output), 사용자 인터페이스 방법(user interface) 등이 포함됨

- 누락되는 부분이 있으면 이 단계를 다시 반복해야 함

② 문제 분석 (analysis)

- 추상적으로 기술된 요구 사항을 해결하기 용이하도록 구체적이고 적당한 크기의 세부 문제들로 분할하는 작업

  → Devide and Conquer 전략 사용

* devide and conquer: 데이터를 작은 단위로 나누어 데이터의 부분 집합에 일련의 절차를 반복하는 패턴

- 상향식(bottom-up)

  > 기본 단위들을 조합하여 중간 단위의 서브 시스템을 구축하고 이 서브 시스템을 다시 결합하여

     최종적인 목표 시스템을 구축해 나가는 방식

- 하향식(top-down)

  > 프로젝트의 최상위 목표에서부터 출발하여 필요한 하위 세부 모듈들을 구성하는 방법

  > 최종적으로 모듈들의 전체 계층도가 생성됨

③ 기능 설계 (design)

- 문제 분석 단계에서 생성된 각 모듈에서 필요한 객체와 연산자들을 정의

④ 구현 (implimentation)

- 각 모듈의 기능을 상세화하고 실행 가능한 코드로 변환하는 과정

⑤ 검증 (verification)

- 구현된 프로그램이 프로젝트의 요구 사항을 만족하는지, 기능들이 정확히 수행되고 있는지 확인하는 과정

- black box test: 입력 값으로부터 발생하는 출력 값을 보고 정확도를 판단

- white box test: 프로그램 내부 루틴 (if-else, switch 등)을 포함하여 오류를 검사

- debugging: 시험 평가 후 오류가 발생하면 오류의 원인에 해당하는 이전 단계로 돌아가서 시행하는 작업

 

 

# 자료형

- 단순 자료형

 

char	1byte
short	2byte
int	4byte
long	4byte
float	4byte
double	8byte
long double	8byte
int *	4byte
double *	4byte

 

- 복합 자료형: 배열, 구조체

 

 

# 추상 자료형

- 새로운 객체의 속성과 연산자를 정의하여 사용할 수 있도록 해주는 자료형

  > 명세부(specification): 객체의 속성을 선언

  > 구현부(implementation): 객체에 적용 가능한 연산자 함수를 정의

- 객체지향 언어: 추상 자료형에 기반한 언어 ex) c++, python

- 자료 추상화: 공통적인 속성과 행동을 갖는 객체들을 자료형으로 정의하는 행위

- 연산자: 기능에 따라 구분

 

생성자(constructor)	새로운 객체를 생성
변형자(transformer)	기존 객체를 이용하여 새로운 객체를 생성
참조자(reporter)	기존 객체의 속성값을 참조

 

- 예시: 은행 계좌 추상 자료형

  > 속성: 계좌 번호(account_id), 계좌 종류(account_type), 계좌 소유주(owner_name), 잔액(balance)

  > 연산자: 입금(deposit), 인출(withdraw) 함수

  > init 함수: 객체 생성자. 인자들을 이용해 객체의 속성 값을 초기화

  → 예시에서는 myaccount라는 계좌 객체가 초기값을 가지고 생성됨

 

# 은행 계좌의 추상 자료형 선언
class BankAccount
{
  int account_id;
  int account_type;  # 0:cheking, 1:saving
  char owner_name[20];
  float balance = 0;  # 여기까지가 명세부

  deposit(amount){  # 입금
    balance = balance + amount;
  }
  withdraw(amount){  # 인출
    balance = balane - amount;
  }
  init(name, type, money)  # 생성자
  {
    owner_name = name;
    account_type = type;
    deposit(money);
  }  # 여기까지가 구현부
}

BankAccount myaccount("Kim", 0, 1000);