C++자료구조
[자료구조]그래프의 표현
그래프를 표현하는 방법 인접 행렬 -정점들 사이의 인접관계를 행렬을 이용하여 표현하는 방법 그래프 G=(V,E):n개의 정점을 갖는 (|V(G)|=n>=1) 그래프 → 인접 행렬 A의 표현 A = (a ij ) : 2차원 n×n 배열. a ij = 1, if(vi, vj) E(G)에 포함 a ij = 0, if(vi, vj) E(G)에 미포함 -장점: 임의의 두 정점 사이에 간선이 있는지를 쉽게 결정할 수 있고, 정점의 차수(degree)를 쉽게 계산할 수 있다. -방향 그래프(diagraph)의 경우는 모든 행의 합이 진출차수가 되고, 모든 열의 합이 진입차수가 된다. -단점: 주어진 그래프 내에 간선의 수를 계산하거나 그래프가 연결그래프인지를 결정하는 등의 문제를 해결할 때는 많은 시간을 요구한다.(..
[C++자료구조]DFS(깊이우선탐색)와 BFS(너비우선탐색)
DFS(Depth-first Search)깊이 우선 탐색은 출발 정점 v를 방문함으로써 시작된다. 다음으로 v에 인접하면서 아직 방문하지 않은 한 정점 w를 선택하여 이 w에서 다시 깊이-우선 탐색을 시작한다. 인접 정점들을 이미 모두 방문한 정점 u에 도달하면, 마지막으로 방문한 정점 중 아직 방문하지 않은 인접 정점 w를 가지고 있는 정점까지 되돌아가서 정점 w로부터 깊이-우선 탐색을 다시 시작한다. 이러한 탐색은 방문을 한 정점들로부터 방문하지 않은 정점으로 더 이상 갈 수 없을때 종료된다. 인접리스트 쓰는 경우 복잡도는 O(e)이다. e는 간선개수다. 인접행렬 쓰는 경우 인접한 모든 정점들을 결정하는 데 O(n)의 시간이 걸린다. 그러므로 최대 n개의 점을 방문해야하므로 복잡도는 O(n^2)이다...
[C++] fill함수
템플릿 함수 template void fill (ForwardIterator first, ForwardIterator last, const T& val); value(값)으로 범위를 Fill range 범위[first,last)안에 있는 모든 elements에 val(값)을 할당. 위의 템플릿함수는 아래와 같다: template void fill (ForwardIterator first, ForwardIterator last, const T& val) { while (first != last) { *first = val; ++first; } } 매개변수 -first, last 처음과 마지막의 iterator(커서/포인터)로 T데이터타입의 값할당을 elements의 순차적위치로 보여준다. 그래서 first..