2019년 7월 15일 월요일

[독학사] 자료구조 내용정리 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. 의사 코드

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

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


Share:

댓글 1개: