[독학사] 자료구조 내용정리 2편 (기본개념)

자료 추상화



은닉성의 기본 개념인 추상화는 전체 내용 중 필요한 부분만 외부로 노출 시키고 나머지는 감추는걸 의미한다.

자료형에 추상화를 시키면 추상 자료형(ADT: Abstract Data Type)이라고 하며 추상 자료형은 객체와 연산만 정의하는걸 의미한다.

추상 자료형은 언어마다 형식과 지원되는 연산의 갯수가 차이남.

추상 자료형 예시) createStack(S) : S라는 공백 스택을 생성한다는 뜻.

C언어에서 추상 자료형은 사용자와 구현자의 구분이고, 객체지향 언어인 C++과 Java는 각각 ADT 타입으로 지원되며 각각 스택과 힙에 할당되는 차이점이 있다.

스택이란 일정한 갯수의 데이터를 가진 리스트의 일종이며 고유한 연산으론 CreateStack(), Push(), Pop(), isEmpty()와 같은 연산들이 존재함.

연산의 집합을 일컬을때 일반적으로 알고리즘이라고 하고 객체 지향에서는 메서드, C++에서는 멤버 함수라고 하낟.

데이터 집합을 일컬을때 일반적으로 자료구조라고 하고 객체 지향에서는 인스턴스, C++에서는 멤버 데이터라고 한다.





SPARKS (Structured Programming A Reasonably Komplete Set )



SPARKS란 알고리즘을 기술하는 언어이다.

알고리즘 기술에 필수인 선언, 지정, 조건, 입출력문을 정리함.

선언문 : 변수 선언에 쓰이는 문장이며 자료형을 사용한다.

지정문 : 변수나 결과값을 변수에 할당하는 문장.

조건문 : 조건에 따라 판단한 결과값에 따라 참, 거짓 두가지 경우로 나눠 수행 여부를 결정하는 문장.

CASE문 : 조건에 따라 결정되지만 결과값이 참, 거짓 두가지 경우가 아닌 특정 조건을 찾아 많은 경우로 분기가 가능한 문장. 중첩된 IF문과 기능은 동일.

반복문 : 특정 문장을 여러 번 수행할때 사용되는 문장.
반복문의 종류로는 for문, while~do문, repeat~until문이 있다.

Procedure문 : 프로그램을 기능이나 특정 기준에 따라 나누어진 단위를 프로시저나 모듈, 서브루틴, 함수, 매서드라고 부른다.

프로그램을 나누어서 얻는 장점은 추상화 적용이 가능해지고, 다수의 인원이 참여가 용이하고, 재사용성과 빠른 구조 파악이 있다.

테스트도 체계적으로 쉽게 할 수 있겠네.

프로시저 형식은 프로시저 이름 선언과 함께 필요한 매개변수 목록을 적으면 되고 반환값이 있을 경우 활용할 수 있게 지정문도 함께 활용한다.

Call문 : 프로시저들 간 자료 전달을 위해 사용되는 문장.

프로시저 내부에서 다른 프로시저를 호출하는 방식으로 사용

call by value = 값의 의한 호출로 함수를 호출할 때 실제 값을 매개변수로 넘기고 받는걸 의미한다
call by reference = 주소에 의한 호출로 함수를 호출할 때 해당 변수의 주소 값을 매개변수로 넘기거나 받는걸 의미한다.

값의 의한 호출을 할 경우 실제 값만 복사해서 주고 받으니깐 다른 프로시저의 결과에 따라 값에 영향을 받지 않게 하는게 가능하지만 참조에 의한 호출은 해당 주소를 넘기기 때문에 다른 프로시저의 결과에 따라 주소 값이 바뀜으로 값에 영향을 무조건 주게 된다.

입출력문 : Read와 Print문으로 입력과 출력을 담당하는 문장.





순환 알고리즘



알고리즘이 자기자신을 호출하여 반복하는걸 의미함.

자기자신을 직접 호출할 경우 직접 순환. 제 3의 함수를 호출하고 그곳에서 다시 원래 함수를 호출하는 형식을 간접 순환이라고 한다.

복잡한 문제를 부분으로 나눠 해결할때 많이 사용된다.

예) 팩토리얼 계산이나 피보나치 수열 구하는 알고리즘, 이진 탐색이 대표적





성능분석



문제를 해결하기 위해 알고리즘이 사용된 시간.
문제를 해결하기 위해 알고리즘이 사용한 메모리 양.

시간은 시간 복잡도로도 불리고, 메모리는 공간 복잡도로 불림.

공간 복잡도는 무조건 일정하게 사용되는 고정공간과 변수들의 사용에 따라 잠시 빌려 사용할 가변 공간 두가지로 구분되며 고정 공간은 변수나 상수를 위한 공간이고, 가변공간은 인스턴스가 필요로 하는 공간이다.

임의의 프로그램이 사용한 총 공간 요구량을 수식으로 나타내면

총 공간 요구량 S(P) = c + Sp(I) 로 표현된다.

c는 고정 공간이고, Sp(I)는 인스턴스 작업시 요구되는 공간.

시간 복잡도는 프로그램이 소요한 실행 시간과 컴파일 시간 모두를 합한 값으로 컴파일은 고정 공간과 유사하지만 한번만 수행되기 때문에 대부분 프로그램 실행 시간만 고려한다.

연산 시간을 표기하는 방법인 Bic-Oh, Bic-Omega, Bic-Theta는 수식이 어려워서 사실 이해를 하진 못했음;; 이거 계산하는 문제 나옴 다 틀리겠다...