gksrudtlr
|2025. 2. 19. 09:08
STL
- STL이란?
- C++ 내장 템플릿 기반 라이브러리
- 크게 컨테이너, 반복자, 알고리즘으로 구성
- 종류
- Vector
- 동적으로 구현된 컨테이너
- 연속적 메모리 블럭을 사용해 랜덤 접근이 가장 빠름
- 원소를 추가/삭제할 때 마지막 원소에 대해 가장 효율적
- Map
- Key, value를 한쌍으로 묶어 관리
- 키는 유일하며 검색 삽입 삭제가 평균적으로 O(logN)
- set
- 키만 저장 가능, value가 따로 필요 없을 때 사용
- 중복이 불가하며 이미 원소가 존재하지 않으면 다시 넣어도 들어가지 않음
- 검색 삽입 삭제가 평균 O(logN)
- multimap
- multiset
- priority_queue
- queue와 달리 선입 선출이 아니라 들어온 값들의 우선 순위를 부여해 우선순위 순서대로 되어있는 큐
- 내부적으로는 힙 구조를 사용
- 삽입/삭재는 항상 O(logN), top()은 가장 우선 순위가 높은 원소로 조회시 O(1)
- 가장 큰/작은 원소를 순식간에 추출하는 문제에서 최적
반복자
- 반복자란?
- Iterator는 데이터를 순차적으로 접근할 수 있게 해주는 객체
- STL용 포인터
- 종류
- reverse_iterator
- 컨테이너를 역순으로 순회할 때 사용
- rbegine(), rend()를 사용
- 상수 반복자(const_iterator)
- 컨테이너의 데이터를 수정할 수 없는 반복자
- read only용도로만 사용
- 삽입 반복자
- 컨테이너에 새로운 원소를 삽입할 때 사용
- back_inserter, front_inserter, inderter가 있음
레드블렉 트리
- 래드블랙 트리란?
- 이진 탐색 트리의 일종으로 편향되지 않고 트리의 높이를 logN으로 유지
- 노드가 빨간색인지 검은색인지 판단해 균형잡힌 트리를 만들어 탐색 속도가 빨라짐
- 규칙
- 균형을 이뤄야함
- 깊이를 기준으로 검은 리본의 갯수가 어디서나 같이야 함
- 빨간 리본이 이어지면 안됨
- 빨간 리본을 단 나무가 연달아 나오면 재배치
- 이 규칙 덕분에 균형을 이룸
- 최상위 부모 노드는 검은색
- 데이터 추가
- 새로 추가하는 노드는 빨간색으로 추가 후 빨간 리본이 이어지면 재배치
- 데이터 삭제
- 검은 리본이 없어지면 같은 층의 검은 리본의 갯수가 깨질 수 있어 나무 위치 조정
STL 함수
순열
- 순열이란?
- 순서가 정해져있는 수의 배열
- STL 제공되는 next_permutation/perv_permutation을 사용하면 편하게 값을 구할 수 있음
- 이미 정렬된 상태의 컨테이너 사용
k 번째 값
- nth_element
- pivot 기반 n번째 작은 원소를 배열의 n 번째 위치로 보낸 뒤, 그 왼쪽은 n 보다 작은 원소, 오른쪽은 큰 원소로 반 정렬 됨
- 퀵소트와 유사
- 편균 시간 복잡도는 O(n)
연속합 구하기
- partial_sum
- numeric 헤더에 포함된 함수
- 컨테이너의 시작부터 끝까지 누적합을 구해 새로운 컨테이너에 저장
유니크 값 구하기
- unique
- 연속된 중복 원소를 제거하여(끝 위치) iterator를 반환하는 함수
- 정렬이 필요한 함수로
- erase등을 사용하여 iterator부터 컨테이너의 끝부분까지 삭제해 중복된 값을 제거해야함
총 합 구하기
- accumulate
- numeric 헤더에 포함된 함수
- 컨테이너의 총 합을 구하는데 사용
- 기본 초기값은 0 또는 원하는 값으로 사용 가능
- 4번째 인자에 따라 다른 사칙연산도 가능
빠른 이진 탐색
- 정렬된 구간에서 이진 탐색을 깔끔히 제공
- 이진 트리를 탐색해 원하는 값을 찾을 수 있음
- 시간 복잡도 O(logN)
- lower_bound
- upper_bound
원소 변환
- transform
- 1,2 인자 : 변환할 원소들의 입력구간
- 3 인자 : 변환된 원소들을 저장할 출력 구간의 시작 위치
- 4 인자 : 각 원소에 적용할 변환 함수
- 단항 연산
- 각 원소를 하나씩 반환
- ex) 제곱, 2배 ...
- 이항 연산
- 두 구간의 원소들을 짝지어 변환
- ex) 같은 인덱스끼리 합, 곱하기 ...
최대/최소 값 탐색
- max_element
- 컨테이너에서 최대 값을 가진 이터레이터를 반환
- min_element
- 컨테이너에서 최소 값을 가진 이터레이터를 반환
특정 조건을 만족하는 원소 구하기
이터레이터 이동
- distance
- 첫번째 이터레이터와 두번째 이터레이터의 거리(두 개의 차)를 반환
- advance
코테 노하우
헤더 파일
- #include <bits/stdc++.h>
- GCC전용 헤더로 c++ 표준 라이브러리를 모두 포함시킴
- 사용 불가할 때도 있음
효율적 입출력
- ios::sync_with_stdio(false), cin.tie(nullptr)
- c 표준 입출력과 c++스트림을 분리해 동작하게 하여 버퍼링 효율이 좋아짐
- \n
- endl을 사용하면 출력 버퍼가 강제로 flush돼서 느려질 수 있으나 큰 문제의 반복 출력할땐 \n이 선호
- getline(cin, string)
- 문자열 전체를 입력받는 함수
- 공백이나 탭 같은 구분 문자도 읽을 수 있음
- 한줄 통째로 string에 저장
문제풀이 팁
- 제한 사항과 입력 크기 다시보기
- 예외 케이스 챙기기
- 문제 풀었을 때 틀렸다면 예외 케이스를 챙겨 다시 풀기
- 빠른 코딩 테스트 제출
- 빠르게 초기 코드르 짜 제출한 뒤 틀렸다면 빠르게 정
