본 포스팅은 Fundamentals of Data Structures in C++ 책에 있는 내용을 바탕으로 정리한 글입니다.
Index
- 시스템 생명 주기
- 객체 지향 설계(Object-Oriented Design)
- 데이터 추상화와 캡슐화
- c++의 기초
- 표준 템플릿 라이브러리(STL)
0. 개요
프로그램 과정
프로그램은 Input -> processing -> output 순서로 이루어져 있다.
Input
Input에는 데이터(값, 타입)가 들어가며 데이터 타입을 정의할 때는 각각 명세와 구현 방법이 있다.
- 명세는 데이터의 논리적 정의를 의미하며, 데이터가 무엇이고 각 연산은 무슨 기능을 수행하는지 정의한다.
- 구현은 실제 데이터가 어떻게 컴퓨터 저장장치에 표현되고 각 연산이 어떻게 구현되는지 정의한다.
processing
우리는 자료구조에 대해 공부하고 있기 때문에 processing 과정에는 자료구조에 대한 분류에 대해 설명하겠다.
우선 자료구조는 순차 구조와 비순차 구조가 있다.
순차 구조 : 자료의 논리적 순서가 물리적 인접성으로 표현되는 구조 ex) 스택, 큐
비순차 구조 : 논리적 순서, 인접성이 무관하며, 이를 표현하기 위해 별도의 방법이 필요한 구조 ex) 트리, 그래프
output
output은 위 두 과정을 거쳐 나온 값, 또는 어떤 함수를 출력하는 과정이다.
1. 시스템 생명 주기
시스템은 위에 설명한 대로 input, process, output을 합친 것을 일컫는 말이다.
시스템 생명 주기란 시스템 개발을 위한 일련의 단계인데 이 단계는 다음과 같다.
- 요구조건 분석
- 분석
- 설계
- 정제와 코딩
- 검증
1) 요구조건 분석 : 프로그래머에게 주어진 데이터의 입력과 프로그래머가 만들어야 하는 결과(출력)에 관한 정보를 기술한다.
2) 분석 : 상향식과 하향식 접근 방법으로 나뉘며, 보통 프로그래머들은 고수준의 계획부터 하위 수준의 세부 사항까지 분리하는 하향식 접근 방법을 선호하고 있다.
3) 설계 : 프로그램이 필요로 하는 데이터 객체들과 수행될 연산들의 관점에서 시스템에 접근하는 단계로 이 과정에서 시간을 많이 투자할수록 가장 효과적인 구현을 선택할 수 있을 확률이 높아진다.
4) 정제와 코딩 : 설계 과정을 거쳤으면 이제 그에 따른 알고리즘을 작성한다.
5) 검증 : 이 단계에서는 보통 정확성 증명(시간 복잡도, 공간 복잡도), 테스트, 오류 제거를 수행한다.
2. 객체 지향 설계
객체 지향 설계는 소프트웨어의 응용 분야의 개체를 잘 정의된 객체의 집합으로 보며, 이러한 객체는 서로 상호작용하여 소프트웨어 시스템을 형성한다. 주된 장점으로 코드의 재사용을 조장한다는 점이 있다.
2.1 기본적 정의와 개념
객체 : 자신의 상태를 가지며 계산을 수행하는 개체. 그 자체로 변수, 자료구조, 함수 또는 메서드가 될 수 있다.
구현 방법
- 객체를 기본적인 구성단위로 설정
- 각 객체를 어떤 클래스의 인스턴스로 설정
- 클래스는 상속 관계에 의해 서로 연관되어 있다.
조건
- 객체를 지원한다.
- 모든 객체는 클래스에 속한다.
- 상속을 지원한다.
이 세 가지 조건을 만족시켜야 객체 지향 언어라고 부른다.
3. 데이터 추상화와 캡슐화
데이터 추상화 : 데이터 객체의 명세와 구현을 분리하는 것, 무엇(what)? 과 어떻게(how)?를 독립시켜 놓은 것.
데이터 캡슐화
- 외부에 대해 데이터 객체의 자세한 구현을 은폐한다.
- 내부 표현을 사용자에게 은폐한다.
예를 들어, 집에 DVD 플레이어가 있을 때 우리는 재생, 정지, 빨리 감기 등의 버튼(추상화)을 통해 동작시키지만,
사실 DVD 플레이어 내부에는 우리가 내부 회로를 직접 건드릴 수 없도록 패키징 되어 있다. 따라서 DVD 플레이어는 추상화, 캡슐화되어 있다고 볼 수 있다.
3.1 C++의 기본적인 데이터 타입
밑에서 추상 데이터 타입(ADT)을 설명하기 이전에, 미리 C++의 기본적인 데이터 타입부터 살펴보자.
기본적으로 C++의 데이터 타입은 char, int, float, double과 저장 비트에 따라 나뉘는 short, long, signed, unsigned가 있다. 이 데이터 타입에 대한 구체적은 설명은 생략하도록 하겠다.
추가로 파생 데이터 타입이 있는데, 이는 포인터 * 와 참조 & 타입이다. 이들은 기본 데이터 타입으로부터 파생되고 종속적인 타입이라고 볼 수 있다.
3.2 추상 데이터 타입(ADT)
그렇다면 추상 데이터 타입이란 무엇일까?
앞에서 추상화의 예시로 들었던 DVD 플레이어의 재생, 정지, 빨리 감기 버튼처럼 실제 객체들 사이에서 동작하는 연산은 아니되, 객체의 표현을 더 강화한 데이터 타입이라고 볼 수 있겠다.
추상 데이터 타입의 예제로 MAXINT, MININT, Zero 등이 있는데 딱 봐도 최대, 최소 int 값, 0으로 유추할 수 있지만
그 자체로 연산이 되지 않는 그런 데이터 타입을 추상 데이터 타입이라 한다.
이들은 사용하는 코드 윗부분에 분명히 따로 구현되어있을 것이고, 명세하는 역할만 한다.
따라서 이러한 타입은 주로 데이터 추상화의 조건인 명세와 구현의 분리에 쓰인다.
3.3 데이터 추상화와 캡슐화의 장점
- 소프트웨어 개발의 간소화
- 검사와 디버깅의 단순화
- 재사용성 (별개의 개체로 구현된 자료 구조)
- 데이터 타입 표현 수정의 편리함
4. C++의 기초
보통 C++ 언어에 대해 설명할 때 "보다 나은 C"라는 표현으로 자주 묘사하는데, 이는 다음과 같은 의미를 갖는다.
- C와 공통적인 기능을 많이 가지고 있다.
- C를 개선하는 데이터 추상화나 상속과 무관한 많은 기능을 가지고 있다.
4.1 C++ 프로그램의 구성
C와 마찬가지로 C++ 프로그램은 헤더 파일과 소스 파일로 구성되어 있다.
헤더 파일은 뒤에. h 접미사를 가지거나 <iostream> 같은 시스템 정의 파일을 포함한다.
소스 파일은 C++의 소스 코드를 저장하기 위해 사용되며 보통 우리가 프로그램을 구현하는 공간이다.
4.2 C++에서의 영역(scope)
- 파일 영역 : 함수 정의에 속하지 않은 선언으로 클래스 정의, namespace는 파일 영역에 속한다.
- 네임스페이스 영역 : 논리적으로 연관된 변수나 함수를 한 그룹으로 만드는 기법으로 예를 들어 표준 라이브러리는 std라는 네임스페이스 안에 들어간다.
- 우리가 c++ 코드를 짤 때 맨 위에 써놓는 "using namespace std"는 본래 std::cout, std::cin처럼 std 영역 정보를 제공해 쓰는 코드를 단축시키는 효과를 가져온다.
- 지정 영역 : 블록 {, } 안에서 선언된 이름이다.
- 클래스 영역 : 클래스 정의에 관련된 선언이다.
변수는 자신의 영역과 이름으로 유일하게 식별되고, 자신의 영역 내에서만 식별될 수 있다.
4.3 C++ 함수 다중화
함수 다중화(function overloading)는 함수의 인자 리스트가 다르기만 하면 같은 이름을 가진 함수가 둘 이상 존재할 수 있다는 뜻이다. 예를 들면
- int max(int, int);
- int max(int*, int);
- int max(float, int);
이런 함수들은 전부다 한 파일에 선언될 수 있다.
4.4 C++ 동적 메모리 할당
C언어에서 동적 할당으로 malloc과 free를 배운 적이 있을 것이다.
C++ 언어에서도 그와 동일한 기능을 new, delete가 하게 된다.
- new : 원하는 타입의 객체를 생성하고 그에 대한 포인터 반환 ex) int *jp = new int [10];
- delete : new로 생성된 객체에 할당된 기억 장소를 반환 ex) delete [] jp;
4.5 C++ 예외처리
오류와 다른 특별한 조건이 발생했음을 알리는 데 사용하며, 예외 각각에 대한 예외 클래스를 정의한다.
구성은 다음과 같다.
try { 프로그램 코드 }
catch(예외 유형){
//예외 처리 코드
}
catch(예외 유형){
//예외 처리 코드
}
...
각 catch 블록은 예외 타입을 나타내는 한 인자를 가지며, try 블록에서 발생하면 throw를 통해 catch로 가게 된다.
4.6 인라인 함수(inline)
인라인 함수는 함수 정의 앞에 키워드 inline을 첨가하면서 선언된다. ex) inline sum(int a, int b)
이 inline 키워드는 함수 sum에 대한 모든 호출이 sum의 몸체(body)로 대체되어야 한다는 것을 컴파일러에 알려 함수 호출과 인자 복사 과정을 없앤다. 함정은 많이 사용하면 디버그 하기가 힘들다는 점이다.
5. 표준 템플릿 라이브러리 (STL)
C++ 표준 템플릿 라이브러리는 컨테이너, 어댑터, 반복자, 함수 객체, 알고리즘의 집합이다.
라이브러리는 알고리즘 문제를 풀 때도 많이 사용하는데 대표적으로 algorithm 라이브러리에 대해 살펴보자.
5.1 라이브러리 선언
STL 선언은 보통 #include <lib>로 선언된다. ex) #include <algorithm>
5.2 accumulate(start, end, initValue)
순차에 있는 원소들을 합산하는 데 사용되는 알고리즘이다. 배열의 start ~ end - 1 범위에 있는 원소를 합산하게 되고, 추가로 initValue의 값을 더한다.
5.2 copy(start, end , to)
copy 알고리즘은 원소 순차를 한 장소에서 또 다른 장소로 복사한다.
따라서 원소들은 start ~ end-1에서 to ~ to + end - start까지 복사된다.
5.3 next_permutation(start, end)
주어진 배열의 모든 순열을 순차적으로 생성해주는 알고리즘으로, 시간 복잡도 O(N!) 이기에 문제풀이에서 자주 사용되지는 않지만 눈으로 보기엔 좋다.
이 알고리즘은 start ~ end-1 범위에 있는 원소들의 다음으로 큰 사전식 순열을 생성한다.
예시로 1,2,3,4 순열을 next_permutation에 넣으면, 1,2,4,3을 받을 수 있게 된다. 이 알고리즘은 do~while문으로 사전 순 끝까지 리턴하게 할 수 있다.
