[자료구조] 기초 - 개론

자료(Data)

 생할속에서 단순한 관찰이나 측정을 통하여 수집한 사실이나 개념의 값들 또는 값들의 집합이다.


정보(Information)

 자료를 처리/가공하여 의미를 부여한 결과 의사결정에 도움을 주기위해 유용한 형태로 다시 작성된 자료를 의미한다.


자료구조(Data struct)

 다 루고자하는 자료 원소들간의 논리적 관계를 기술한 것으로, 컴퓨터의 내/외부에 물리적으로 구성되는 휘발성 또는 비휘발성 메모리에 존재하는 자료의 집합으로써 컴퓨터를 이용하여 문제를 해결하기 위하여 자료의 값들에 대한 연산을 효율적으로 처리할 수 있도록 자료의 구성을 조직적이고 체계적으로 표현하는 것을 의미한다.

자료구조를 선택하는 기준

* 자료의 양 (차지하는 메모리 공간)
* 자료의 활용 빈도
* 자료의 갱신 빈도
* 사용 가능한 기억 용량 (사용가능한 전체 메모리)
* 처리 시간의 제한성
* 프로그래밍의 용이성

자료구조를 선택할 때에는 프로그램이 원하는 기준을 만족하는지 검사하여 가장 효율적인 자료구조를 선택/사용한다.

 

자료구조를 사용하는 이유

효율성(Efficiency)

자료를 구조화하여 사용함으로써 조금더 효율적으로 알고리즘을 구성할 수 있다.
자료에 대한 알고리즘을 사용하는데 있어 자료를 구조화하여 사용함으로써 최악의 상황 (처리 시간, 차지하는 기억용량)등을 고려하여 알맞는 알고리즘을 선택하여 사용할 수 있다.

추상화(Abstraction, 일반화)

자료를 구조하는데 있어 자료를 표현하고 조작하는 방법을 추상화하여 사용함으로 인해 프로그램에 의존적이지않다.
그렇기 때문에 다양한 프로그래밍 언어로 구현이 가능하며, 어떻게 구현할 것인가가 아닌 어디에 어떻게 사용할 것인가에 초점을 맞출 수 있다.

재사용성(Reusability)

자료구조는 모듈화되어있고 문맥에 자유롭기 때문에 재사용이 가능하다.
문맥에 자유롭기 때문에 다양한 자료와 상황에 다양하게 사용될 수있고, 규정된 자료구조를 모듈화하여 사용함으로써 다양한 프로그램에서 재사용할 수 있다.


알고리즘

 알고리즘이란 어떤 문제를 해결하기 위해 기술해 놓은 명확한 절차를 의미하며 다음 5개의 특징을 가지고 있어야 한다.

* 입력(Input). 외부에서 제공되는 자료가 있을 수도 있고 없을 수도 있다.
* 출력(Output). 한 개 이상의 결과가 반드시 생성되어야 한다.
* 명백성(Definiteness). 문제해결 단게에서 수행할 내용은 명백해야 한다.
* 유한성(Finiteness). 한정된 수의 단계 후에는 반드시 종료되어야 한다.
* 유효성(Effectiveness). 앍리즘의 모든 명령은 수행 가능한 것이어야 한다.


소프트웨어 공학(Software engineering)

 프로그램 작성 시 중요한 정확성과 효율성을 갖춰 진행하기 위한 워칙과 기술, 도구를 적용하는 방법론이다.
컴 퓨터의 발전과 더불어 소프트웨어를 개발하는 데 있어서 필요한 원리를 연구하는 분야로써 소프트웨어의 분석, 설계 구현 및 유지보수에 관한 체계적인 접근 방법으로써 신뢰성 있는 양질의 소프트웨어를 경제적인 비용으로 생산하는 데 그 목적을 둔다.

소프트웨어 개발비용보다 차후에 발생하는 유지보수에 드는 비용이 증가됨으로써 발생하는 문제점들을 해결하기 위해 시작


소프트웨어 생명주기(Software life cycle)

소프트웨어 공학의 관점에서 개발 과정 및 유지 단계를 요구 분석, 시스템 명세, 설계, 구현, 테스트, 유지보수 의 6가지 단계로 나눈 것

 요구 분석

 

사용자의 요구사항을 토대로 문제를 해결하기 위한 방안을 정의하는 단계

 시스템 명세

 

요구 분석을 토대로 문제를 해결하기 위한 방안(시스템이 무엇을 해야하는가)을 정의하는 단계

 설  계

 

실질적인 수행 방법을 논리적으로 설계하여 소프트웨어 시스템에서의 알고리즘을 구축하는 단계(어떻게 수행해야 하는가)

         하향식 설계. 프로그램을 단계별로 세분화하여 처리
         상향식 설계. 다른 소프트웨어에서 작성해놓은 알고리즘이나 도구를 재사용후 기능을 추가

 구  현

 

설계된 알고리즘등을 프로그래밍 언어를 이용하여 개발자가 코딩하는 단계(프로그램 작성)

         구조적 프로그래밍. 유지보수와 디버깅이 용이
         모듈러 프로그래밍. 프로그램의 효율적인 구현이 가능, 변경과 이식이 용이

 테스트

 

설계에 의해 제대로 동작하는지 실험하는 단계(문제없이 작동하는가)

         단위 테스트. 각 모듈별로 제공되는 테스트 자료로 검사를 수행
         통합 테스트. 관련이 있는 몇 개의 모듈들을 그룹화하여 통합 검사 수행
         시스템 테스트. 완성된 시스템이 명세에 따라 정확하게 수행되는지 검사

 유지보수

 

시스템의 사용후에 발생하는 모든 사후처리
    
         테스트 단계에서 검출할 수 없었던 오류나 버그가 나타난 경우
         소프트웨어를 설계할 당시의 실제 운영 환경등이 변경되어 적응시키기 위한 교정이 필요한 경우
         사용자의 추가 요구에 따라 소프트웨어를 갱신해야 하는 경우 가 발생할 경우 개발의 연장선상에서 프로그램을 교정한다.


자료구조의 분류

 선형 구조

         배열(Array)
         연결 리스트(Linked list)
                  단순 연결 리스트
                  이중 연결 리스트
                  원형 연결 리스트
         스택(Stack)
         큐(Queue)
         데크(Deque)

 비선형 구조

         트리(Tree)
                  일반 트리
                  이진 트리
                  AVL 트리
                  2-3-4 트리
         그래프(Graph)
                  무방향 그래프
                  방향 그래프
                  가중치 그래프