Kanadel의 블로그!

2019년 7월 16일 화요일

[독학사] 자료구조 내용정리 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는 수식이 어려워서 사실 이해를 하진 못했음;; 이거 계산하는 문제 나옴 다 틀리겠다...

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

독학학위제 컴퓨터과학부 4단계 전공 과목 중 자료구조 과목을 학습하며 정리한 내용을 작성한 포스트입니다.

국가평생교육진흥원에서 제공한 시험 영역을 기준으로 학습했습니다.

자료(Data)와 정보(Imformation).

자료는 현실에서 관찰이나 측정으로 수집한 결과 값이나 수치들을 의미하며 표현하는 방법은 논리값 (True, False)과 수치, 문자열 세가지로 구분된다.

수치 자료는 컴퓨터에서 2진수로 적용.
문자열 자료는 문자코드를 사용하여 숫자로 변환되어 컴퓨터에 적용.
(ASCII, BCD, EBCDIC 코드 들)
논리 자료는 가 부 값을 0 , 1로 변환하여 컴퓨터에 적용.

수치와 문자 자료는 표현 방식에 따라 값의 범위가 결정되어짐
(수치에서 부호의 포함여부 같은)

정보는 어떠한 현상이나 상황에 필요한 의사결정에 도움이 되는 자료의 해석이나 프로그램으로 처리된 결과 값을 의미한다.

정보는 시간에 따라 가치가 바뀌는 한시성을 가지거나, 많은 이들이 공유함으로써 가치가 상승하는 공공성이나, 소유한 개체가 적을수록 가치가 상승하는 독점성과, 사용 횟수에 가치가 변하지 않는 비소모성 네가지의 특성으로 구분한다.

특성들은 서로간에 모순점이 있으니 전부를 포함하긴 어려울듯 싶다.

자료구조(Data Structure)

자료구조란 자료를 더 사용하기 편하게 하기 위해 특성에 따라 분류한 구조체를 의미함.

구조체는 또한 그 자체가 컴퓨터에 저장되는 단위이자 방법이기 때문에 자료 구조를 파악하는건 자료의 특성과 저장 방식을 파악하는것과 동일한 의미이다.

자료구조의 분류는 다음과 같음

1. 단순 자료구조 : 정수나 실수 문자열 등 단일 형태의 자료를 저장할 때 메모리 공간과 자료를 다루는 연산자들의 모음.

2. 선형 자료구조 : 자료간 1:1로 짝을 맷는 형식 (리스트, 스택, 큐 같은거)의 자료를 저장할 때 메모리 공간과 자료를 다루는 연산자들의 모음.

3. 비선형 자료구조 : 자료간 1:N으로 대응되는 자료들 (트리나 그래프 등)를 저장할 때 메모리 공간과 자료를 다루는 연산자들의 모음.

4. 파일 : 메인메모리가 아닌 보조기억장치에 저장될 대용량 자료구조를 의미. 파일은 구성에 따라 인덱스, 해싱, 순차, 상대적 파일 구조로 구분된다.

자료를 저장하거나 정보로 만들기 위해선 자료를 적절한 자료구조로 저장하는게 우선이다.

자료구조는 자료의 크기, 사용 횟수나 방법, 관계 특성들을 고려하여 적절하게 선택되어야 한다.

알고리즘(Algorithm)

알고리즘이란 문제를 해결하기 위한 절차나 방법들을 단계로 구분하여 정의한 일정의 단계들이다.

알고리즘을 통하여 문제를 유한한 단계의 과정으로 풀어낼 수 있다.

알고리즘은 문제 해결을 위한 입력과 출력이 필요하며, 명령이 명확해야 하고, 무한한 단계를 거치지 않고 종료가 되어야 한다.

알고리즘의 요구 조건

1. 입력 : 문제 해결의 기본 자료가 될 입력값.
2. 출력 : 입력값을 알고리즘을 통해 도출된 결과 값.
3. 명확성 : 각 단계는 모호한 명령이 없어야 함.
4. 정확성 : 각 단계는 입력값에 대한 정확한 출력값을 도출해야함.
5. 유한성 : 무한 루프로 영원히 해결되지 않는 알고리즘이 되지 않아야함.
6. 효율성 : 알고리즘은 최대한 간소한 단계로 수행되어야 함.
7. 일반성 : 문제가 요구하는 모든 형태의 입력값에 대응 할 수 있어야 함.

자료 구조와 알고리즘이 결합, 조합되면 프로그램이 됨.

예)
배열 자료구조 + 최대값 찾는 알고리즘 = 순열중 최대값을 찾는 프로그램

알고리즘 기술 방법

1. 자연어
2. 순서도

자연어는 작성자의 의도와 다른 해석이 가능하여 알고리즘의 요구 조건 중 명확성을 위반할 가능성이 높으며, 순서도는 직관적이고 이해가 빠르지만 복잡한 단계의 표현이 어렵다는 단점이 있다.

그래도 모호한 내용보다는 복잡한게 더 낫기 때문에 둘 중에선 알고리즘은 순서로도 작성하는게 일반적이다.

(순서도 기호는 따로 정리하지 않음)

3. 의사 코드

자연어와 순서도의 장점을 섞은 방식으로 순서도를 매서드와 시켜 코딩하듯 나열하는 방법.
자연어보다 구조적인 표현이 가능하고 프로그래밍 언어로 변환이 용이한 장점이 있음.
순서도에 비해 매우 간단하게 표현이 가능.

(의사 코드를 따로 작성하진 않겠음)

독학사 태그에 대해서 (독학학위제 컴퓨터과학과)

오늘부터 블로그에 새로 신설된 태그인 독학사에 대한 설명과 앞으로 작성될 포스트 시리즈에 대해 알리는 글을 작성합니다.

(블로그 카테고리에 추가된 독학사 관련 태그들)

독학사(독학학위제)는 국가에서 공인한 교육 기관을 거치지 않고 스스로 독학한 성과를 시험을 통해 학위나 학점으로 인정 받는 제도입니다.

(독학학위제 공식 홈페이지 링크 : 이동하기)

(독학학위제 홈페이지의 소개 내용)

따라서 대학에 다닐 여유나 시간이 없는 상황에서 가장 빠르고 저렴하게 학위를 취득할 수 있는 방법이 이 독학학위제 입니다.

독학학위제를 통해 학위를 취득하는 과정은 다음과 같은데요

4년제 대학의 네 학년과 같이 독학사 또한 네 단계의 과정이 존재하며 각 과정당 정해진 과목의 시험을 통과하면 해당 과목의 학점을 인정하는 방식입니다.

한가지 특이한 점은 각 과정을 시험으로 통과하는 방법뿐만 아니라 일정한 자격이나 경력에 따라 과정이나 과목을 면제해주는 제도도 함께 운영되고 있기 때문에 잘 맞추면 많은 과목을 면제 받아 좀 더 빠른 학위 취득이 가능하다는 점이 있습니다.

독학학위제로 취득할 수 있는 학위의 종류는 총 11가지가 있으며

각 과정별 시험은 일년에 딱 한번만 진행이 됩니다.

그리고 시험은 과목당 100점 만점으로 운영되며 보통 합격 기준점이 60점입니다.

제가 이 블로그에 독학사 태그를 신설한 이유는 올해 학위취득 인정 시험인 독학사 4단계 시험에 응시하기 때문인데요.

지금 저는 컴퓨터 프로그램과 관련된 일을 하지만 대학은 화공쪽을 졸업해서 시스템 공부는 전혀 해본적이 없었습니다.

그래서 취직 하고는 지금까진 혼자 이런저런 하고싶은 공부를 조금씩 했었는데요. 마침 독학사의 컴퓨터과학부는 정보처리 기사 자격증이 있으면 3단계까지 면제를 해준다는 소식을 우연히 듣고 검색해보니

과목 면제 알람에서

정보처리기사의 과정 면제를 확인해서 기왕 공부하는김에 학위도 인정 받는 시험을 준비해보자란 생각이 들어 시험 준비에 들어가게 되었습니다. ^^

독학사 4단계 시험은 과목이 총 6개 (교양2 + 전공 4)인데요

교양은 국어 국사 외국어 중 2개를 선택하고, 전공은 시스템구조, 네트워크구조, 자료구조, 운영체제 4과목이 고정되어 있습니다.

저는 이중에서 전공은 고정이니 그대로 하고 교양은 일본어와 국사를 선택했는데요

합격 기준은 과목별 과락을 모두 넘기면 방법이 아닌 총점 과락제를 할 예정입니다.

부디 교양에서 까먹는 점수를 전공에서 만회했으면 좋겠습니다 ^^;;

앞으로 블로그에 독학사 태그가 붙는 포스트들은 제가 이 과목들을 공부하고 정리한 내용이나 시험관련 내용을 올릴 예정입니다.

독학사는 정보가 별로 없어서 도움이 되었으면 좋겠습니다.

긴 글 봐주셔서 감사합니다!