Coding Test

STL 기본 구조

iiblueblue 2025. 2. 5. 17:12
⊙ STL이 무엇인지 알아보고 그 쓰임을 이해한다.
더보기

코드스니펫

 

STL(Standard Templete Library)

STL이란 표준 템플릿 라이브러리(Standard Template Library)의 약자로 이름 그대로 C++에 내장된 템플릿 기반의 라이브러리이다.

이전에 벡터를 배열로 직접 구현해보았을 때 느낄 수 있었다. 나 말고 다른 똑똑한 사람이 구현해 놓은 것을 쓸 수 있다는 것이 얼마나 행복한 일인지 말이다. 그 똑똑한 사람이 미리 만들어서 제공하고 있는 것이 STL이다. 결국 내가 직접 만든 벡터를 include 하여 사용한 것처럼 C++에서 이미 예쁘게 만들어 놓은 것을 include해서 쓸 수 있는 것이다.

STL의 구성 요소

STL은 크게 컨테이너(Container), 반복자(Iterator), 알고리즘(Algorithm)으로 구성되어 있다.

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

결론적으로 모두 그냥 있는 것들이 아니다. 코딩을 하다보면 "아 이런 기능은 있었으면 좋겠다.", "이런 모양의 컨테이너도 있었으면 좋겠다." 생각한 것들의 종합이라고 할 수 있다. 이 셋은 유기적으로 연동되어 우리가 하는 코딩에 막강한 지원을 해준다.

 


 

컨테이너(Container)

컨테이너는 데이터를 저장/관리하는 구조체(자료구조)들의 집합이다. 즉 데이터를 안전하고 편리하게 담아두는 창고같은 것이다.

이런 설명보다 일단 컨테이너인지 보면 구면인 것들이 있을 것이다. 컨테이너는 아래와 같은 것들이 있다.

  • vector
  • list
  • deque
  • queue
  • map
  • set
  • unordered_map
  • unordered_set
  • priority_queue

각각의 컨테이너는 뚜렷한 특징들이 있다. 따라서 내가 어떤 상황에서 데이터를 사용해야하는지에 따라 어떤 컨테이너를 사용할지 달라질 것이다. 예를 들어 학번으로 학생을 찾는 행동을 자주 한다면 학번을 key로 가지고 있는 map을 사용하는 것이 적절할 것이고, 순서대로 줄을 세워놓고 n번째 사람을 찾아 조회하는 행동을 자주 한다면 vector를 사용하는 것이 좋을 것이다.

 

왜 컨테이너를 골라 사용해야 하는가?

사실 레벨1 코딩 테스트를 풀다 보면 결국 vector만 알면 모든 문제를 해결할 수 있는 것이 아닌가 하는 의문이 들기도 한다. 많은 문제들이 다른 컨테이너를 사용하지 않고 vector 만으로 정리되는 경우가 많기 때문이다.

 

하지만 이 문제를 보고 생각이 달라졌다.

https://iiblueblue.tistory.com/211

 

[2025.02.11] 달리기 경주

문제 설명안에서 매년 달리기 경주가 열립니다. 해설진들은 선수들이 자기 바로 앞의 선수를 추월했을 때 추월한 선수의 이름을 부릅니다. 예를 들어 1등부터 3등까지 "mumu", "soe", "poe" 선수들이

iiblueblue.tistory.com

이전에 풀어본 문제인데 오직 vector만 사용하여도 일부 정답은 맞힐 수 있는 문제이다. 하지만 vector만 사용하면 일부 테스트 케이스에서 시간초과가 발생하여 절대 전체 정답을 맞힐 수 없는 문제이다. 이 문제에서는 검색 속도의 차이 때문에 vector와 함께 map을 사용해주어야만 정답을 맞힐 수 있다.

 

결론적으로 코딩 테스트에선 상황마다 알맞은 컨테이너를 사용해야 풀이가 가능한 문제들이 있다. 그렇기 때문에 vector 하나를 무기로 하여 문제를 푸는 것은 위험하다.

 


 

반복자(Iterator)

세 가지의 요소 중 내게 가장 낯설었던 개념이 반복자라는 개념이었다.

 

반복자는 컨테이너 내 데이터를 순회(Navigation)할 수 있도록 도와주는 일종의 '포인터' 역할이다. 즉, 컨테이너의 어디를 가리키고 있는지를 알려주는 것이다.

 

또한 여직 auto를 사용해서 잘 느끼지 못하였지만 컨테이너 마다 반복자 타입이 다르다. 

 

사용 방법

  • begin() : 시작 위치의 요소를 가리키는 반복자 반환
  • end() : 마지막 요소 바로 뒤의 요소를 가리키는 반복자 반환
  • *it : 이터레이터 앞에 *를 붙이면 원소 참조 가능(마치 포인터 처럼)
  • ++, -- : 반복자에서 위치를 하나 뒤, 하나 앞으로 이동 가능
  • begin()+i : 인덱스 i인 요소를 가리키는 반복자

 

반복자의 종류

역방향 반복자(reverse_iterator)

rbegin(), rend()

: 컨테이너를 역순으로 순회할 때 사용한다.

for (std::vector<int>::reverse_iterator rit = vec.rbegin(); rit != vec.rend(); ++rit) 
{
    std::cout << *rit << " ";
}

 

상수 반복자(const_iterator)

cbegin(), cend()

: 컨테이너의 데이터를 수정할 수 없는 반복자이다. 읽기 목적으로만 사용한다면 명시적으로 값이 바뀌지 않음을 적어주는 것이 좋다.

for (std::vector<int>::const_iterator it = vec.cbegin(); it != vec.cend(); ++it) 
{
    std::cout << *it << " ";
}

 

삽입 반복자

: 컨테이너에 새로운 원소를 삽입할 때 사용한다.

std::vector<int> vec = {1, 2, 3};
std::vector<int> vec2 = {4, 5, 6};
// vec 뒤에 vec2를 삽입 => vec {1,2,3,4,5,6}
std::copy(vec2.begin(), vec2.end(), std::back_inserter(vec));

 

auto 키워드

std::vector<int>::iterator와 같은 긴 타입명은 복잡하게 느껴지고 그래서 일단 거부감이 느껴진다. 하지만 auto를 사용하면 긴 타입명을 짧게 줄이면서 좀 더 깔끔하게 코드를 짤 수 있다.

// 일부 배열 순회 시(일반 for문)
for (auto it = vec.cbegin(); it != vec.cend(); ++it) 
{
    std::cout << *it << " ";
}

// 처음 부터 끝까지 순회 시(범위 기반 for문)
for (int val : vec) 
{
    std::cout << val << std::endl;
}

 


 

알고리즘(Algorithm)

알고리즘이란 정렬, 탐색, 삽입, 삭제 등과 같은 로직을 매우 효율적이고 제네릭하게 제공하는 것이다. 

 

알고리즘 문제를 풀면서 #include <algorithm> 하나만 입력하면 내가 하나하나 구현하면 힘들지만 누가 제공해주면 좋겠다 싶은 기능들을 아주 많이 사용할 수 있다. 컨테이너를 정렬한다거나, 요소를 찾는다거나, 모든 값을 더하거나 하는 등 많은 기능을 제공하고 있다.

 

알고리즘의 종류

아래 처럼 많은 종류의 알고리즘을 제공하고 있다.

정렬 관련 sort, partial_sort, stable_sort, nth_element ...
탐색 관련 find, binary_search, lower_bound, upper_bound ...
수치 관련 accumulate, inner_product, adjacent difference ...
수정 관련 fill, replace, remove_if, unique ...

* 함수 이름을 누르면 상세 설명으로 이동

 

결론적으로 복잡한 기능을 내가 직접 구현할 필요 없이 가져다 쓰기만 하면 되니 알고리즘을 활용하면 코딩 테스트 문제 해결 속도가 매우 빨라진다. 또한 내가 만든 것이 아니라 제공하고 있는 것이기 때문에 이미 최적화 되어 있어 믿고 사용할 수 있다. 

 

 


 

배운 내용 정리

  • 내용

'Coding Test' 카테고리의 다른 글

11강 과제 : 블루트포스 최적화  (0) 2025.03.11
블루트포스  (0) 2025.03.11
2강 과제 : 온라인 학습 관리 시스템 구현  (0) 2025.02.07