백준10810과 에러

문제 링크

백준 10810

SOlved기준 티어

브론즈 3에서 2정도로 많이 평가 받음

풀이 및 유의사항

제시된 N과 M이 모두 100이하로 범위가 작아서 벡터나 배열 중에 편한 쪽으로 사용
또한 범위가 작으니, 이분탐색 등으로 탐색 범위를 고민하기 보다는 정확하게 풀기

정답 코드

#include<iostream>
#include<vector>
using namespace std;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, m;
	cin >> n >> m;
	vector<int>v(n+1);
	for (int i = 0; i < m; i++) {
		int s, e, idx;
		cin >> s >> e >> idx;
		for (int j = s; j <= e; j++) {
			v[j] = idx;
		}
	}
	for (int i = 1; i <= n; i++) {
		cout << v[i]<<" ";
	}
	return 0;
}

1차 제출 런타임 에러

DoubleFree

동일한 heap공간에 대해 메모리의 해제를 2번 해주면서 일어나는 에러

수정 후 정답처리

벡터의 size가 부족하여 생긴 문제로 판단하여 크기 변경 후 정답처리 확인
v의 크기를 n이 아닌 n+1로 변경

어디 지점에서 에러가 발생하였는가

두번쨰 for문에서 범위를 초과하는 것이라고 생각하여,
v[j]=idx;보다 앞에서 v.resize(n+1)을 하니 제대로 동작하는 것도 확인 하였다.

그런데 왜 out of range가 아니라 DoubleFree오류?

크기를 잘못 잡아서 오류가 뜬 것은 3분 이내로 바로 캐치했으나,
오류 메시지가 이상했다.
분명 탐색 도중에 크기인 n을 넘었으니 out of range가 떠야하는데
처음보는 오류가 떴다.
배열이었으면 범위에 대한 에러가 떠야하나 벡터였기 때문에
아마 작동방식의 차이에서 다른 에러가 발생했음을 짐작할 수는 있었다.

벡터의 작동방식

기존에 잘못 이해한 개념

vector은 크기가 자유롭다.
따라서 -1인덱스를 참조해도 에러가 발생하지 않아, 문제풀이 시 자유자재로 편리하다.
그런데 크기가 자유롭다는 것을 잘못 이해하여 크기의 범위를 넘어선 탐색도 문제가 없다고 착각하고 있었다

벡터의 초기화와 크기

아까처럼 v(n)으로 초기화를 하면 v의 크기는 n이 되고 그 안의 모든 요소는 0으로 초기화 되는 것이다

#include<iostream>
#include<vector>
using namespace std;
int main() {
	vector<int>v(10);
	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << " "; // 0 0 0 0 0 0 0 0 0 0
	}
	return 0;
}

위 코드를 보면 어떻게 초기화가 되는지는 잘 알 수 있을 것이다.

벡터의 제대로된 개념과 연관자료

vector은 메모리 heap에 동적할당되는 자료의 길이를 변경할 수 있는 배열이다.
벡터와 메모리heap에 대해 알고싶다면
메모리의 구조

위의 두 글을 통해 알 수 있던 점은 벡터는 메모리를 기반으로 하고
그렇기 때문에 -1 인덱스는 참조가 가능하여도
범위를 넘어서는 index의 참조를 시도하면 재할당을 시도하여 아까와 같은 에러가 뜬다는 사실이다