Unique Life

출처: http://hyeonstorage.tistory.com/324

vector 컨테이너는 대표적인 시퀀스 컨테이너로 배열과 비슷하여 사용이 쉬우며 자주 사용된다.

vector는 임의 접근 반복자(Random Access Iterator)를 지원하는 배열 기반 컨테이너이다.

vector의 가장 큰 특징 중 하나는 원소가 하나의 메모리 블록에 연속하게 저장된다는 것이다.

그렇다 보니 원소가 추가되거나 삽입될 때 메모리 재할당이 발생할 수 있고 상당한 비용을 지불하게 된다.

그래서 메모리 할당 크기를 알 수 있게 capacity() 함수를 제공하며 한번에 메모리를 할당할 수 있는 reserve() 함수도 제공된다.

원소가 연속하게 저장되므로 [] 연산자 또는 at 으로 읽기에는 빠르지만  insert(), erase(), push_back() 등은 비효율적으로 동작한다.

시퀀스 컨테이너는 차례차례 원소를 추가하고 제거하는 push_back()과 pop_back()을 가지며, 첫 원소와 마짐가 원소를 참조하는 front()와 back()을 가진다. 또한, 지정한 위치에 원소를 삽입할 수 있는 insert()를 가진다.

vector는 앞쪽이 막혀 있는 형태로 앞쪽에는 원소를 추가/제거할 수 없으며 뒤쪽에만 추가/제거할 수 있다.

* vector 사용 예제 1

- v.reserve(8) : 벡터의 메모리 공간(capacity) 을 미리 할당한다. * 추가할당이 아님

- vector<int>::size_type : 벡터의 size 의 반환 타입을 가져온다 (unsigned int)

- v.resize(10) : 벡터의 원소 갯수를 수정한다. (size 를 줄여도 capacity는 그대로다)

- v.clear() : 벡터를 비운다 (capacity 크기는 그대로다)

- v.empty() : 벡터가 비워져 있는지 확인한다.

* for문으로 vector를 탐색할 때, v.size() 만큼 i를 돌리려면, v.size()의 타입과 i 가 같아야 한다.

* v.capacity()는 벡터에 할당된 메모리 공간이다.

새로운 원소가 벡터에 추가되면 메모리 공간이 추가적으로 할당된다.

매번 새로운 원소가 들어올 때마다 새로운 메모리가 할당되는 것은 비효율적이다.

capacity가 모자랄 경우 capacity/2 만큼의 capacity를 늘려간다.

만약 입력될 원소의 갯수를 알 수 있다면 reserve 를 사용하여 미리 capapcity 메모리를 할당해 놓으면 효율적이다.

* v.clear()를 사용하면 벡터의 원소를 비운다.

하지만 capacity는 그대로 남아 있다. 비어있는 벡터인데 메모리를 할당하고 있는 것은 아깝다.

이럴경우 clear()를 사용하기 보다 . 임시 벡터와 swap 을 통해 교환하면 메모리까지 해제할 수 있다.

* vector<int>().swap(v); : 임의 벡터와 swap을 하면서 벡터를 비우고 할당된 메모리(capacity)까지 해제한다.

* v.front()는 벡터의 첫번째 요소를 반환하고 v.back()는 마지막 요소를 반환한다.

* 벡터의 임의 요소에 접근하는 방법으로는 [] 연산자와 at 멤버함수가 있다.

[] 연산자를 사용하면 접근이 빠르지만 범위 점검을 하지 않는다.

at() 멤버 함수를 사용하여 접근하면 범위 점검을 수행하며, 범위에 벗어난 요소에 접근하면 out_of_range 예외를 throw 하여 예외를 처리할 수 있다.

출처:http://hyeonstorage.tistory.com/325

deque 컨테이너는 vector 컨테이너와 기능과 동작이 비슷한 컨테이너로 vector의 단점을 보완하는 몇가지 특징을 갖는다.

deque도 vector 컨테이너와 같이 시퀀스 컨테이너이며 배열 기반 컨테이너이다.

[C++/STL] - [STL] vector 벡터 정리 및 예제

deque 는 vector의 메모리 할당 단점을 해결하기 위해 여러 개의 메모리 블록을 할당하고 사용자에게는 하나의 블록처럼 보이게 하는 정책을 사용한다.

vector는 새로운 원소를 삽입할 때 할당된 메모리가 부족하면 이전 메모리 블록을 삭제하고 새로운 메모리 블록을 재할당하며 이전 원소를 모두 복사하지만, deque는 새로운 단위의 메모리 블록을 할당하고 원소를 삽입한다.

또한, 새로운 원소를 순차열 중간에 삽입 , 제거 하더라도 원소의 개수가 작은 쪽 으로 밀어낸다.

따라서 deque는 vector 보다 효율적으로 동작한다.

출처:http://janghw.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Backtracking-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9

백트래킹

정의 : 여러 해들 중에 조건에 맞는 모든 해를 찾는 알고리즘.

알고리즘

1. 후보 해를 선택한다.

2. 조건에 따라 후보 해에 적절성 검사를 시행한다. 통과하지 못하면 지금 현재 선택한 후보 해를 버리고 1로 돌아가 후보 해를 다시 선택한다.

3. 적설성 검사가 통과한 경우 이 후보 해가 문제의 해가 되는지 검사한다. 검사를 통과하면 이것이 문제의 해이고, 검사를 통과하지 못하면 1로 돌아가 후보 해를 계속해서 선택한다.

백트래킹의 활용

1. 미로 탈출로 찾기

재귀함수를 통해 백트래킹으로 미로 탈출로를 찾아보자. 

알고리즘

1. 시작점을 현재 위치로 지정하고, 이동방향을 북으로 설정한다.

2. 현재 위치에서 가고자 하는 이동 방향으로 이동이 가능한지 확인한다. 벽과 이미 지나온 길은 이동가능한 길이 아니다.

3. 현재 가고자 하는 이동 방향으로 이동이 가능하면 그곳으로 이동한다. 이동이 불가능하면 방향을 바꾸어 다시 2번을 수행한다. 모든 방향으로 이동이 불가능하면 이전 위치로 되돌아간다.

4. 출구에 다다르거나 미로 내의 모든 길을 방문할때까지 2, 3단계를 반복한다.

3번 과정에서 이동하는 부분을 재귀함수로 구현하면 될 것이다. 이동이 가능하면 재귀함수를 통해 그곳으로 이동하면 모든 방향으로 이동이 불가능하면 반환을 통해 재귀함수를 탈출하여 이전 상태로 돌아가면 될 것이다.

2. N개의 퀸

체스에서 퀸은 모든 방향으로 거리 제한없이 움직일 수 있는 말이다. N개의 퀸 문제는 N × N 크기의 체스판에서 N개의 말들이 서로 공격이 불가능하게 배치하는 모든 경우를 구하는 문제이다. 

알고리즘

1. 첫 행, 첫 열을 시작점으로 지정한다.

2. 현재 지점에서 퀸을 놓으면 다른 퀸에게 위협을 받는지 검사한다. 이전 단계에서 놓은 퀸들 중에 현재 지점에서의 퀸의 행 값이 같으면 수평방향으로 위협을 받는 것이고, 열 값이 같으면 수직방향으로 위협을 받는 것이다. 행의 차와 열의 차가 같으면 대각선 방향으로 위협을 받고 있는 것이다.

3. 위협을 받고 있지 않다면 행의 값을 증가시키고 열의 첫번째 값으로 가서 2를 수행한다. 위협을 받고 있다면 열의 값을 증가시켜서 2를 수행한다. 열의 마지막 값에서도 위협을 받고 있다면 이전 단계의 퀸의 위치로 되돌아간다.

4. 마지막 행, 마지막 열에 다다르면 종료한다.

과정 3을 재귀함수로 구현하면 될 것이다.

출처:http://janghw.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Dynamic-Programming-%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95

동적 계획법

정의 : 어떤 문제가 반복적이고 최적 하위구조로 이루어질때, 하위구조에 있는 부분 문제의 답을 기반으로 전체 문제의 답을 구하는 방법

최적 하위구조(Optimal Substructure)란 전체 문제의 답이 부분 문제의 답으로부터 만들어지는 구조를 말한다. 예를 들어 어떤 문제를 7개의 하위문제로 나눌 수 있을때, 7개의 하위문제의 답을 모두 얻어야 이 문제의 답을 구할 수 있다면 이 문제는 최적 하위구조를 갖추었다고 할 수 있다.

분할정복과 비슷해 보이지만, 분할정복은 문제를 큰부분에서 작은부분으로 나누는데반해(Top-Down), 동적 계획법은 제일 작은 부분부터 큰 문제로 풀어 올라간다(Bottom-Up). 또한 분할정복은 나눈 문제들을 완전히 새로운 하나의 독립된 새로운 문제로 보지만, 동적 계획법은 이전 단계의 답에 의존적이다. 그래서 한번 푼 적 있는 문제는 다시 푸는 일이 없도록 테이블 등에 저장해둔다.

알고리즘

1. 문제를 부분 문제로 나눈다.

2. 가장 작은 부분의 문제부터 답을 구한 뒤 테이블에 저장한다.

3. 테이블에 저장되어 있는 부분 문제의 답을 이용하여 점차적으로 상위 부분의 문제의 답을 구한다.

동적 계획법의 활용

1. 피보나치 수열 (Fibonacci Sequence)

피보나치 수열은 다음과 같이 정의할 수 있다.

이것을 그냥 코드로 옮기면 다음과 같이 작성된다.

이 알고리즘의 수행시간은 으로 상당히 비효율적이다.

동적 계획법을 이용하여 이 알고리즘을 재구성해보자.

먼저 문제를 부분 문제로 나눈다.

은  과 의 합이다. 은 와 의 합이다.

그리고 은 과 의 합이다. 이로부터 이라는 문제를 ,, …, , , 의 하위구조로 나눌 수 있는 것을 알 수 있다.

두번째로 작은 부분의 답을 구한뒤 테이블에 저장한다.

인덱스	저장된 값
0	0
1	1
2	1
3	2
4	3
5	5
6	8
...	...
n-2
n-1
n

과 는 이미 정의되어 있는 값을 저장하면 되고, 부터는 테이블에 저장된 값을 이용하여 답을 구해 나간다. 이렇게 계속 구해나가면 의 값을 구할 수 있다.

이렇게 구한 피보나치 수의 시간 복잡도는 이다.

분할정복으로 구한 시간 복잡도는 이였지만 동적 계획법으로 구한 시간 복잡도는 로써 분할정복보단 떨어진다. 더 나은 기법을 알기 위해서가 아니라 알고리즘 설계 기법의 이해를 위한 것이므로 뭐가 더 우수한지는 논외로 하기로 한다.