1장 - 기본개념

자료구조와 C++ 1장 정리

목차 

1. 시스템 생명 주기
2. 객체 지향 설계
3. 데이터 추상화와 캡슐화
4. c++의 기초
5. 알고리즘 명세
6. 표준 템플릿 라이브러리
7. 성능 분석과 측정

1. 시스템 생명주기

Data Structure(자료구조) - Sequential (순차적) : 배열

                                 - Non-Sequential (비순차적) : 연결 리스트

- 스택, 큐, 트리, 그래프는 둘 다 표현 가능

 

먼저 시스템은 Input - Process - output의 단계를 거친다.

 

이에 생명주기는

① 요구조건 -> ② 분석 -> ③ 설계 -> ④ 정제와 코딩 ->⑤ 검증 단계를 거친다.

 

2. 객체 지향 설계

객체 지향 설계 vs 구조화 프로그래밍

 

유사점 : 분할 - 정복 기법 사용

차이점 : 분할 방법

객체 지향 설계	구조화 프로그래밍
소프트웨어 = 객체의 집합 소프트웨어를 객체로 분해 재사용성 변경에 유연 (객체만 수정하면 됨)	소프트웨어 = 프로세스 프로세스의 스텝을 나타낸다 모듈로 분해 전통적 프로그래밍

객체 -> 데이터 + 연산 +oid(객체 식별자)

 

객체 지향 언어의 조건 : 객체 지원, 모든 객체는 class에 소속, 계승 지원

 

3. 데이터 추상화와 캡슐화

데이터 캡슐화 - 외부에 대해 내부 표현을 사용자에게 은폐 (정보 은닉) ex. private(전용) 멤버 함수로 선언

데이터 추상화 - 데이터 객체의 명세와 구현을 분리 ex. 멤버 함수의 선언은 class내에서, 구현은 class밖에서

데이터 캡슐화와 추상화의 장점 

• SW 개발 간소화
• 디버깅 단순화
• 재사용성
• 데이터 타입 표현의 수정

 

C++의 데이터 타입

• 기본 데이터 타입 : char, int, double, float... (타입 수식어 - short, long, unsigned, signed)
• 파생 데이터 타입 : pointer, reference(참조)
• 데이터 캡슐화 구조 : structer, class, array
• 사용자 정의 데이터 타입 : user defined data type

추상 데이터 타입 (ADT) : 객체의 명세와 객체에 대한 연산의 명세를 객체의 표현과 연산의 구현으로부터 분리시킨 데이터 타입 (사용자 정의 타입도 이에 해당) -> 명세와 구현을 분리한다는 것이 중요!

 

	데이터	연산
추상화	ADT	알고리즘
구체화(구현)	데이터 타입	프로그램

 

4. C++의 기초

C++에서의 영역

• 파일 영역 : 함수 정의에 속하지 않은 선언
• 네임스페이스 영역 : 논리적으로 연관된 변수나 함수를 한 그룹으로 묶은 영역 (이름 공간)
• 지역 영역 : 블록 안에 선언된 이름 ex. (), {},...으로 이루어진 블록
• 클래스 영역 : 클래스 정의에 관련된 영역

Q1) 블록 안에서 전역 변수의 이름을 지역 변수로 다시 사용했을 때, 전역 변수 접근 방법은?

A1) int y=:: x   ->영역 연산자 : 가장 바깥에 있는 x 사용

 

Q2) 어떤 전역 변수가 file1.c에 정의되어있고, file2.c에서 사용되어야 한다. 어떻게 선언해야 사용할 수 있는가?

A2) extern int x; ->extern은 외부에 있는 변수, 전역 변수를 쓸 것이란 이야기이다.

 

Q3) 한 프로그램에서 file1.c와 file2.c가 같은 이름의 전역 변수를 사용하였다. 변수명을 바꾸지 않고 사용하는 방법은?

A3) static int x; -> 정적 전역 변수 = 이것에 해당되는 파일에서만 유효한 변수

 

지역 변수의 정적 변수화 -> 함수 내에서 static으로 선언이 되면 함수 실행 시 초기화되지 않음

추가적으로

const -> 상수 변수         ex. const int Max=500; -> Max 변수를 500으로 고정

enum -> 열거 타입         ex. enum semester {Spring, Summer, Fall, Winter};

 

매개 변수 전달 방법

call by value	call by reference
전달된 객체를 값으로 받음 저장소에 복사, 실인자 영향X ex) void bfs (int x) {};	전달된 객체의 주소만 저장 직접 접근을 하므로 실인자 영향 O 타입 명세자에 & 추가 ex) void bfs (&const int x)

call by reference로 매개 변수 전달 시 실 인자가 변하는 것을 원하지 않는다면 const(상수 참조) 사용!!

 

C++ 메모리 동적 할당

동적 할당 시 - new

메모리 해제 시 - delete

ex) int * kr = new int [10]     //kr이라는 이름의 int형 배열의 크기를 10으로 할당하겠다.

    delete [] kr;                   //kr의 메모리 해제

 

inline 함수 -> 함수 호출과 인자 복사의 오버헤드를 줄임, 함수를 호출하지 않고 바로 실행

 

5. 알고리즘 명세

알고리즘 - 특정 일을 수행하기 위한 명령어의 유한 집합

요건 

• 입력, 출력
• 명백성 : 모호하지 않은 명확한 명령
• 유한성 : 반드시 종료되어야 함
• 유효성 : 기본적, 실행 가능

ex. flowchart 가 알고리즘이 아닌 이유 - 명백성, 유효성 결여

 

선택 정렬, 이원 탐색 코드 등은 https://github.com/kimtaehyun98/-에 정리해 놓았음

 

6. 표준 템플릿 라이브러리 (Standard Template Library)

STL 사용 시 이미 많은 기본적인 함수들이 정의되어 있기 때문에 보다 빠르고 쉽게 코드를 작성 가능하다.

예시는 위의 github에 정리해 놓았다.

 

7. 성능 분석과 측정

• 명세에 부합
• 정확히 작동
• 문서화
• 논리적 작업 단위를 위한 함수 효과적 이용
• 코드의 판독 용이
• 메모리 효율적 사용
• 적절한 시행 시간

프로그램에 필요한 공간

고정 공간 요구 : c

 -> 명령어 공간, 단순 변수, 고정 크기의 구조화 변수

가변 공간 요구 : Sp(I)

 -> 문제의 인스턴스, I에 의존하는 공간, 즉 가변 공간, 스택 공간

따라서 공간 요구량은 S(p) = c + Sp(I)

 

시간 복잡도 : 컴파일 시간 + Tp(실행시간)인데 컴파일은 한번 완료 후에는 더 이상 하지 않으므로 고려하지 않음

 

점근 표기법 - 정확한 단계의 계산이 무의미 하기 때문에 평균,최대 수행 단계수를 구하는 방법

O(n) - f(n) <= c * g(n)이고, 모든 n이 n>n0 인 어떠한 n0와 c가 존재한다면, f(n)=O(g(n)) 이다.

- 가장 작은 g(n)을 O(n)으로 표시한다, n>n0인 모든 n에 대하여 f(n)의 상한 값은 g(n)이 된다.

Ω(n) - f(n) >= c * g(n)이고, 모든 n이 n>n0 인 어떠한 n0와 c가 존재한다면, f(n)=Ω(g(n)) 이다.

- n>n0인 모든 n에 대하여 f(n)의 하한 값은 g(n)이 된다.

Θ(n) - c1 * g(n) <= f(n) <= c2 * g(n)이고, 모든 n이 n>n0 인 어떠한 n0와 c1,c2가 존재한다면, f(n)=Θ(g(n)) 이다.

- 상한값과 하한값 모두 가짐

시간 복잡도와 매직 스퀘어 관련 코드는 https://github.com/kimtaehyun98/-

kimtaehyun98/-