[코딩 테스트] 프로그래머스 C++ 코테 준비 필수 문법 | STL 컨테이너, STL 알고리즘

이 글은 〈[되기] 코딩 테스트 합격자 되기(C++ 편)〉에서 발췌했습니다.

골든래빗 출판사
박경록 지음

코딩 테스트 문제를 풀기 전에는 당연히 코딩 테스트에. 사용할 언어의 문법을 알아야 합니다. 여기서는 C++ 기초 문법을 충실히 설명하기보다는 코딩 테스트에 자주 사용하는 문법을 설명하는 데 집중합니다. C++ 기초서 1권을 완독했다는 가정하에 설명했으므로 참고하기 바랍니다.

빌트인 데이터 타입과 STL과 자주 사용하는 필수 문법은 아래 글을 참고해주세요.

• [코딩 테스트] 프로그래머스 C++ 코테 준비 필수 문법 | 빌트인 데이터 타입, STL

1. STL의 컨테이너

STL의 컨테이너는 데이터를 저장하는 객체를 말합니다. 여기서 소개할 컨테이너는 벡터, 셋, 맵, 우선순위 큐입니다. 실제 STL은 더 많은 컨테이너를 지원하지만, 코딩 테스트에 꼭 필요한 STL에만 집중하겠습니다. 각 컨테이너를 공부할 때는 단순히 데이터를 저장한다는 특성도 중요하지만, 어떤 방식으로 저장하고 접근하는지를 아는 게 중요합니다. 이러한 특성을 잘 이해해야 문제를 풀 때 입력값을 가장 효율적으로 제어하는 컨테이너를 선택할 수 있습니다. 예를 들어 저장된 데이터에 배열처럼 임의 접근을 해야 한다면 벡터를 선택해야 하고, ‘키-값’ 형태로 저장해야 하면 맵을 선택해야 합니다. 컨테이너를 잘못 선택하면 구현해야 할 코드의 분량이 늘어나고 알고리즘의 효율이 떨어질 수 있습니다.

1.1 벡터

벡터(Vector)는 배열과 매우 유사한 컨테이너입니다. 데이터를 순차적으로 저장하고, 인덱스를 통해서 특정 위치의 원소에 쉽게 접근할 수 있습니다. 문제를 풀 때 배열 대신 벡터를 사용하는 경우가 많습니다. 문제를 설명할 때 벡터를 배열로 표현하도록 하겠습니다.

벡터의 선언 및 초기화

벡터를 사용하려면 #include <vector>로 벡터 헤더를 포함해야 합니다. STL은 템플릿 기반으로 구현되어 있기 때문에 초기화 코드에서 int 대신 char, double, string, 사용자 정의형 모두 쓸 수 있습니다.

#include <vector>

using namespace std;

vector<int> v; // <int>를 <char>, <double> 등으로 바꿔 사용할 수 있음
vector<int> v2 = {1, 2, 3, 4, 5};
vector<int> v3(4, 3);
vector<int> v4(v3);

위 코드에서 v는 빈 벡터이고, v2는 초기화 리스트를 활용해서 초기화와 동시에 원소 다섯 개를 넣은 벡터입니다. v2, v3, v4를 그림으로 나타내면 다음과 같습니다. 그림에서 화살표로 표시한 부분이 v2[3]의 위치입니다.

1차원 배열과 매우 유사하죠. v3는 초기 벡터의 크기를 4로 하고, 모든 원소를 3으로 채운다는 표현입니다. v4는 v3를 복사해서 독립된 새로운 벡터를 만들었습니다. 초기화 이후 v2[3]을 출력하면 4가 출력될 겁니다.

지금까지는 1차원 벡터를 알아봤습니다. 이제 2차원 벡터는 어떻게 선언할 수 있을지 예를 통해 알아보겠습니다.

#include <iostream>
#include <vector>

using namespace std;

// 빈 2차원 벡터 선언
vector<vector<int>> v1;

// 특정 크기로 초기화된 2차원 벡터
int rows = 3;
int cols = 4;
vector<vector<int>> v2(rows, vector<int>(cols));

// 특정 값으로 초기화된 2차원 벡터
int val = 9;
vector<vector<int>> v3(rows, vector<int>(cols, val));

// 초기화 리스트를 사용한 2차원 벡터 초기화
vector<vector<int>> v4 = {
  {1, 2, 3},
  {4, 5, 6},
  {7, 8, 9}
};

위 코드에서 v2, v3, v4를 그림으로 나타내면 다음과 같습니다. v3[1][2]와 v4[0][0] 위치를 확인해보세요.

벡터의 원소 변경

벡터에서 원소를 변경하는 방법은 여러 가지가 있지만, ‘[ ]’ 연산자를 활용하는 방법만 알면 충분합니다. 방법은 배열과 완전히 같고 시간 복잡도는 O(1)입니다. 어렵지 않으므로 코드 예를 바로 보겠습니다.

#include <iostream>
#include <vector>

using namespace std;

int main() {
  vector<int> vec = {1, 2, 3, 4, 5};

  // ① 인덱스 2의 원소를 10으로 수정
  vec[2] = 10;

  return 0;
}

벡터의 삽입과 삭제

초기화하는 방법을 알았으니 원소의 삽입과 삭제를 어떻게 하는지 알아보겠습니다. 벡터의 내부는 배열로 구성되어있습니다. 따라서 맨 뒤에서는 삽입, 삭제 연산을 효율적으로 할 수 있지만, 맨 앞에서 원소를 삽입, 삭제 연산을 할 때는 매우 비효율적입니다. 맨 앞의 원소를 삽입, 삭제하면 뒤의 원소들을 한 칸씩 이동해야 하기 때문이죠. 벡터에 데이터가 N개 있으면 해당 연산은 시간 복잡도가 O(N)이 됩니다. 만약 문제를 풀 때 벡터를 활용해서 구현했는데 맨 앞에 원소를 삽입, 삭제하는 일이 빈번하다면 다른 컨테이너로 접근할 수 있는지 고민해보는 게 좋습니다. 맨 앞 원소를 효율적으로 삽입, 삭제할 수 있는 자료구조는 덱(Deque)이 있으며 시간 복잡도는 O(1)입니다.

벡터로 맨 뒤에 원소를 삽입, 삭제하는 법을 알아보겠습니다. 맨 뒤에 원소를 삽입할 때는 push_back( ) 메서드를 활용하고, 맨 뒤에 있는 원소를 삭제할 때는 pop_back( ) 메서드를 활용합니다. 내부가 배열로 구성되었으므로 맨 뒤의 삽입, 삭제는 저장된 다른 값에 전혀 영향을 미치지 않습니다. 따라서 이 두 메서드의 시간 복잡도는 O(1)입니다.

#include <iostream>
#include <vector>

using namespace std;

int main() {
  vector<int> v = {2, 3, 4, 5};

  //. ① 맨 뒤에 원소 삽입
  v.push_back(6);

  // ② 맨 뒤의 원소 삭제
  v.pop_back();

  return 0;
}

위 코드를 그림으로 나타내면 다음과 같습니다. ① push_back( ) 메서드를 통해 v의 맨 뒤에 원소를 추가하고 ② pop_back( ) 메서드를 통해 맨 뒤의 원소를 삭제하고 있습니다.

맨 앞에 원소를 삽입할 때는 insert( ) 메서드를 활용하면 됩니다. insert( ) 메서드는 첫 번째 인수로 원소를 삽입할 주소를, 두 번째 인수로 삽입할 값을 받습니다. 맨 앞의 원소를 삭제할 때는 erase( ) 메서드를 사용합니다.

코드 예의 첫 v.begin( )은 v의 시작 주소를 나타냅니다. 반복해서 말하지만 벡터의 맨 앞에 원소를 삽입하거나 삭제해야 한다면 다른 컨테이너를 고민하는 걸 추천합니다. 주석으로 코드가 수행된 이후 v의 모습을 나타냈습니다.

#include <iostream>
#include <vector>

using namespace std;

int main() {
  vector<int> v = {2, 3, 4, 5};

  // 맨 앞에 원소 삽입
  v.insert(v.begin(), 1); // v: {1, 2, 3, 4, 5}
  // 맨 앞의 원소 삭제
  v.erase(v.begin()); // v: {2, 3, 4, 5}

  return 0;
}

1.2 셋

셋(Set)은 중복을 허용하지 않고, 저장된 데이터를 자동으로 정렬하는 컨테이너입니다. 집합이라고 표현하기도 합니다.

셋의 선언 및 초기화

셋을 사용하려면 #include <set>으로 셋 헤더를 포함시켜야 합니다.

#include <iostream>
#include <set>

using namespace std;

set<int> s1; // ① 빈 셋 선언
set<int> s2 = {3, 1, 3, 2, 5}; // ② 초기화 리스트를 사용한 셋 초기화
set<int> s3(s2); // 다른 셋을 사용하여 초기화

① s1은 빈 셋을 하나 선언한 것이고, ② s2는 초기화 리스트를 활용해서 특정 값으로 초기화했습니다. ③ s3는 s2를 복사해서 동일한 셋을 하나 선언한 것입니다. s2와 s3를 그림으로 나타내면 다음과 같습니다.

그런데 그림을 보면 s2와 s3가 {3, 1, 3, 2, 5}가 아니라 {1, 2, 3, 5}입니다. 왜 그럴까요? 그 이유는 셋이 중복값을 허용하지 않기 때문입니다. 뿐만 아니라 셋은 원소를 대입할 때 동시에 내부에서 정렬을 수행하여 {1, 2, 3, 5}가 됩니다.

※ 셋을 그림으로 표현할 때 배열처럼 표현했지만 실제로는 균형 이진 트리로 구성되어 있습니다.

여기서 정렬이 되었다는 의미는 배열처럼 작은 원소부터 메모리에 순차적으로 저장된다는 의미가 아니라 트리 구조를 통해 정렬 상태를 유지한다는 의미입니다.

셋에서 원소 탐색

셋에 특정 원소가 있는지 확인하려면 find( ) 메서드를 사용합니다. 만약 찾는 원소가 있으면 원소의 위치를 반환하고 없으면 end 반복자를 반환합니다. 셋의 크기가 N일 때 find( ) 메서드의 시간 복잡도는 O(logN)입니다. 코드 예는 다음과 같습니다.

#include <iostream>
#include <set>

using namespace std;

int main() {
  set<int> numbers = {1, 2, 3, 4, 5};
  int targets[] = {3, 7}; // 원소가 3과 7인 배열
  for (int target : targets) {
    // set에서 원소를 탐색하는 방법
    auto it = numbers.find(target);

    if (it != numbers.end()) {
      cout << "원소 " << target << "를 찾았습니다. 값: " << *it << endl;
    } else {
      cout << "원소 " << target << "를 찾지 못했습니다." << endl;
    }
  }

  return 0;
}
/*
  원소 3를 찾았습니다. 값: 3
  원소 7를 찾지 못했습니다.
*/

코드에서 find( ) 메서드가 호출되면 셋에 3이 있으므로 해당 위치를 반환하고, 7은 없으므로 end 반복자를 반환합니다.

셋의 삽입과 삭제

이제 셋에서 원소의 삽입과 삭제를 어떻게 하는지 알아보겠습니다. 벡터는 원소의 위치에 따라 삽입, 삭제의 시간 복잡도의 차이가 많이 났습니다. 하지만 셋은 모든 삽입, 삭제의 시간 복잡도가 O(logN)입니다. 삽입, 삭제 후에도 정렬된 상태를 유지하기 때문입니다. 구현할 때 삽입은 insert( ), 삭제는 erase( ) 메서드를 활용합니다. 이때 erase( ) 메서드에는 삭제할 원소의 값이 올 수도 있고, 삭제할 원소의 주소가 올 수도 있습니다.

다음 코드 예에서 erase( )에 주소를 인수로 받는 경우를 설명하기 위해 find( ) 메서드를 사용했습니다. find( ) 메서드는 특정 원소가 있으면 원소의 주소를 반환하고, 없으면 end 반복자를 반환합니다. end 반복자는 해당 컨테이너의 마지막 원소의 다음 주소이며, 셋 뿐만 아니라 대부분 STL에서 제공하는 탐색 관련 함수 혹은 메서드를 찾지 못했을 때 end 반복자를 반환합니다. 삽입과 삭제 코드 예는 다음과 같습니다.

#include <iostream>
#include <set>

using namespace std;

int main() {
  set<int> s = {1, 3, 2, 1, 5};

  // ① 원소 4 삽입
  s.insert(4);

  // ② 원소 2 삭제
  s.erase(2);

  // ③ 원소 4가 있는지 확인 후 삭제
  auto it = s.find(4);
  if (it != s.end()) {
    s.erase(it);
  }

  return 0;
}

코드를 그림으로 나타내면 다음과 같습니다. ① insert( ) 메서드로 s에 원소를 추가하고 ② erase() 메서드로 특정 원소를 삭제하고 있습니다.

셋은 삽입, 삭제할 때도 데이터의 정렬 상태를 유지하며, erase( ) 메서드를 활용해서 특정 값 혹은 특정 값의 위치 기준으로 삭제합니다. 주의해야 할 점은 erase( ) 메서드에 원소의 주소를 인수로 넘길 때 s의 원소 주소에 해당되지 않는 주소를 넘기면 프로그램이 정상적으로 동작하지 않습니다. ③ find( ) 메서드를 활용해서 특정 값이 있는지 확인할 때 end 반복자가 아닐 때만 erase( ) 메서드를 수행합니다. 그 이유는 end 반복자는 s가 가지고 있는 원소의 주소가 아니기 때문입니다. 만약 end 반복자 위치를 삭제하라고 하면 예외가 발생할 겁니다.

1.3 맵

맵(Map)은 키와 값을 쌍으로 갖는 컨테이너입니다. 여기서 키와 값의 쌍을 entry라고 하며 STL에서는 std::pair 타입으로 표현합니다. 내부는 균형 이진 탐색 트리로 구성되어 있기 때문에 항상 키값을 기준으로 데이터가 자동 정렬됩니다. N개의 키가 있다면 키를 기준으로 검색, 삽입, 삭제를 하는데 시간 복잡도는 O(logN)입니다. 추가로 맵의 키값은 중복되지 않고 유일하다는 특징이 있습니다. 일반적인 배열은 인덱스를 통해 원하는 값을 찾습니다. 하지만 맵은 배열과 같이 정수형 인덱스로 한정되지 않고, 키 자체를 통해 원하는 값을 찾을 수 있습니다. 예를 들어서 키가 문자열로 된 이름이고, 값이 연락처면 문자열로 된 이름을 통해 연락처를 바로 찾을 수 있습니다.

※ 시간 복잡도는 엄밀하게 말해서 각 키의 비교 연산도 고려해야 하지만 상수로 가정했습니다.

맵의 선언 및 초기화

맵을 사용하려면 #include <map>을 통해 맵 헤더를 포함시켜야 합니다.

#include <map>
#include <string>
using namespace std;

//빈 맵 선언
map<string, double> employeeSalaries;

map<string, double> studentGrades = {
  {"John", 3.7},
  {"Emma", 3.9},
  {"Sophia", 4.0}
};

studentGrades를 그림으로 나타내면 다음과 같습니다.

실제 맵은 이진 탐색 트리로 구성되어 있기 때문에 그림에서 보는 것처럼 선형적이지 않습니다. 이해를 돕기 위한 그림이라고 생각해주세요. 키-값 형태로 저장되고, 키값을 기준으로 자동 정렬 된다는 부분을 중점적으로 보면 됩니다.

맵에서 특정 키에 접근

맵에서 특정 키에 접근하는 방법은 2가지입니다.

• [ ] 연산자 활용하기 // studentScores[“Alice”]
• find( ) 메서드 활용하기 // studentScores.find(“Charlie”);

[ ] 연산자는 표현상으로 배열과 비슷할 뿐더러 가독성도 좋으므로 많이 활용합니다. 다만 주의할 점은 배열과 다르게 [ ] 연산자를 통해 접근하려는 키가 맵에 없으면 맵에 현재 키를 추가한다는 것입니다. 다시 말해 맵에 없는 키에 접근하려고 하면 오류가 발생하는 것이 아니라 새로운 키가 만들어집니다. [ ] 연산자의 시간 복잡도는 O(logN)입니다.

만약 특정 키를 검색할 때 키가 없고, 맵에 새로운 키를 추가하는 것이 아니라 키가 없는 상태를 유지해야 하면 find( ) 메서드를 사용합니다. find( ) 메서드는 키가 맵에 있으면 해당 키의 위치를 반환하고, 없으면 end 반복자를 반환합니다. find( ) 메서드의 시간 복잡도는 O(logN)입니다. 각 원소는 pair 객체이므로 멤버 변수로 first와 second를 갖습니다. first는 맵의 키 정보를 담고 있고 second는 맵의 값 정보를 담고 있습니다.

#include <iostream>
#include <map>

using namespace std;

int main() {
  // 맵 생성
  map<string, int> studentScores;

  // 키-값 쌍 추가
  studentScores["Alice"] = 95;
  studentScores["Bob"] = 88;
  studentScores["Charlie"] = 92;

  // [] 연산자를 사용하여 키에 접근 - 키가 있는 경우
  int score1 = studentScores["Alice"];
  cout << score1 << endl; // ➊ 출력값 : 95

  // [] 연산자를 사용하여 키에 접근 - 키가 없는 경우
  int score2 = studentScores["rabbit"]; // ➋
  cout << score2 << endl; // 출력값 : 0

  // find() 메서드를 사용하여 키에 접근
  auto it = studentScores.find("Charlie"); // ➌
  if (it != studentScores.end()) {
    int score3 = it->second;
    cout << score3 << endl; // 출력값 : 92
  }

  return 0;
}

코드 예를 그림으로 나타내면 다음과 같습니다.

① ‘[ ]’ 연산자를 활용해서 “Alice”라는 키에 해당하는 값을 출력합니다. ② 다음으로 ‘[ ]’ 연산자를 활용하여 맵에 없는 “rabbit”이란 키에 접근합니다. 현재 맵에 없지만 ‘[ ]’ 연산자로 접근했기 때문에 “rabbit” 키가 새로 생성되었고 해당하는 값이 출력됩니다. ③ 마지막으로 find( ) 메서드를 활용해서 “Charlie”라는 키가 맵에 있는지 확인 후 값을 출력합니다.

맵의 값 변경

맵의 값을 변경할 때는 벡터와 마찬가지로 ‘[ ]’ 연산자를 활용합니다. 인덱스가 숫자가 아닐 수도 있다는 것만 기억하면 됩니다. 바로 코드 예를 보겠습니다.

#include <iostream>
#include <map>

using namespace std;

int main() {
  map<string, int> myMap = {{"Apple", 1}, {"Banana", 2}, {"Cherry", 3}};
  
  // "Banana" 키에 해당하는 값을 10으로 수정
  myMap["Banana"] = 10;

  return 0;
}

위 코드를 그림으로 나타내면 다음과 같습니다.

맵의 삽입과 삭제

맵에 원소를 삽입하는 방법은 2가지입니다. 첫 번째는 insert( ) 메서드를 활용하는 것이고, 두 번째는 [ ] 연산자를 활용하는 것입니다. 두 방법 모두 많이 사용합니다. insert( ) 메서드는 인수로 pair 객체를 받는데, 이때 make_pair( ) 함수를 쓰거나 { }를 사용합니다. 삽입 연산의 시간 복잡도는 O(logN) 입니다.

삭제할 때는 erase( ) 메서드를 사용합니다. 인수로 키값 혹은 키의 위치를 넣으면 해당 키 혹은 위치의 원소가 삭제됩니다. 인수로 값을 넘길 때 시간 복잡도는 O(logN), 위치를 넘길 때 시간 복잡도는 O(1)이 됩니다.

#include <iostream>
#include <map>

using namespace std;

int main() {
  map<int, string> myMap;

  // ① 삽입
  myMap.insert(make_pair(1, "Apple"));
  myMap.insert({2, "Banana"});
  myMap[3] = "Cherry";

  for (const auto &pair : myMap) {
    cout << pair.first << ": " << pair.second << endl;
  }
  /*
    1: Apple
    2: Banana
    3: Cherry
  */

  // ② 삭제
  myMap.erase(2);

  for (const auto &pair : myMap) {
    cout << pair.first << ": " << pair.second << endl;
  }
  /*
    1: Apple
    3: Cherry
  */

  auto it = myMap.find(3);
  if (it != myMap.end()) {
    myMap.erase(it);
  }
  
  // 삭제 후 맵 출력
  for (const auto &pair : myMap) {
    cout << pair.first << ": " << pair.second << endl;
  }
  // 1: Apple

  return 0;
}

① 그림을 통해 삽입하는 부분의 코드 동작을 확인해보겠습니다. 앞에서 설명한 다양한 방법으로 원소를 삽입할 수 있습니다.

② 이어서 맵에서 원소를 삭제하는 동작을 그림으로 보겠습니다. erase( ) 메서드에 인수로 2라는 키를 전달해서 삭제하고, 이어서 find( ) 메서드를 활용해서 키 3의 위치를 확인한 후 해당 위치의 원소를 삭제했습니다.

1.4 정렬되지 않은 셋과 맵

기본적으로 C++ STL의 셋과 맵은 내부 구조가 이진 탐색 트리이기 때문에 정렬 상태를 유지합니다. 하지만 자동으로 정렬되는 것이 무조건 좋은 것만은 아닙니다. 문제를 풀 때 굳이 필요 없는데도 정렬을 하면 성능 저하를 가져옵니다.

C++에서는 이때 사용할 수 있는 정렬되지 않은 셋(unordered_set)과 정렬되지 않은 맵(unordered_map)을 제공합니다. 이 둘은 기본적으로 앞에서 배운 셋, 맵과 같은 방법으로 사용할 수 있습니다. 다만 내부 구조가 이진 탐색 트리가 아닌 해시 기반이기 때문에 데이터를 자동으로 정렬하지 않습니다. 따라서 삽입, 삭제, 탐색의 시간 복잡도가 O(1)입니다. 최악의 경우에는 O(N)이지만 이런 경우는 거의 발생하지 않으므로 넘어가겠습니다. 기존에 제공했던 셋과 맵이 O(logN)이었던 것에 비해 빠르다고 할 수 있죠.

정렬되지 않은 셋을 사용하려면 #include<unordered_set>을 추가하면 되고, 정렬되지 않은 맵을 사용하려면 #include<unordered_map>을 추가하면 됩니다. 앞에서 셋과 맵의 사용 방법을 충분히 학습했습니다. 정렬되지 않은 셋과 맵의 사용 방법은 셋과 맵의 사용 방법과 동일하므로 간단한 코드 예 하나만 보고 넘어가겠습니다.

먼저 정렬되지 않은 셋의 코드 예입니다. 원소가 자동으로 정렬되지 않은 것을 확인해보세요.

#include <iostream>
#include <unordered_set>

using namespace std;

int main() {
  unordered_set<int> myUnorderedSet;

  // 삽입
  myUnorderedSet.insert(3);
  myUnorderedSet.insert(1);
  myUnorderedSet.insert(4);
  myUnorderedSet.insert(2);

  for (int num : myUnorderedSet) {
    cout << num << " ";
  }
  cout << endl;

  //출력값 : 2 4 1 3
  return 0;
}

다음은 정렬되지 않은 맵의 코드 예입니다. 키가 정렬되지 않은 것을 확인해보세요.

#include <iostream>
#include <unordered_map>

using namespace std;

int main() {
  unordered_map<string, int> myUnorderedMap;

  // 삽입
  myUnorderedMap["apple"] = 3;
  myUnorderedMap["banana"] = 1;
  myUnorderedMap["cherry"] = 4;
  myUnorderedMap["date"] = 2;

  // unordered_map의 요소 출력
  for (const auto& pair : myUnorderedMap) {
    cout << pair.first << ": " << pair.second << endl;
  }

  /*
    출력값
    date: 2
    cherry: 4
    banana: 1
    apple: 3
  */

  return 0;
}

2. STL의 알고리즘

count( ) 함수는 컨테이너 내에서 특정 값이 나타나는 횟수를 셉니다. 인수는 3개를 받는데 시작 반복자, 끝 반복자, 그리고 나타나는 횟수를 확인할 값입니다. 이 함수는 시작 반복자부터 끝 반복자까지 범위에서 3번째 인수로 받은 값과 일치하는 원소의 개수를 반환합니다. 시간 복잡도는 범위로 지정한 원소의 개수가 N개일 때 O(N)입니다. 코드 예는 다음과 같습니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
  vector<int> v = {1, 4, 3, 4, 5, 4, 5};

  // 5라는 값이 벡터 v에 몇 번 나타나는지 세기
  int ret = count(v.begin(), v.end(), 5);

  cout << ret << endl; // 2
  
  return 0;
}

벡터의 맨 처음 원소부터 끝 원소까지 하나씩 확인하면서 원소 5의 개수를 세고 반환합니다.

2.1 sort( ) 함수로 정렬하기

sort( ) 함수는 컨테이너를 정렬하는 함수입니다. sort( ) 메서드는 다음과 같이 오버로딩되어 있습니다.

• sort(시작 반복자, 끝 반복자) // ①
• sort(시작 반복자, 끝 반복자, 비교 함수) // ②

① 인수를 2개 받을 때는 시작 반복자와 끝 반복자를 받아 범위 내 원소들을 오름차순으로 정렬합니다. ② 인수를 3개 받을 때는 시작 반복자, 끝 반복자에 추가로 비교 함수를 받습니다. 비교 함수를 기준으로 범위 내 원소를 정렬하는 것이죠. 사용자가 정의한 타입의 원소를 정렬하려면 sort( ) 함수를 활용해야 합니다. sort( ) 함수의 시간 복잡도는 O(NlogN)입니다.

먼저 인수가 2개인 버전의 코드 예를 보겠습니다. ① 첫 번째 sort( ) 함수에서는 순방향 반복자를 활용해서 벡터의 원소들을 오름차순으로 정렬했습니다. 만약 내림차순으로 정렬하고 싶다면 ② 두 번째 sort( ) 함수처럼 역방향 반복자를 사용하면 됩니다.

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {
  std::vector<int> v = {4, 2, 5, 3, 1};

  // ① 벡터 v를 오름차순으로 정렬
  sort(v.begin(), v.end());
  // v의 상태 : 1 2 3 4 5

  // ② 벡터 v를 내림차순으로 정렬
  sort(v.rbegin(), v.rend());
  // v의 상태 : 5 4 3 2 1

  return 0;
}

이번에는 sort( ) 함수에서 인수를 3개 사용하는 코드 예를 보겠습니다.

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

struct Point {
  int x, y;

  Point(int x, int y) : x(x), y(y) {}
};

// 사용자 정의 비교 함수
bool compare(const Point &a, const Point &b) {
  if (a.x == b.x) {
    return a.y < b.y; // ① x 좌표가 같으면 y 좌표가 작은 순서대로 정렬
  }
  return a.x < b.x; // ② x 좌표가 작은 순서대로 정렬
}

int main() {
  vector<Point> points = {{3, 4}, {1, 2}, {3, 1}, {2, 5}};

  // points 벡터를 사용자 정의 기준으로 정렬
  sort(points.begin(), points.end(), compare);

  // 정렬된 벡터 출력
  for (const Point &p : points) {
    cout << "(" << p.x << ", " << p.y << ") ";
  }
  cout << endl;
  // 출력값 : (1, 2), (2, 5), (3, 1), (3, 4)

  return 0;
}

코드를 보면 3번째 인수로 비교 함수 compare( )가 들어갔습니다. sort( ) 함수에서 사용자 정의 비교 함수는 반환값이 false일 때 원소의 위치를 바꿉니다. compare( ) 함수를 보면 ① a.x와 b.x가 같으면 a.y가 b.y보다 작을 때 true입니다. ② 그리고 a.x와 b.x가 다르면 a.x가 b.x보다 작을 때 true입니다. Point 구조체 변수에서 x값이 같을 때 y값이 작은 Point 구조체 변수가 앞에 오는 것입니다. 그리고 x값이 다르면 x값이 작은 Point 구조체 변수가 앞에 옵니다. 정리하면 x값이 작은 구조체 변수가 앞에 오고 x값이 같으면 y값이 작은 구조체 변수가 앞에 오도록 정렬하는 비교 함수입니다. 출력값을 보면 비교 함수에서 정의한 대로 정렬이 되었습니다.

2.2 next_permutation( ) 함수로 순열 생성하기

next_permutation( ) 함수는 가능한 모든 순열을 생성합니다. 인수는 시작 반복자와 끝 반복자 2개를 받습니다. 순열은 사전 순으로 생성하며 실제 범위 내 원소들의 위치가 변경됩니다. 가능한 순열이 있으면 true를 반환하며, 더 이상 가능한 순열이 없으면 false를 반환합니다.

가능한 모든 순열을 생성할 때 이 함수를 주로 사용하므로 코드 예처럼 while 내에서 함수를 호출하는 패턴이 많습니다. 데이터가 N개라면 각 순열을 생성할 때 최대 번 만큼 원소의 위치를 맞바꿀 수 있고, 순열은 최대 N/2개 있으므로 모든 순열을 생성할 때 연산 횟수를 기준으로 시간 복잡도는 O(N*N!)입니다.

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {
  vector<int> v = {1, 2, 3};
  // 모든 가능한 순열 출력
  do {
    for (int i : v) {
      cout << i << " ";
    }
    cout << endl;
  } while (next_permutation(v.begin(), v.end()));
  return 0;
}
/*
출력값:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
*/

next_permutation( )에서 가능한 모든 순열을 생성하려면 데이터가 사전순으로 정렬된 상태여야 합니다. 만약 데이터가 사전순으로 정렬된 상태가 아니라면 정렬을 한 후에 next_permutation( )을 호출해야 합니다.

※ 데이터를 사전순으로 정렬하지 않은 코드로 수정하여 직접 실행해 결과를 확인해보기 바랍니다.

2.3 unique( ) 함수로 중복 정리하기

unique( ) 함수는 컨테이너 내 중복되는 원소들을 뒤로 밀어내고 중복되지 않은 원소들만 남겨 새로운 범위의 끝 반복자를 반환합니다. 인수는 시작 반복자와 끝 반복자 2개를 받습니다. 시간 복잡도는 데이터의 개수가 N개일 때 O(N)입니다. 코드 예는 다음과 같습니다.

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {
vector<int> v = {1, 2, 2, 3, 3, 3, 4, 4, 5, 5, 5};

// ① unique 함수를 사용하여 중복 요소 제거
auto newEnd = unique(v.begin(), v.end());

// 중복되지 않는 요소들만 출력
for (auto it = v.begin(); it != newEnd; ++it) {
  cout << *it << " ";
}
cout << endl;
// 1 2 3 4 5

// 벡터의 크기 출력
cout << v.size() << endl; // 11

// 전체 원소 출력
for (auto it = v.begin(); it != v.end(); ++it) {
  cout << *it << " ";
}
cout << endl;
// 1 2 3 4 5 3 4 4 5 5 5

  return 0;
}

코드의 동작을 그림으로 표현하면 다음과 같습니다. ① unique( ) 함수를 수행하면 범위 내 원소중 중복되는 원소는 뒤로 이동시킵니다. 그리고 newEnd 즉 unique( )가 반환하는 위치는 중복되지 않는 원소 범위의 마지막 원소 바로 다음입니다.

※ 원래 끝 반복자는 마지막 위치 바로 다음이었다는 것을 기억하세요.

2.4 binary_search( ) 함수로 이진 탐색하기

search( ) 함수는 컨테이너에서 주어진 범위 내 원소에 이진 탐색을 수행합니다. 인수는 시작 반복자, 끝 반복자, 찾을 값으로 3개를 받습니다. 탐색을 수행하고 원소가 있으면 true 없으면 false를 반환합니다. 시간 복잡도는 데이터의 개수가 N이면 O(logN)입니다.

이진 탐색의 특성상 원소가 이미 정렬되어 있어야 정상 동작합니다. 데이터가 이미 정렬되어 있고, 원소를 자주 탐색해야 한다면 이진 탐색이 배열을 순차 탐색하는 것보다 유용합니다.

※ 이 설명을 보고 ‘이진 탐색이 무조건 좋다’라고 오해하지 않기를 바랍니다. 이진 탐색은 정렬된 상태를 가정한 알고리즘이므로 정렬되지 않은 상태에서 이진 탐색을 하려면 정렬 후 이진 탐색을 진행해야 하므로 선형 탐색보다 더 많은 시간 복잡도를 필요로 합니다.

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {
  vector<int> v = {1, 2, 3, 4, 5};

  cout << binary_search(v.begin(), v.end(), 3) << endl; // ① 1
  cout << binary_search(v.begin(), v.end(), 7) << endl; // ② 0

  return 0;
}

코드를 보면 ① 3은 컨테이너에 있는 값이므로 1을 반환하고, ② 7은 컨테이너에 없는 값이므로 0을 반환했습니다.

2.5 max_element( ), min_element( ) 함수로 최댓값, 최솟값 위치 구하기

max_element( ) 함수와 min_element( ) 함수는 컨테이너 내에서 최댓값, 최솟값의 위치를 반환합니다. 두 함수는 시작 반복자와 끝 반복자로 2개의 인수를 받습니다. 시간 복잡도는 데이터의 개수가 N개일 때 O(N)입니다. 코드 예를 보면 직관적으로 이해할 수 있을 것입니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
  vector<int> v = {1, 3, 5, 7, 2, 4, 6};

  auto maxIt = max_element(v.begin(), v.end());
  auto minIt = min_element(v.begin(), v.end());

  cout << *maxIt << endl; // 7
  cout << *minIt << endl; // 1

  return 0;
}

3. 함수

함수는 프로그램의 중요한 요소입니다. 이건 프로그래밍 기초를 공부했다면 누구나 아는 사실이죠. 주요 내용과 코딩 테스트를 위해 알아야 할 내용만 빠르게 공부하고 넘어가겠습니다.

3.1 함수 정의

C++의 함수는 ‘반환 타입 함수명 (인수1, 인수2 …)’와 같은 방식으로 정의합니다. 만약 반환하는 값이 없다면 반환 타입에 void를 사용하면 됩니다.

// 정수형을 반환하는 func1 함수
int func1(param1, param2..., paramN) {
  // 함수의 실행 코드
  // …
  // …
  return result; // 반환값
}

3.2 함수 호출

함수를 정의했으면 함수를 호출할 수 있습니다. 함수를 호출할 때 매개변수가 있으면 func(a, b)와 같이 인수를 함께 전달합니다.

#include <iostream>

using namespace std;

// 두 수를 더하는 함수
int add(int num1, int num2) {
  return num1 + num2;
}

int main() {
  int a = 5;
  int b = 10;

  // add 함수를 호출하여 결과 출력
  cout << add(a, b) << endl; // 15
  return 0;
}

4. 코딩 테스트 코드 구현 노하우

코딩 테스트를 공부하면 만나는 첫 난관은 코드 구현입니다. 자료구조나 알고리즘은 이론 지식이므로 공부하면 지식이 쌓이면서 실력이 늡니다. 하지만 코드 작성 노하우는 쉽게 늘지 않습니다. 여기서는 코딩 테스트에 유용한 코드 작성 노하우를 몇 가지 소개하겠습니다. 이런 노하우는 하루만에 습득하기 어렵습니다. 습관이 되어야 하므로 코드를 작성할 때마다 적용해보기 바랍니다.

4.1 조기 반환

조기 반환(Early Return)은 코드 실행 과정이 함수 끝까지 도달하기 전에 반환하는 기법입니다. 이 방식은 코드의 가독성을 높여줄 뿐만 아니라 예외를 조금 더 깔끔하고 빠르게 처리할 수 있습니다.

#include <iostream>

using namespace std;

// 주어진 수량과 가격에 따라 총 가격을 계산하는 함수
double total_price(int quantity, double price) {
  double total = quantity * price; // ➊ total 계산
  if (total > 100) { // ➋ total이 100보다 크면
    return total * 0.9; // ➌ 조기 반환
  }

  return total;
}
...생략...(수많은 작업들)
int main() {
  cout << total_price(4, 50) << endl;
  return 0;
}

① total에 quantity * price를 대입합니다. ② total의 값이 100보다 큰 경우 ③ total에 0.9를 곱하고 반환합니다. 이렇게 하면 함수 자체를 조기에 종료할 수 있으므로 이후 예외에 대한 처리를 하지 않아도 됩니다.

4.2 보호 구문

보호 구문(Guard Clauses)은 본격적인 로직을 진행하기 전 예외 처리 코드를 추가하는 기법입니다. 예를 들어 조건문을 이용하여 초기에 입력값이 유효한지 검사하고 그렇지 않으면 바로 함수를 종료하는 보호 구문을 쓸 수 있습니다.

#include <iostream>
#include <vector>

using namespace std

// ① 벡터의 값을 모두 더해서 N으로 나눈 값을 반환하는 함수
double get_avg(const vector<int>& arr, int N) {
  // ② 벡터가 비어 있는 경우
  if (arr.empty()) {
    return -1;
}

// ③ N이 0인 경우
if (N == 0) {
  return -1;
}
  int sum = 0;
  for (int num : arr) {
    sum += num;
  }

  return sum / N;
}

이렇게 구현한 코드는 보호 구문 이후 구현부에서 입력값에 대한 예외를 고려하지 않아도 되므로 보기 좋습니다. 추가로 이런 습관을 들이면 처음부터 예외를 고려할 수 있어 코드를 더 안전하게 작성할 수 있습니다. 코드를 보면 ① 실제 벡터의 값을 모두 더해서 N으로 나누기 전에 ② 벡터가 비었거나 ③ N이 0인 경우를 먼저 예외 처리합니다. 그러면 이후 코드에서는 원하는 동작 구현에만 집중할 수 있겠죠?

저자 박경록

매일 퇴근과 점심 메뉴를 고민하는 9년차 시스템 S/W 개발자입니다. 수학, 알고리즘 같은 실생활과 가깝고도 먼 학문을 좋아하고, 명확하지만 개선 여지가 있는 문제들에 대해 논의하고 사고를 개선해 나가는 과정을 좋아합니다.