＊오늘 학습 내용＊
코드카타 문제 / C++ STL
1. ✅ vector::end()와 back()의 차이와 올바른 사용법
-
vector::end()는 벡터의 마지막 원소 다음 위치를
가리키는 반복자(iterator)
→ *v.end()는 UB(정의되지 않은 동작) -
마지막 원소를 직접 가져오고 싶다면:
v.back() → 마지막 값을 안전하게 반환 -
*(v.end() - 1) → 가능하지만 덜 직관적
-
결론: 마지막 값을 사용하려면 back()을 우선적으로 쓰는 게 정석
2. ✅ abs() 함수의 활용과 조건 비교 최적화
-
abs(x)는 정수 x의 절댓값을 반환하는 함수 ( or 포함 시 사용 가능)
-
조건 예시:
if (abs(a - b) == 1) → a와 b가 1만큼 차이 나는지 확인 가능 -
두 조건을 하나로 단순화 가능함.(범위 계산시 매우 효과적)
a == b - 1 || a == b + 1 → abs(a - b) == 1 -
확장성도 높음:
→ 나중에 조건이 5 차이로 바뀌면 abs(a - b) == 5로만 변경하면 됨 -
정리: 양방향 거리 비교가 필요한 상황에서
abs()를 쓰면 코드가 간결하고 유지보수에 유리함.
3. ✅ lower_bound와 upper_bound를 이용한
범위 내 원소 개수 계산
- 정렬된 벡터 vec이 있을 때, 범위 [a, b]에 해당하는 값 개수를 구하려면:
*예시코드
auto lb = lower_bound(vec.begin(), vec.end(), a); // a 이상 첫 원소
auto ub = upper_bound(vec.begin(), vec.end(), b); // b 초과 첫 원소
int count = ub - lb;
lower_bound는 ≥ a인 첫 원소 반복자
upper_bound는 > b인 첫 원소 반복자-
두 반복자 차이로 [a, b] 구간에 포함된
원소 개수를 O(log N)으로 계산 가능 -
정렬된 배열의 구간 질의 처리에 매우 자주 쓰이는 패턴
4. ✅ next_permutation의 동작 원리와 실전 활용법
-
next_permutation(first, last)는 현재 배열을
사전식으로 다음 순열로 재배치 -
반환값:
→ 다음 순열이 있으면 true
→ 마지막 순열(내림차순)이면 false 반환 -
시작 전에 반드시 오름차순 정렬 필요 → sort(v.begin(), v.end())
*예시코드
sort(v.begin(), v.end());
do {
// 순열 사용
} while (next_permutation(v.begin(), v.end()));- 실전에서는 순열 완전탐색, 백트래킹, 조합 문제에서 자주 쓰임
9. ✅ nth_element 함수의 작동 방식과 안전한 사용 조건
- nth_element(first, nth, last)
→ nth 위치에 정렬 시 올 값이 오도록 배열을 재배치
특징:
-
전체 정렬을 하지 않음 ( 정렬 순서를 보장하지 않는다!)
-
nth보다 앞 원소들은 작거나 같음 (정렬 순서 보장 X)
-
nth보다 뒤 원소들은 크거나 같음 (정렬 순서 보장 X)
-
평균 시간 복잡도 O(N)
*예시코드
nth_element(v.begin(), v.begin() + 2, v.end());
cout << v[2]; // 정렬 시 3번째로 작은 원소
*안전 조건: v.size() >= n 확인 후 사용
*범위 벗어난 nth 반복자 사용 시 UB 발생- nth_element는 “정렬된 n번째 값을 빠르게 알고 싶을 때” 최적의 선택
