ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [자료구조] 1강 1장 기본 개념 - 1절 자료구조와 알고리즘
    프로그래밍/자료구조 2014. 4. 17. 16:23
    반응형

    Data : 어떠한 사실이나 값

    수치값 : 진수로 표현

     

    * 스트링 : 연속적인 저장 공간에 저장된 문자열을 의미하며 문자 사이의 공백을 포함하여 문자열의 길이를 표현

     

    * 정보 : Data값을 처리하여 발생되는 결과

     

    * 자료구조란?

    - 자료 사이에 존재하는 관계를 개념적으로 정의

    - 자료를 효율적으로 이용할 수 있도록 자료의 특성에 따라 분류하여 구성하고 저장 및 처리하는 모든 작업

     

    * 자료 구조를 기억 공간 내에서 실현하는 방법

    - 기억 공간 내에 앞에서부터 차례로 데이터를 기억시키는 방법 (배열)

    - 자료 사이의 관계가 기억 공간 내의 위치와 독립하여 포인터에 의한 접속으로 얻게 되는 방법 (리스트)

     

    * 배열과 리스트의 차이점

    - 배열 : 메모리 공간 내에 연속적인 공간이 있어야한다

    - 리스트 : 메모리 공간 내에 연속적인 공간이 없어도 메모리 공간 어디에도 저장가능

     

    * 자료 구조의 형태에 따른 분류

    - 단순 구조 : 정수, 실수, 문자, 문자열 등의 기본 자료형

    - 선형 구조 : 순서 리스트, 연결 리스트, 스택, ,

    - 비선형 구조 : 트리, 그래프

    - 파일 구조 : 순차파일, 색인파일, 직접파일 (속도면에서 순차파일<색인파일)

     



    * 자료구조를 선택하기 위한 요인

    - 데이터의 양

    - 데이터를 사용하는 방법과 횟수

    - 데이터의 정적 혹은 동적인 특성

    - 데이터 구조에 의해 요구되는 기억 장치의 양

     

    * 알고리즘

    - 특정한 일을 수행하는 명령어들의 유한집합 (문제를 해결하기 위한 수행과정)

     

    * 알고리즘의 요구조건

    - 입력 : 외부로부터의 자료 입력이 0개 이상있어야한다.

    - 출력 : 최소 한 가지 이상의 출력이 있어야한다.

    - 명확성 : 각 명령들은 명확하고 모호하지 않아야한다.

    - 유한성 : 언젠가는 반드시 종료해야한다.

    - 유효성 : 알고리즘을 구성하는 명령문들은 하드웨어에서 실행 가능해야한다.

     

    * 알고리즘을 기술하는 방법

    - 자연어를 사용하는 방법(잘 안쓰임)

    - 흐름도를 사용하는 방법(가시적으로는 좋으나 복잡해지면 표현하기가 어렵다)

    - 의사 코드(pseudo-code)를 사용하는 방법(가장 일반적인 방법)

     

    * 흐름도를 사용하는 방법

    (복잡해지면 흐름도 사용X) -> 의사코드 사용

     

    * 자료 추상화

    - 데이터 타입 : 데이터의 집합과 연산의 집합

    - 추상화 : 필수적이고 중요한 속성만을 골라서 일반화시키는 과정

    - 추상 데이터 타입 (Abstract Data Type : ADT) :

    데이터 타입의 일반화로 정의

    데이터가 무엇이고 무슨 기능을 수행하는가만을 정의

    데이터 구조 및 연산의 구현 방법은 불포함 (이유 : 프로그램언어마다 구현방법이 다름)

    객체와 연산을 정의

     

    * SPARKS (Structured Programming : AReasonably Komplete Set)

    - 알고리즘을 기술하는 언어

    - 선언문, 지정문, 조건문, 입출력문등

     

    * 선언문

    - 여러 가지 형태의 변수를 선언하여 자료형(Data Type)을 사용

     



    * 지정문

    - 상수나 변수 또는 연산식의 결과를 변수에 지정하는 문장

    PX; q0 : 여러문장은 세미콜론(;)으로 구분하여 한줄에 표현가능

    LINK(p)Y

    qq+1 : 산술식, 논리연산자, 관계연산자, 부울식, 문자식 표현가능

     

    * 조건문

    - 조건 결과에 따라 참이나 거짓으조건의 수행여부를 결정

    - if, while~do, repeat~until

    - 조건에 따라 실행되는 명령문이 여러 개인경우에는 대괄호[]로 묶어 표현

     

    * if

    - 참이나 거짓을 판별할수 있는 조건식을 표현하고 조건이 참인 경우에는 실행하는 문장과 거짓인 경우에 실행하는 문장을 기술

     

    형식 1

    if (조건식) then 명령문1 : if 조건식이 참이라면 명령문 1을 수행 거짓이라면 명령문2 수행

    else 명령문2

     

    형식 2

    if (조건식) then 명령문1 : if 조건식이 참이라면 명령문 1을 수행 거짓이라면 수행X

     

    * while~do

    - 조건식이 참인 동안에는 해당 명령문을 반복 수행하는 구문

    while (조건식) do

    명령문

    end

     

    * repeat~until

    - 조건문에서 명령문을 먼저 실행한 다음 조건식을 판별하고 조건식이 참이 될 때까지 해당 명령문을 반복 수행

    repeat

    명령문

    until 조건식

     

    * CASE

    - 여러 조건식 중에서 해당 조건을 찾아서 그에 해당되는 명령문을 수행하는 구문

    - 여러 개의 if문이 쓰이는 블록을 대체

    - 반복적인 내포 관계에서는 if문보다는 case문으로 표현하면 가독성이 높아짐

    case

    :조건식1:명령문1

    :조건식2:명령문2

    :

    :

    :조건식n:명령문n

    :else:명령문n+1

    end

     

    * 반복문 for

    - 조건식이 초기 값부터 시작하여 증분 값에 따라 최종 값에 해당될 때까지 해당 문장을 반복 수행하는 문장

     

    for 변수 초기값 to 최종값 by 증분값 do

    명령문

    end

     

    * Procedure

    - 일련의 반복적인 명령을 수행하는 블록을 별도의 블록으로 표현한 것

    - 알고리즘은 하나 이상의 procedure로 구성

    - 프로시저간 연락은 매개변수를 사용

    - 실행한 후 다시 제어권만을 회수(서브루틴)

    - 실행한 후 결과값을 변환(함수)

     

    procedure NAME(parameter list)

    명령문

    end

     

    * 프로시저간의 자료 전달 방법 (value, reference 가 많이 쓰인다)

    - call by value : 실 매개변수 값을 계산하여 서브 프로시저의 형식 매개변수에게 전달하는 방법

    - call by reference : 실 매개변수 값이 저장된 기억장소를 가리키는 포인터나 실제주소를 형식 매개변수에 전달하는 방법

    - call by name : 서브 프로시저에서 매개 변수가 사용되기 전까지 실매개변수를 계산하지 않고 전달하여 실 매개 변수의 값을 계산하는 시기를 서브 프로시저에서 결정하는 방법

     

    * 입출력문

    - Read: data값을 입력받을 때 사용

    - Print: 변수의 내용이나 계산 결과를 출력할 때 사용

    read(argument list)

    print(argument list)

     

    * 주석

    - 두 개의 슬래쉬(//)를 사용하여 알고리즘의 어떠한 위치에서도 사용이 가능

    - /* */ 는 주석의 시작과 끝을 표시

    - 여러 문장에 대해 기술 가능

     

    * stop

    - 현재 진행 중인 알고리즘을 중단하는 구문

     

    * SPARKS언어의 사용 규칙

    - 모든 프로시저의 입출력 변수를 명확히 명세

    - 변수의 의미를 알 수 있게 정의

    - 알고리즘의 제어 흐름은 되도록 순차적으로 표현

    - 가독성을 위해 각 문장들은 들여쓰기(indentation)을 사용

    - 주석은 짧으면서 의미는 명확히 기술

    - 함수를 적절히 사용

    반응형

    댓글 0

Designed by Tistory.