컬럼 url : http://www.zdnet.co.kr/column/column_view.asp?artice_id=20160905080503
IT, 비용인가 투자인가에 대한 위 url컬럼을 1장으로 요약
| [경제] 원자재,자본재, 중간재, 투자재, 생산재, 소비재 (0) | 2016.10.20 |
|---|---|
| [컬럼 요약] BEPS, 다국적 기업들의 조세회피 (0) | 2016.10.17 |
| 보안 오프소스 실무 활용 (홍석범) (0) | 2016.10.05 |
| Flow Chart 프로그램 (0) | 2016.09.25 |
| [엑셀] 엑셀 - 유령문자, 음표문자, 개행문자를 삭제하고자 할때... (0) | 2016.09.02 |
출처: 디지에코, KT경영경제연구소
[트렌드스펙트럼] 10월 2주차 분석보고서201610111476168679976-2.pdf
ict in china 2015_digieco201507101436493639161.pdf
트렌드스펙트럼은 삼성 및 facebook 트렌드를 다룬 파일이며, ict in china 의 경우 중국 ICT에 대해 다룬 파일입니다.
위 두 보고서를 보고, 한장 ppt로 간단 요약 정리를 해보았습니다.
| 2017년 중국 소비 현황 및 신흥 소비층 (0) | 2017.10.19 |
|---|---|
| 옴니프레즌스(온 오프라인을 결합한 쇼핑환경) (0) | 2017.02.18 |
| 데일리 디톡스 (0) | 2017.02.18 |
| 새로운 안식처 (0) | 2017.02.14 |
| 퓨처 푸드 (0) | 2017.02.14 |
출처: http://blog.naver.com/powersilk/10168065952
[경로탐색 알고리즘]
큐를 이용한 너비우선탐색 알고리즘(BFS - Breath First Search)
O. 들어가며
경로탐색 또는 길찾기 알고리즘을 공부할 때에 가장 기본적으로 이해하고 알고있어야 할 알고리즘은 깊이우선탐색(Depth First Search)과 너비우선탐색(Breath First Search)이다. 물론 실제 게임에서의 경로찾기는 A*알고리즘 등 최단경로 찾기 알고리즘을 사용한다. 혹은 네비게이션 맵을 이용하여 그래프를 구성하고 경로찾기를 구현하는 경우도 많이 있다. 이유는 A* 알고리즘이나 네비게이션 방법이 탐색 속도에서 훨씬 빠르기 때문이다. 이외에도 유전알고리즘이나 뉴럴네트워크와 같은 휴리스틱 알고리즘을 이용하기도 한다.
그러나 스택을 이용하는 깊이우선탐색이나 큐를 이용하는 너비우선탐색은 자료구조 및 알고리즘에서 기본이 되는 부분이기 때문에 반드시 이해하고 알고있어야 하는 부분이다. 여기서는 큐를 이용한 너비우선탐색 알고리즘을 다루도록 한다. 먼저 큐에 대한 설명을 간단히 하고, 큐를 이용한 너비우선탐색 알고리즘이 어떻게 동작하는지 살펴보도록 하겠다.
O. 큐(Queue)
큐는 스택과 함께 자료구조에서 꼭 이해하고 있어야할 부분 중의 하나이다. 큐는 FIFO(First-In, First-Out), 즉, 선입선출 방식의 자료구조이다. 프로그램으로 구현할 때에는 tail(or rear)에서 데이터 삽입이 진행되고, front에서 데이터가 삭제된다. 배열을 이용한 큐의 추상자료형은 다음과 같다.
enqueue(int item) 메쏘드는 tail 위치에 데이터를 추가하는 기능이고, dequeue() 메쏘드는 front 위치의 데이터를 제거하는 기능이다. 큐를 프로그램 코드로 작성하는 것은 큐에 대한 포스팅에서 자세히 다루도록 하겠다.
O. 너비우선탐색 (Breath First Search)
너비우선탐색은 시작 노드를 먼저 방문한 후 시작 노드에 인접한 모든 노드들을 우선 방문하는 방법으로 트리 또는 그래프에서 동일한 레벨에 있는 노드를 먼저 탐색하는 방법이다. 이에 따라 출발 노드에서 목표 노드까지의 최단 경로 찾기가 가능하다. 그러나 그래프의 사이즈가 클 경우 탐색 가지가 급격히 증가함에 따라 메모리 소모가 크며, 최악의 경우 모든 경로를 탐색하게 된다.
너비우선탐색은 큐를 이용하여 구현할 수 있다. 시작노드를 방문하고, 큐에 삽입한 후 큐가 빈 상태가 되거나 목적노드를 방문할 때까지 큐의 front에 있는 노드를 삭제한 후 이 노드와 인접한 노드들을 다시 모두 큐에 삽입한다. 이때 큐에 삽입되는 노드들의 Parent 노드는 큐에서 제거되는 노드로 설정한다. 이런 과정을 거치면 각 노드들의 Parent 노드가 결정되고, 목표노드에서부터 시작노드까지 Parent 노드들을 거꾸로 찾아가면 최종 경로를 찾을 수 있다. 이를 그림으로 설명하면 다음과 같다.
그래프가 다음과 같고 A를 시작노드로 하고, F를 목적노드로 할 때, 큐와 각 노드들의 Parent 노드 정보를 초기화 한다.
노드 A를 방문하고 이를 큐에 삽입한다. 그리고, A노드의 Parent 노드를 A로 설정한다.
이 때 A를 방문했다고 표시한다.
큐의 front에 있는 노드 A를 삭제하고, A와 인접한 노드 B와 G를 큐에 차례로 삽입한다. 같은 방법으로 노드 B와 노드 G의 Parent 노드를 큐에서 삭제된 노드 A로 설정한다. 노드 B와 G가 큐에 삽입될 때, 노드 B와 G를 방문했다고 표시한다.
위와 같은 방법으로 큐의 front에 있는 노드 B를 삭제하고, 이 노드와 인접한 노드 C와 E를 차례로 큐에 삽입한다. 이 때 노드 C와 E의 Parent 노드는 방금 전 큐에서 삭제된 노드 B가 된다.
최종적으로 목적 노드인 F를 방문한 후의 결과는 다음과 같다.
목적 노드까지 방문한 후에는 Parent 정보를 이용하여 시작노드까지의 경로를 거꾸로 탐색하면 된다. 목적 노드인 F의 Parent 노드는 노드 E가 되고, 노드 E의 Parent 노드는 B가 되며, 노드 B의 Parent 노드는 A가 된다. 즉, F->E->B->A가 되며 실제 프로그램에서는 이를 거꾸로 처리하면 시작노드 A에서 목적노드 F까지의 경로를 찾을 수 있다. 최종 결과의 모습은 다음과 같다.
O. 너비우선탐색 알고리즘
위에서 설명한 너비우선탐색의 알고리즘은 다음과 같다.
큐를 생성. 시작노드를 큐에 삽입하고 방문한 것으로 표시한다. 큐가 비어있지 않고 목적노드를 찾지 못하면 큐에서 front에 있는 노드를 얻어오고 이 노드와 인접한 모든 노드들을 큐에 삽입한다. 큐에 노드를 삽입할 때 삽입되는 노드들은 방문했다고 표시한다. 또한, 이 코드에서는 기술되지 않았지만, 큐에 삽입되는 모든 노드들의 Parent 노드들은 front에서 얻어온 노드로 설정한다.
O. 실행결과
아래 동영상은 자료구조 시간에 구현한 결과로 큐를 이용한 너비우선탐색 알고리즘을 이용하여 목적노드까지 탐색하는 과정을 나타내고 있다. 맵은 타일맵으로 구성되어 있으며, 검정색 타일은 벽을, 녹색 타일은 오브젝트로 하였다. 빨간 원이 너비우선탐색을 이용하여 탐색해가는 과정을 나타내고 있다.
O. 마치며
이번 포스팅에서는 큐를 이용한 너비우선탐색 알고리즘을 살펴보았다. 스택과 큐는 반드시 이해하고 알아야할 자료구조 중의 하나이다. 또한 너비우선탐색은 큐를 이용한 응용 중에 하나이며 깊이우선탐색과 더불어 길찾기알고리즘의 기본이 되는 알고리즘이다. 따라서 너비우선탐색 알고리즘의 동작원리를 이해하는 것은 매우 중요하다.
다음 포스팅에서는 지금까지 여러번 언급하였지만, 너비우선탐색 알고리즘과 함께 길찾기의 기본 알고리즘 중의 하나인 깊이우선탐색 알고리즘에 대해 살펴보도록 하겠다.
| Gradient Descent 탐색 방법 (0) | 2017.03.06 |
|---|---|
| 컨벌루션 신경망 ( Convolutional Neural Networks, CNN ) ~ 개요 (0) | 2017.03.06 |
| [C++] [STL] vector 벡터 정리 및 예제 (0) | 2016.10.15 |
| [C++] [STL] deque 정리 및 예제 (0) | 2016.10.15 |
| [알고리즘] Backtracking (백트래킹) (0) | 2016.10.14 |
출처: http://hyeonstorage.tistory.com/324
vector 컨테이너는 대표적인 시퀀스 컨테이너로 배열과 비슷하여 사용이 쉬우며 자주 사용된다.
vector는 임의 접근 반복자(Random Access Iterator)를 지원하는 배열 기반 컨테이너이다.
vector의 가장 큰 특징 중 하나는 원소가 하나의 메모리 블록에 연속하게 저장된다는 것이다.
그렇다 보니 원소가 추가되거나 삽입될 때 메모리 재할당이 발생할 수 있고 상당한 비용을 지불하게 된다.
그래서 메모리 할당 크기를 알 수 있게 capacity() 함수를 제공하며 한번에 메모리를 할당할 수 있는 reserve() 함수도 제공된다.
원소가 연속하게 저장되므로 [] 연산자 또는 at 으로 읽기에는 빠르지만 insert(), erase(), push_back() 등은 비효율적으로 동작한다.
템플릿 형식 | |
template<typename T, typename Allocator = allocator<T>> class vector | T는 vector 컨테이너 원소의 형식 |
생성자 | |
vector v | v는 빈 컨테이너이다. |
vector v(n) | v는 기본값으로 초기화된 n개의 원소를 갖는다. |
vector v(n,x) | v는 x 값으로 초기화된 n개의 원소를 갖는다. |
vector v(v2) | v는 v2 컨테이너의 복사본이다.(복사 생성자 호출) |
vector v(b,e) | v는 반복자 구간 [b,e)로 초기화된 원소를 갖는다. |
멤버함수 | |
v.assign(n,x) | v에 x 값으로 n개의 원소를 할당한다. |
v.assign(b,e) | v를 반복자 구간 [b,e)로 할당한다. |
v.at(i) | v의 i번째 원소를 참조한다. |
v.back() | v의 마지막 원소를 참조한다. |
p=v.begin() | p는 v의 첫 원소를 가리키는 반복자 |
x=v.capacity() | x는 v에 할당된 공간의 크기 |
v.clear() | v의 모든 원소를 제거한다. |
v.empty() | v가 비었는지 조사한다. |
p=v.end() | p는 v의 끝을 표식하는 반복자 |
| p=v.erase(p) | p가 가리키는 원소를 제거한다. q는 다음 원소를 가리킨다. |
| q=v.erase(b,e) | 반복자 구간 [b,e)의 모든 원소를 제거한다. q는 다음 원소 |
v.front() | v의 첫 번째 원소를 참조한다. |
| q=v.insert(p,x) | p가 가리키는 위치에 x 값을 삽입한다. q는 삽입한 원소를 가리키는 반복자다. |
v.insert(p,n,x) | p가 가리키는 위치에 n개의 x 값을 삽입한다. |
| v.insert(p,b,e) | p가 가리키는 위치에 반복자 구간 [b,e)의 원소를 삽입한다. |
| x=v.max_size() | x는 v가 담을 수 있는 최대 원소의 개수(메모리의 크기) |
v.pop_back() | v의 마지막 원소를 제거한다. |
| v.push_back() | v의 끝에 x를 추가한다. |
p=v.rbegin() | p는 v의 역 순차열의 첫 원소를 가리키는 반복자다. |
| p=v.rend() | p는 v의 역 순차열의 끝을 표식하는 반복자 |
| v.reserve(n) | n개의 원소를 저장할 공간을 예약한다. |
v.resize(n) | v의 크기를 n으로 변경하고 확장되는 공간의 값을 기본값으로 초기화 한다. |
v.resize(n,x) | v의 크기를 n으로 변경하고 확장되는 공간의 값을 x 값으로 초기화한다. |
| v.size() | v의 원소 갯수 |
v.swap(v2) | v와 v2를 swap한다. |
연산자 | |
v1==v2 | v1과 v2의 모든 원소가 같은가? (bool) |
v1!=v2 | v1과 v2의 모든 원소 중 하나라도 다른 원소가 있는가? |
v1<v2 | 문자열 비교처럼 v2가 v1보다 큰가? |
v1>v2 | 문자열 비교처럼 v1이 v2보다 큰가? |
v[i] | v의 i번째 원소를 참조한다. |
멤버 형식 | |
allocator_type | 메모리 관리자 형식 |
const_iterator | const 반복자 형식 |
const_pointer | const value_type* 형식 |
const_reference | const value_type& 형식 |
const_reverse_iterator | const 역 반복자 형식 |
difference_type | 두 반복자 차이의 형식 |
iterator | 반복자 형식 |
pointer | value_type* 형식 |
reference | value_type& 형식 |
| reverse_iterator | 역 반복자 형식 |
| size_type | 첨자(index)나 원소의 개수 등의 형식 |
value_type | 원소의 형식 |
시퀀스 컨테이너는 차례차례 원소를 추가하고 제거하는 push_back()과 pop_back()을 가지며, 첫 원소와 마짐가 원소를 참조하는 front()와 back()을 가진다. 또한, 지정한 위치에 원소를 삽입할 수 있는 insert()를 가진다.
vector는 앞쪽이 막혀 있는 형태로 앞쪽에는 원소를 추가/제거할 수 없으며 뒤쪽에만 추가/제거할 수 있다.
* vector 사용 예제 1
#include <iostream> #include <vector> using namespace std; int main(){ vector<int> v; v.reserve(8); // 벡터 메모리 공간 8 예약 할당 v.push_back(10); v.push_back(20); v.push_back(30); v.push_back(40); v.push_back(50); for (vector<int>::size_type i = 0; i < v.size(); ++i) cout << v[i] << endl; cout << endl; cout << "size : " << v.size() // 벡터 원소 개수 << " capacity : " << v.capacity() // 벡터의 할당된 메모리의 크기 << " max_size : " << v.max_size() << endl; // 최대 저장 가능한 원소 개수 cout << endl << "-- resize(10) -- " << endl; v.resize(10); // 벡터의 원소 갯수를 10개로 확장, 추가된 공간은 디폴트 0으로 채워진다. for (vector<int>::size_type i = 0; i < v.size(); ++i) // 벡터의 size 타입으로 i를 지정한다 (unsigned int) cout << v[i] << endl; cout << endl; cout << "size : " << v.size() << " capacity : " << v.capacity() << " max_size : " << v.max_size() << endl; cout << endl << "-- resize(3) -- " << endl; v.resize(3); // 벡터의 원소 갯수를 3개로 축소, capacity는 변화 없다. for (vector<int>::size_type i = 0; i < v.size(); ++i) cout << v[i] << endl; cout << endl; cout << "size : " << v.size() << " capacity : " << v.capacity() << " max_size : " << v.max_size() << endl; cout << endl << "-- vector clear() -- " << endl; v.clear(); // 벡터 비운다 capacity(메모리) 는 그대로 남아있다. if (v.empty()){ // 벡터에 원소가 없는지 확인한다. cout << "벡터에 원소가 없다." << endl; } cout << "size : " << v.size() << " capacity : " << v.capacity() << " max_size : " << v.max_size() << endl; return 0; } |
결과 : 10 20 30 40 50 size : 5 capacity : 8 max_size : 1073741823 -- resize<10> -- 10 20 30 40 50 0 0 0 0 0 size : 10 capacity : 12 max_size : 1073741823 -- resize<3> -- 10 20 30 size : 3 capacity : 12 max_size : 1073741823 벡터에 원소가 없다. size : 0 capacity : 12 max_size : 1073741823 |
- 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 을 통해 교환하면 메모리까지 해제할 수 있다.
#include <iostream> #include <vector> using namespace std; int main(){ vector<int> v(5); // 0으로 초기화된 5개의 원소 cout << "size : " << v.size() << " capacity : " << v.capacity() << endl; vector<int>().swap(v); // 임의 벡터와 교환한다. cout << "size : " << v.size() << " capacity : " << v.capacity() << endl; vector<int> v1; v1.push_back(10); v1.push_back(20); v1.push_back(30); v1.push_back(40); v1.push_back(50); cout << v1[0] << ", " << v1.at(0) << ", " << v1.front() << endl; // 첫번째 원소 cout << v1[4] << ", " << v1.at(4) << ", " << v1.back() << endl; // 마지막 원소 v1.front() = 100; v1.back() = 500; cout << v1[0] << ", " << v1.at(0) << ", "<< v1.front() << endl; // 첫번째 원소 cout << v1[4] << ", " << v1.at(4) << ", " << v1.back() << endl; // 마지막 원소 try{ cout << v.at(10) << endl; // 범위를 벋어난 호출 throw out_of_range 예외 } catch (out_of_range &e){ cout << e.what() << endl; } return 0; } |
결과 : size : 5 capacity : 5 size : 0 capacity : 0 10, 10, 10 50, 50, 50 100, 100, 100 500, 500, 500 invalid vector<T> subscript |
* vector<int>().swap(v); : 임의 벡터와 swap을 하면서 벡터를 비우고 할당된 메모리(capacity)까지 해제한다.
* v.front()는 벡터의 첫번째 요소를 반환하고 v.back()는 마지막 요소를 반환한다.
* 벡터의 임의 요소에 접근하는 방법으로는 [] 연산자와 at 멤버함수가 있다.
[] 연산자를 사용하면 접근이 빠르지만 범위 점검을 하지 않는다.
at() 멤버 함수를 사용하여 접근하면 범위 점검을 수행하며, 범위에 벗어난 요소에 접근하면 out_of_range 예외를 throw 하여 예외를 처리할 수 있다.
| 컨벌루션 신경망 ( Convolutional Neural Networks, CNN ) ~ 개요 (0) | 2017.03.06 |
|---|---|
| [경로탐색 알고리즘] 큐를 이용한 너비우선탐색 알고리즘(BFS - Breath First Search) [출처] [경로탐색 알고리즘] 큐를 이용한 너비우선탐색 알고리즘(BFS - Breath First Search)|작성자 Android Kang (0) | 2016.10.15 |
| [C++] [STL] deque 정리 및 예제 (0) | 2016.10.15 |
| [알고리즘] Backtracking (백트래킹) (0) | 2016.10.14 |
| [알고리즘] Dynamic Programming (동적 계획법) (0) | 2016.10.14 |
IT, 비용인가 투자인가.pptx