2024/06/21 2

[C++ STL] 2.6 그래프(graph)

그래프(graph)트리는 원형 또는 순환적인 종속성을 표현할 수 없다.하나의 노드에서 다른 노드로 이동하는 경로가 하나만 존재하기 때문에도로망을 생각해보자. 특정 노드에서 다른 노드로 이동하기 위한 다양한 경로가 존재할 수 있다.이러한 경우에는 그래프(graph) 구조를 사용해야 한다그래프 구분 - weight그래프는 노드 데이터뿐만 아니라 노드 사이의 에지 데이터도 저장해야 한다.도로망을 예로 들면 각각의 노드에 다른 어떤 노드들이 연결되어 있는지에 대한 정보를 가지고 있어야 한다.이런 방법으로 필요한 모든 노드와 에지가 있는 그래프를 만들 수 있다.이러한 그래프를 비가중 그래프(unweighted graph)라고 한다.에지에 가중치 또는 더 많은 정보를 부여할 수 있다.도로망에서 에지에 노드와 노드 ..

[C++ STL] 2.5 힙(Heap)

힙(heap)std::priority_queue에서 다룬 heap에 대해 더 깊이 있게 알아보자힙은 앞서 말했던 것처럼 다음과 같은 시간 복잡도를 만족해야 한다O(1) : 최대 원소에 즉각적으로 접근할 수 있어야 한다.O(log N) : 원소 삽입에 대한 시간 복잡도O(log N) : 최대 원소 삭제에 대한 시간 복잡도원소 삽입 또는 삭제에 대해 O(log N)의 시간 복잡도를 만족하기 위해 트리 구조를 사용해야 한다.특히 이 경우 완전 이진 트리를 사용해야 한다.완전 이진 트리는 트리의 데이터를 배열을 이용하여 저장할 수 있다.루트 노드를 배열 또는 벡터의 맨 처음에 저장하고, 그다음 레벨의 모든 노드는 왼쪽부터 오른쪽 순서로 저장한다포인터를 사용하지 않아서 메모리 사용 측면에서 효율적이다.부모 노드로..