IT, FIRE, License and Daily life

순차 자료구조를 사용하여 다항식의 표현과 연산을 처리할 수 있다. 다항식은 aX^e 형식의 항들의 합으로 구성된 식이다. (a : 계수(coefficient), X : 변수(variable), e : 지수(exponent))

다항식의 특징은 지수에 따라 내림차순으로 항을 나열하고, 다항식의 차수는 가장 큰 지수이고, 다항식 항의 최대 개수는 (차수 +1)개이다.

1차원 배열을 이용하여 다항식과 그 계수들을 나타낼 수 있다.

[C로 풀어본 다항식 덧셈 프로그램]

-결과-

<2차원 배열의 순차 표현>

2차원 배열의 구조를 논리적으로 표현할 때는 행과 열의 구조로 나타내지만, 실제로 메모리에 저장될 때는 1차원 순서로 저장된다.

첫번째 인덱스인 행을 기준으로 하는 행 우선 순서 방법과 마지막 인덱스인 열을 기준으로 하는 기준으

로 하는 열 우선 순서 방법이 있다.

int sale[2][4] = {{63, 84, 140, 130}, {157, 209, 251, 312}};

행 우선 순서 방법은 행을 기준으로 하여 같은 행 안에 있는 열을 먼저 저장하는 방법이다.

위 그림의 배열을 예로 들면 sale[0][0]=63 sale[0][1]= 84 sale[0][2]= 140 sale[0][3]= 130 sale[1][0]= 157 sale[1][1]= 209 sale[1][2]= 251 sale[1][3]=312

[행 우선 순서의 배열 위치를 계산 하는 방법]

시작주소 + (행번호 * 열 개수 + 열 번호) * 원소의 길이​

​

열 우선 순서 방법은 열을 기준으로 하여 같은 열 안에 있는 행을 먼저 저장하는 방법이다.

위 그림의 배열을 예로 들면 sale[0][0]=63 sale[1][0]=157 sale[0][1]=84sale[1][1] =209 sale[0][2]=140 sale[1][2]=251 sale[0][3]=130 sale[1][3]=312

[열 우선 순서의 배열 위치를 계산 하는 방법]

시작주소 + (열번호 * 행 개수 + 행 번호) * 원소의 길이

<3차원 배열의 순차 표현>

int sale[2][2][4] = {{{63, 84, 140, 130}, {157, 209, 251, 312}},

{{59, 80, 130, 135}, {149, 187, 239, 310}};

3차원 논리 구조를 1차원의 물리구조로 변환하는 방법은 2개다.

면 우선 순서 방법은 첫 번째 인덱스인 면을 기준으로 하는 방법이다.

sale[0][0][0]=63 sale[0][0][1]=84 sale[0][0][2]=140 sale[0][0][3]=130 sale[0][1][0]=157 sale[0][1][1]=209 sale[0][1][2]=251 sale[0][1][3]=312 sale[1][0][0]=59 sale[1][0][1]=80 sale[1][0][2]=130 sale[1][0][3]=135 ​sale[1][1][0]=149 sale[1][1][1]=187 sale[1][1][2]=239 sale[1][1][3]=310

[행 우선 순서의 배열 위치를 계산 하는 방법]

시작주소 + {(면번호 * 행의 개수​ *열의개수) + (행번호 * 열의 개수) + 열 번호} * 원소의 길이

​

열 우선 순서 방법은 마지막 인덱스 열을 기준으로 하는 방법이다.

​sale[0][0][0]=63 sale[1][0][0]=59 sale[0][1][0]=157 sale[1][1][0]=149 sale[0][0][1]=84 sale[1][0][1]=80 sale[1][1][1]=187 sale[0][0][2]=140 sale[1][0][2]=130 sale[0][1][2]=251 sale[1][1][2]=239 sale[0][0][3]=130 ​sale[1][0][3]=135 sale[0][1][3]=312 sale[1][1][3]=312 sale[1][1][3]=310

[열 우선 순서의 배열 위치를 계산 하는 방법]

​​시작주소 + {(열번호 * 면의 개수​ *행의개수) + (행번호 * 열의 개수) + 면 번호} * 원소의 길이

Copyrightⓒ2014 By 한빛아카데미(주)

<선형 리스트>

나열한 원소들 간에 순서를 가지고 있는 리스트를 선형리스트(Linear List) 라 한다.

선형 리스트는 원소들 간의 논리적인 순서와 메모리에 저장하는 물리적인 순서가 같은 구조로 되어 있는데 이러한 구조를 순차 자료구조라고 한다.

순차자료 구조는 시작 위치와 원소의 크기를 알면 특정 원소의 위치를 알 수 있다.​

[선형 리스트의 예]

[리스트를 표현하는 방법]

리스트 이름 = (원소1, 원소2, ... 원소n)

※ 원소가 하나도 없는 리스트는 공백 리스트라 하고, 빈 괄호로 표현한다.

공백 리스트 이름 = ()

<선형 리스트의 삽입>

선형 리스트에 새로운 원소를 삽입하려면 먼저 삽일할 자리를 만든 후, 그 자리에 원소를 삽입해야 한다. 원소를 삽입할 자리를 만들려면 삽입할 위치 이후의 원소들을 한 자리씩 뒤로 옮겨야 한다.

빈자리를 매꾸기 위해 이동 횟수 : n(마지막 원소의 인덱스) - k(삭제한 원소의 인덱스)

위의 그림을 예로 들면 6-2=4이다. 즉, 4번 이동해야 함

​

​

​

Copyrightⓒ2014 By 한빛아카데미(주)

추상화란 무엇인가를 논리적으로 정의하는 것이고, 구체화는 어떻게 할 것인지를 실제적으로 표현하는 것이다.

자료 추상화는 기본적으로 3가지가 있다.

1. 자료 : 프로그램의 처리 대상이 되는 모든 것을 의미

2. 연산 : 어떤 일을 처리하는 과정으로 연산자에 의해 수행

3. 자료형 : 처리할 자료의 집합과 자료에 대해 수행할 수 있는 연산자의 집합

자료형에는 프로그래밍 언어에서 제공하는 시스템 정의 자료형과 사용자가 정의하여 사용하는 사용자 정의 자료형이 있다.

알고리즘이란 주어진 문제를 해결하기 위한 방법을 추상화하여 일련의 단계적 절차를 논리적으로 기술해놓은 명세서이다.

​[알고리즘 표현 방법 4가지]

1. 자연어(사람이 사용하는 언어)를 이용한 서술적 표현 방법

2. 순서도를 이용한 도식화 표현 방법

3. 프로그래밍 언어를 이용한 표현 방법

4. 가상 코드를 이용한 추상화 표현 방법

공간 복잡도 : 알고리즘을 프로그램으로 실행하여 완료하기까지 필요한 총 저장 공간을 의미하며, 고정 공간 + 가변공간 이다.

시간 복잡도 : 알고리즘을 프로그램으로 실행하여 완료하는데 걸리는 시간이다. 컴파일 시간 + 실행 시간이다.

Copyrightⓒ2014 By 한빛아카데미(주)

1단계. 요구 분석 단계

문제 분석 단계이며, 개발할 소프트웨어의 기능과 제약조건, 목표 등을 소프트웨어 사용자와 함께 정의하는 단계
개발할 소프트웨어의 성격을 이해하고 개발 방법과 필요한 개발 자원 및 예산을 측정하고, 요구 사항 명세서도 작성한다.

2단계. 시스템 명세 단계

시스템이 무엇을 수행해야 하는가를 정의하는 단계이며, 시스템 기능 명세서를 작성한다.

입력 자료, 처리 내용, 생성되는 출력이 무엇인지를 정의

3단계. 설계 단계

시스템 명세 단계에서 정의한 기능을 실제 수행할 수 있도록 수행 방법을 논리적으로 결정

① 시스템 구조 설계
- 시스템을 구성하는 내부 프로그램이나 모듈 간의 관계와 구조 설계
② 프로그램 설계
- 프로그램 내의 각 모듈에서의 처리 절차나 알고리즘을 설계
③ 사용자 인터페이스 설계
- 사용자가 시스템을 사용하기 위해 보여지는 부분 설계

설계방법 3가지

- 하향식 설계 방법

각 단계를 내려갈수록 수행 방법을 구체적으로 정의하고 세분화하는 방법. 하위단계로 내려갈수록 구체적인 세부 문제를 정의, 분할 정복이라고도 한다.

- 상향식 설계 방법

최하위 단계에 있는 작은 단위를 먼저 결정하고 좀 더 큰 단위인 상위 단계의 문제를 해결하는 방법.

- 객체지향 설계 방법

상향시 설계 방법과 유사하나 자료와 처리 방법이 하나의 객체로 만들어진다는 차이가 있다.

4단계. 구현 단계

프로그래밍 언어를 사용하여 실제로 프로그램으로 작성하는 단계이다.

프로그래밍 언어를 선택해야 하고 프로그래밍 기법과 스타일, 프로그래밍 순서 등을 결정해야 한다.

[프로그래밍 기법 2가지]

① 구조화 프로그래밍 : 지정문, 조건문, 반복문만 사용하여 프로그램을 작성. 순차, 선택, 반복 구조의 3가지 제어 구조로 표현하는 프로그래밍 기법.

② 모듈러 프로그래밍 : 프로그램을 여러 개의 작은 모듈로 나누어서 계층 관계를 갖도록 구성.

5단계. 테스트 단계

개발한 시스템이 요구사항을 만족하는지, 실행 결과가 예상 결과와 맞는지, 숨어있는 오류는 없는지를 찾아내 완성도를 높이는 단계다.

① 단위 테스트 : 요구 사항 명세서에 있는 기능들을 제대로 수행하는지 테스트

② 통합 테스트 : 단위 테스트를 통과한 모듈을 연결하여 전체 시스템으로 완성하여 통합적으로 시행하는 테스트

- 하향식 테스트 : 최상위 단계의 모듈들을 통합하여 테스트 한 후, 하위 단계로 내려가면서 테스트

- 상향식 테스트 : 최하위 단계의 모듈들을 통합하여 테스트 한 후, 상위 단계로 올라가면서 테스트

③ 인수 테스트 : 완성된 시스템을 인수하기 위해서 실제 자료를 사용한 최종 테스트

6. 유지보수 단계

시스템이 인수되고 설치된 후 일어나는 모든 활동이며, 소프트웨어 생명주기에서 가장 긴 기간이다.
[유지보수의 유형]
• 수정형 유지보수 − 사용 중에 발견한 프로그램의 오류 수정 작업
• 적응형 유지보수 − 시스템과 관련한 환경적 변화에 적응하기 위한 재조정 작업
• 완전형 유지보수 − 시스템의 성능을 향상시키기 위한 개선 작업
• 예방형 유지보수 − 앞으로 발생할지 모를 변경 사항을 수용하기 위한 대비 작업

소프트웨어의 품질은 정확성, 유지보수성, 무결성, 사용성에 따라 평가된다.

Copyrightⓒ2014 By 한빛아카데미(주)

<BCD코드>

6비트를 사용하며, 상위 2비트의 존비트와 하위 4비트의 숫자 비트로 구성된다.

[BCD 코드표]

<EBCDIC 코드>

8비트를 사용하며, 상위 4비트의 존 비트와 하위 4비트의 숫자 비트로 구성

[EBCDIC 코드표]

<ASCII 코드>

7비트를 사용하며 상위 3비트의 존 비트와 하위 4비트의 숫자 비트로 구성된다.

[ASCII 코드표]

<수치 자료의 표현>

1. 10 진수의 존 형식 표현

10진수 한 자리를 표현하기 위해서 1바이트(8비트)를 사용하는 형식이다.

존 영역은 상위 4비트이며, 항상 1111로 표현한다.

수치 영역은 하위 4비트이며, 표현하고자 하는 10진수 한 자리 값에 대한 2진수 값을 표시

[수치 영역에 값을 표현하는데 2진수와 10진수의 관계 표]

[여러 자리의 10진수를 표현하는 방법]

10진수의 자릿수만큼 존 형식을 연결하여 사용

마지막 자리의 존 영역에 부호를 표시 (양수(+) : 1100 =>C, 음수(-) : 1101  =>D)

2. 10진수의 팩 형식 표현

10진수 한 자리를 표현하기 위해서 존 영역 없이 4비트를 사용하는 형식이다.

최하위 4비트에 부호를 표시 (양수(+) : 1100 =>C, 음수( - ) : 1101 =>D)

3. 2진수의 정수 표현

최상위 1비트는 부호를 나타내고, 나머지 n-1비트는 2진수 값을 나타낸다.

① 부호 절대값 형식 표현

최상위 비트에 부호를 표시. 부호가 양수인 경우에는 최상위 비트를 0으로 하고, 음수인 경우에는 최상위 비트를 1로한다. 나머지 7비트는 2진수의 절대값을 표현

② 1의 보수 형식 표현

음수의 표현에서 부호 비트를 사용하는 대신 1의 보수를 사용하는 방법

[2진수를 1의 보수로 만드는 방법]

③ 2의 보수

음수의 표현에서 부호 비트를 사용하는 대신 2의 보수를 사용하는 방법

[2진수를 2의 보수로 만드는 방법]

4. 2진수의 실수 표현

① 고정소수점 표현 방식

소수점이 항상 최상위 비트의 왼쪽 밖에 고정되어 있는 것이다.

예를 들어 00011010은 0.00011010의 실수를 의미한다.

② 부동소수점 표현 방식

고정소수점 표현 방식보다 표현 가능한 값의 범위가 큼

실수 자료형은 4바이트나 8바이트로 표현하는데 4바이트의 부동소수점 표현 방식은 다음과 같이 표현.

Copyrightⓒ2014 By 한빛아카데미(주)

<자료구조>

자료를 효율적으로 표현하고 저장, 처리하기 위해 정리하는 것이 자료구조이다.

이론적인 측면 : 그래프, 집합, 조합, 확률이론으로 알고리즘을 분석하여 검색, 정렬방법 등을 결정.

효율적인 측면 : 공간적 효율성과 시간적 효율성을 기준으로 최상의 상태를 결정

실제적인 측면 : 자료를 문자열, 리스트, 트리, 파일 등의 구조로 실제적으로 표현하고 알고리즘을 구현하여, 프로그램과 파일 작성 및 메모리 관리, 운영체제 등에 사용한다.

<자료구조의 분류>

1. 선형구조

자료 간의 연결관계가 1:1관계를 갖는 순차 리스트와 연결 리스트, 스택, 큐, 덱이 있다.

자료의 논리적인 순서와 기억 장소에 저장되는 물리적 순서가 일치하는 구조이다.

2. 비선형 구조

계층 구조나 망 구조를 갖는 자료구조로 트리와 그래프가 있다.

3. 파일 구조

보조 기억 장치에 데이터가 실제로 기록되는 자료구조이다.

순차 파일과 색인 파일, 직접 파일이 있다.