[내일배움캠프 Day42] 알고리즘 수업 Wrap-Up

STL이란?

STL은 C++에 내장된 템플릿 기반의 라이브러리이며, 크게 컨테이너, 반복자(Iterator), 그리고 알고리즘으로 구성되어 있다.

• 컨테이너(Container): 데이터를 저장·관리하는 구조체(자료구조)들의 집합
• 반복자(Iterator): 컨테이너 내 데이터를 순회(Navigation)할 수 있도록 도와주는 일종의 '포인터' 역할
• 알고리즘(Algorithm): 정렬, 탐색, 삽입, 삭제 등과 같은 로직을 매우 효율적이고 제네릭하게 제공

https://dev0404.tistory.com/5

[사전 캠프 Day4] STL

 

순차 컨테이너(sequential container)

https://dev0404.tistory.com/53

[내일배움캠프 Day31] 순차 컨테이너

 

연관 컨테이너(associative container)

• map: 키(key)와 값(value)을 한 쌍으로 묶어서 관리
  • 키는 유일해야 하며, 검색, 삽입, 삭제가 평균 O(log N)
    • 이게 가능한 이유는 내부적으로 이진 탐색 트리(레드-블랙 트리)를 사용하기 때문!
  • 주요 함수
    • insert(pair): 키-값 쌍 삽입
    • erase(key): 키로 요소 제거
    • find(key): 키로 요소 검색 (iterator 반환)
      • key가 있으면 해당 key의 iterator를 반환하나 없으면 end() 리턴!
    • operator[key]: 키로 값에 접근 또는 삽입
    • size(): 요소 개수 반환
• set: 키만 저장. 즉, value가 따로 필요 없을 때 사용
  • 중복이 불가능 → 즉, 어떤 원소가 이미 있으면 다시 넣어도 들어가지 않음
  • 역시나 검색, 삽입, 삭제가 평균 O(log N)
    • 내부 구조는 map과 동일(레드-블랙 트리). 단, 키만 존재한다는 차이가 있음
  • 주요 함수
    • insert(value): 요소 추가
    • erase(value): 요소 제거
    • find(value): 요소 검색 (iterator 반환)
    • size(): 요소 개수 반환
    • lower_bound(value): 지정된 값 이상의 첫 번째 요소를 반환
    • upper_bound(value): 지정된 값보다 큰 첫 번째 요소를 반환
• 중복키가 가능한 것은 이름에 multi가 붙는다.

공통적으로 검색, 삽입, 삭제가 평균 O(log N)이라는 특징이 있는데 이게 가능한 이유는 레드-블랙 트리를 사용하기 때문

레드-블랙 트리에 대한 자세한 내용 :

https://dev0404.tistory.com/55

[자료구조] 레드 블랙 트리

 

컨테이너 어댑터(container adapter)

우선순위 큐 (priority_queue)

• 내부적으로 힙(Heap) 자료구조를 사용
• 삽입, 삭제(pop)은 항상 O(log N) 이고, top()(가장 우선순위 높은 원소 조회)은 O(1)
• 가장 큰/작은 원소를 순식간에 추출해야 하는 문제에 최적
• 세 번째 인자를 통해 최소힙을 만들거나 커스텀으로 정의할 수 있다

 

알고리즘(algorithm)

• count() : 컨테이너 내에서 특정 값이 나타나는 횟수를 센다. O(N)
• sort() : 컨테이너를 정렬하는 함수. O(NlogN)
  • sort(시작 반복자, 끝 반복자, 비교 함수)
• next_permutation(), prev_permutation() : 가능한 모든 순열을 생성한다. O(N*N!)
  • 가능한 순열이 있으면 true를 반환, 더 이상 없으면 false를 반환
  • prev_permutation은 주어진 범위를 사전순으로 이전 순열로 바꿔줌
• unique() : 컨테이너 내 중복되는 원소들을 뒤로 밀어내고 중복되지 않은 원소들만 남겨 새로운 범위의 끝 반복자를 반환. O(N)
• binary_search() : 컨테이너에서 주어진 범위 내 원소에 이진 탐색을 수행. O(logN)
  • 탐색 수행하고 원소가 있으면 true, 없으면 false 반환
• max_element(), min_element() : 컨테이너 내에서 최댓값, 최솟값의 위치를 반환. O(N)
• nth_element() : K번째 값을 찾는 함수. O(n)
• partial_sum() : 연속 구간의 합을 구하는 함수. O(N)
• accumulate() : 총 합을 구하는 함수. O(N)
  • 4번째 인자를 통해 원하는 연산 가능
• lower_bound() / upper_bound() : x 이상의 값이 처음 나오는 위치 반환, x 초과 값이 처음 나오는 위치 반환. O(logN)
• transform() : 입력 범위의 각 요소에 주어진 연산을 적용하여 새로운 값을 생성하는 함수. O(N)

 

 

출처 : 코딩테스트 합격자 되기 책, 내일배움캠프 알고리즘 수업