알고리즘 문제를 풀다가 흥미로운 경험을 했습니다. 저는 습관적으로 vector<T>를 즐겨 쓰고, 반복문도 range-based for를 자주 사용합니다. 그런데 vector<bool>을 사용했을 때는 문제가 생겼습니다.
1. range-based for에서의 오류
다른 타입에서는 잘 돌아가던 코드가 vector<bool>에서는 컴파일 에러를 냈습니다. 이유는 vector<bool>이 일반적인 vector<T>와 다르게 동작하기 때문입니다.
vector<bool>은 bool 값을 비트 단위로 압축 저장하기 때문에, 원소를 bool&로 반환할 수 없습니다. 대신 vector<bool>::reference라는 프록시 객체를 반환하는데, 이게 진짜 참조가 아니기 때문에 범위 기반 for문이나 함수 인자 전달에서 문제가 발생합니다.
2. 실행 시간 차이
또 한 번은 알고리즘 문제 풀이 후 채점 결과를 보면서 발생하였습니다.
제 코드와 다른 사람의 코드가 시간 복잡도 상으론 동일했지만, 제 코드는 실행 시간이 눈에 띄게 느렸습니다.
코드를 비교 했을 때 가장 큰 차이는
- 저는
std::vector<bool>을 사용했고, - 다른 사람은
bool[n]배열을 사용했습니다.
vector<bool>은 매 접근마다 비트 마스크 연산과 프록시 객체 생성이 들어가므로, 단순 메모리 참조만 하는 bool[]보다 훨씬 느릴 수밖에 없습니다. 반복 접근이 많은 BFS, DFS 같은 문제에선 이 차이가 성능에 직접적인 영향을 줍니다.
3. 결론
저는 이 두 가지 경험을 통해 vector<bool>이 일반적인 vector<T>와는 다른 점을 느낄 수 있었습니다. 특히 알고리즘에서는 유의미하기 때문에 따라서 상황에 맞는 적절한 자료구조를 선택하는 것이 필요합니다.
