알고리즘(코딩테스트)
1, 2 주차 알고리즘 정리
gbleem
2025. 2. 17. 20:28
1. STL 기본 구조
STL이란
- C++ 내장 템플릿 기반 라이브러리
- 컨테이너, iterator, 알고리즘으로 구성되어 있다.
주요 컨테이너
- vector
- 동적 배열로 구현된 컨테이너
- 원소 삽입/삭제를 마지막 원소에 할때는 O(1)
- 랜덤 접근이 O(1)
- 중간 삽입/삭제는 비효율적
- list
- 이중 링크드 리스트 구조의 컨테이너
- 중간 삽입/삭제가 효율적
- deque
- 양뱡향으로 동적으로 동작하는 컨테이너
반복자
- 컨테이너를 순환하면서 정리하거나 가져다주는 역할
- 종류
- iterator
- reverse_iterator
- const_iterator
- inserter
알고리즘
- 정렬 관련 : sort, partial_sort, stable_sort, nth_element ...
- 탐색 관련 : find, binary_search, lower_bound, upper_bound ...
- 수치 관련 : accumulate, inner_product, adjacent_diffference ...
- 수정 관련 : fill, replace, remove_if, unique ...
2. map & set
map & set
1. map1-1. map 기본 개념key와 value 쌍으로 이루어져 있으며, key를 통해 value값에 O(1)에 접근할 수 있는 자료구조검색, 삽입, 삭제가 평균적으로 O(logN)의 복잡도를 가진다.내부 구현은 레드-블랙 트리
gbleem.tistory.com
3. priority_queue & Algorithms
우선순위 큐, 순열, k값 찾기
1. 우선순위 큐1 - 1. 기본 개념우선순위를 가지고 정렬 되어 있는 큐내부적으로 Heap 자료구조를 사용한다.삽입 삭제는 "항상" O(logN), 우선순위 높은 원소 검색은 O(1) 1 - 2. 사용하기기본적으로 가
gbleem.tistory.com
4. Algorithm Functions 1
알고리즘 관련 함수
정리 예정1. partial_sum2. uniqueunique 결과값이 필요없는 값들의 시작3. accumulate4. transform
gbleem.tistory.com
5. Algorithm Functions 2 + Tips
알고리즘 관련 함수 2 + 코테 Tip
1. 최대값 & 최소값 탐색주어진 컨테이너(주로 벡터나 string)에서 최대 혹은 최소를 구해주는 함수algorithm 헤더 include 필요min_element와 max_element 모두 리턴값은 해당 위치를 가리키는 iterator이다.strin
gbleem.tistory.com