vector <int> graph(N) 처럼 선언하셨다는 말씀이 아래처럼 선언하셨다는 의미이신가요? (vector <int> graph(N)면 1차원 벡터라서, 트리는 넣을 수 있어도 그래프는 넣을 수가 없어서 여쭤봅니다.)

int N;
// do something...
vector <int> graph[N];

예시 중에 아래와 같이 그래프 선언을 한 것이 있는데 비주얼 스투디오에서는 앞 서 언급된 vector<int>* graph = new vector <int>[N]; 로 사용하라고 되어있더라구요.

아래 코드도 1차원 벡터라고 생각을 했었는데, vector<int> graph[n] 과 vector<int graph(n)이 차이가 무엇인지 헷갈려서 질문 드렸습니다.

vector<int> graph[n+1];

3가지 선언 방법들은 서로 크고 작은 차이가 있습니다. 각각을 간단히 설명하면 아래와 같습니다.

1. vector<int> graph(n): 생성자에 길이 n을 넘겨주어 생성한 "1차원 벡터". 벡터의 원소 수가 n로 초기화됨.
2. vector<int> graph[n]: 배열 생성 문법으로 만든 "1차원 벡터"의 배열(즉, 2차원). 배열의 크기가 n이므로 "1차원 벡터"를 n개 가지고 있음. 각각의 벡터에는 아직 원소가 없음.
3. vector<int>* graph = new vector <int>[N]; "1차원 벡터"의 배열(즉, 2차원)을 동적 할당함. 전자와 마찬가지로 배열의 크기가 n이므로 "1차원 벡터"를 n개 가지고 있음. 각각의 벡터에는 아직 원소가 없음.

vector<int> graph[n]와 vector<int> graph(n)의 차이

전자와 후자는 대괄호를 사용했느냐, 소괄호를 사용했느냐의 차이인데, 대괄호를 사용한 전자는 vector형 원소를 n개 가진 1차원 배열(즉, 2차원)을 만들고, 소괄호를 사용한 후자는 vector 클래스의 생성자에 n을 넘겨줌으로써 길이가 n인 1차원 벡터를 만들게 됩니다.

그래서 전자는 2차원, 후자는 1차원 컨테이너라는 점에서 차이가 큽니다.

vector<int>* graph = new vector <int>[N];와 vector<int> graph[n]의 차이

우선, 두 방법 모두 2차원 컨테이너를 만든다는 점에서 같습니다. 그래서 대부분의 경우 완전히 같은 방법으로 사용할 수 있고, 문제가 생기는 경우도 드뭅니다.

하지만 두 방법은 실제 데이터가 할당되는 메모리 영역이 다르기 때문에 일부 문제에서 vector<int> graph[n]를 사용하면 '런타임 에러'나 '틀렸습니다'를 받을 수 있습니다.

vector<int>* graph = new vector <int>[N];와 같이 동적할당을 하면 이 벡터 데이터는 모두 힙(Heap) 영역에 할당됩니다. 힙 영역의 크기는 이론상 무한하기 때문에, 문제의 메모리 제한이 허용하는 한 마음껏 사용할 수 있습니다.

하지만 vector<int> graph[n] 처럼 선언하면 vector의 멤버변수들이 스택(Stack) 영역에 할당됩니다. 힙은 크기가 무한하지만 스택은 그렇지 않기 때문에(Linux에서는 8MB, Windows에서는 1MB) N이 몇 십만이 된다면 스택이 터지게 됩니다.

그리고 두 변수의 Lifetime도 다른데, 전자는 프로그래머가 명시적으로 delete[] graph;를 호출하기 전까진 메모리를 계속 차지하지만, 후자는 변수가 속한 블럭을 벗어나는 순간 사라집니다.

보통 트리를 표현해야 할 때는 1번 방법을 사용하고, 트리가 아닌 그래프를 표현해야 할 때는 2와 3중 하나를 사용하는 것이 일반적입니다. 그리고 2와 3중에서는 n이 충분히 작다면(100,000 미만) 쓰기 편한 2를, n이 크다면 안전한 3을 쓰는 편이 좋습니다.

와.. 진짜 명쾌하게 설명해주셔서 이해가 잘되었습니다 감사합니다!!