STL로 구현하는 그래프 그래프란 * 동그라미 = vertex = 정점 화살표 = edge = 간선 * 언제 사용하는가? >> 연결관계가 중요할 때 and 연결관계가 복잡하게 얽혀있을 때 * 그래프 특성 추가 >>간선 방향의 유무 (양방향 or 일반통행) >>간선 가중치 유무 (각 간선의 값이 동일하지 않다.) 정점 (vertex) struct Vertex { // 데이터 // 연결관계 }; * vertex는 구조체, 클래스 등으로 구현할 수 있다. * vertex는 (데이터 + 연결관계)를 가지고 있어야 한다. * 그래프에는 많은 vertex가 있으므로 배열등으로 묶어서 관리한다. 간선 (edge) * 간선은 보통 해당 vertex에 종속된다. (간선이 혼자 있을 수는 없으니까) * vertex 내부에..
STL - Standard Template Library STL * C++에서 제공하는 표준 라이브러리이다. * STL을 사용해 기본적인 자료구조를 구현, 사용할 수 있다. (리스트, 큐, 스택, 맵, 셋, 등등...) * 이러한 저장 공간을 Container라고 부르기 때문에 Containers Library라고도 부른다. * STL에서 할당된 메모리를 알아서 관리해 준다. (생성, 삭제, 크기 변경 모두 해준다.) STL가 생각했던 목적 * C++는 Container 라이브러리에 특별한 목적을 넣었는데, 서로 다른 자료구조를 마치 다형성처럼 사용하고 싶었던 것 같다. 아니면 공동 인터페이스 구현? (아마도) * Iterator(반복자)라는 포인터 비슷한 객체가 있는데, 이 반복자를 사용해 요소에 접근..
동적 배열 특징 배열의 특징 * 배열이라고 하면 기본적으로 생각하는 특징들이 있다. * 인덱스를 사용해 요소에 접근한다. * 메모리는 빈틈없이 이어져 있는 하나의 덩어리다. * 데이터의 순서를 중요하게 생각하기 때문에 중간 삽입이나 삭제 시 비용이 크다. (순서유지를 위해 한 칸씩 밀어야 하기 때문에) * 유효한 데이터 사이에 쓰레기 값은 없다. (배열[10]일때 데이터를 5개 넣는다면 0~4까지 넣는다. ) (1, 3, 6, 7, 8처럼 제멋대로 넣지 않는다.) 동적 배열 * 동적 배열은 너무나 자주 사용하기 때문에 대부분의 언어에서 공식 라이브러리로 지원한다. * 위에 특징은 유지하며, 힙 메모리에 만들면 그게 동적 배열이다. 동적 배열 특징 * 힙 메모리에 할당하는 게 특징이다. * 운영체제를 거치..
