[42SEOUL] CPP Module 09

Chapter 1

Introduction

C++은 Bjarne Stroustrup이 C 프로그래밍 언어의 확장 또는 "클래스를 얹은 C"로 만든 범용 프로그래밍 언어이다. (출처: Wikipedia

C++ - Wikipedia

이 모듈의 목적은 객체 지향 프로그래밍에 대해 너에게 소개하기 위함이다. 이것은 너의 C++ 여정에 있어 시작점이 될 것이다. 많은 언어들은 OOP를 배우기를 추천한다. 우리는 우리의 오래된 친구인 C의 파생인 C++을 선택하기로 결정했다. 이것이 복잡한 언어이기 때문에, 단순함을 유지하기 위해서, 너의 코드는 C++ 98 표준으로 컴파일이 될 것이다.

우리는 최신의 C가 많은 측면에서 다르다는 것을 알고 있다. 따라서, 유능한 C++ 개발자가 되려면 42 공통 과정 이후에도 더 나아가야 한다.

Chapter 2

General rules

Compiling

• 너의 코드는 C++과 -Wall -Wextra -Werror로 컴파일 되어야 한다.
• 너의 코드는 -std=c++98 플래그를 추가해도 여전히 컴파일되어야 한다.

포맷팅 및 네임 컨벤션

• 예제 디렉토리들은 다음과 같은 형식으로 작명된다: ex00, ex01, ... , exn
• 너의 파일, 클래스, 함수, 멤버 함수들은 가이드라인에서 요구하는 대로 이름을 지어야 한다.
• 클래스의 이름은 UpperCamelCase 형식으로 작성해라. 클래스를 포함한 파일들은 항상 클래스 이름을 따라 이름지어야 한다. 예를들어, ClassName.hpp/ClassName.h, ClassName.cpp or ClassName.tpp. 그렇다면, 만약 너가 벽돌 벽을 나타내는 "BrickWall" 클래스를 정의한 헤더 파일을 가지고 있다면, 그 이름은 BrickWall.hpp가 될 것이다.
• 달리 지정하지 않는 한 모든 출력 메시지는 개행 문자로 끝나야 하며 표준 출력에 표시되어야 한다.
• Goodbye Norminette! C++ 모듈에서는 코딩 스타일을 강제하지 않는다. 너는 너가 가장 좋아하는 것을 할 수 있다. 그러나 동료 평가자가 이해할 수 없는 코드는 채점할 수 없는 코드라는 점을 명심해라. 깨끗하고 읽기 쉬운 코드를 작성하기 위해 최선을 다해라.

허용/금지

너는 C에 관한 코딩을 할 수 없다. C++의 시간이다! 그러므로:

• 너는 표준 라이브러리에서의 거의 모든 것들을 사용할 수 있다. 따라서, 이미 알고 있는 것을 고수하는 대신, 익숙한 C함수의 C++ 버전을 최대한 많이 사용해보는 것이 현명할 것이다.
• 그러나, 너는 다른 외부 라이브러리를 사용할 수 없다. 이 말의 의미는 C++ 11과 Boost 라이브러리가 금지된다는 것이다. 다음 함수도 금지된다. printf(), alloc() and free(). 이걸 쓰면 너의 점수는 0점이 될 것이다.
• 달리 명시하지 않는 이상, namespace 및 friend 키워드의 사용은 금지된다. 사용하면 -42점이므로 주의하자.
• 오직 모듈 08와 09에서만 STL의 사용이 허용된다. 이 뜻은, 컨테이너(vector, list, map and forth)와 알고리즘(algorithm 헤더가 포함된 어떠한 것들)이 허용되지 않는다는 것이다. 이 또한 사용하면 -42점이다.

몇 가지 디자인 요구사항들

• 메모리 누수가 발생하는것은 C++도 동일하다. 만약 너가 메모리를 할당(new 키워드 사용으로)하면, 메모리 누수를 반드시 피해야한다.
• 모듈 02부터 09까지는 달리 명시된 경우를 제외하고, 클래스를 Orthodox Canonical Form으로 설계해야만 한다.
• 헤더파일에 선언되지 않은 함수들을 사용하는 경우 0점을 받는다.
• 각 헤더를 다른 헤더와 독립적으로 사용할 수 있어야 한다. 따라서 필요한 모든 종속성을 포함해야한다. 그러나 헤더가드를 사용해 이중으로 포함되는 것은 피해야만 한다. 그렇지 않으면 0점을 받을 것이다.

Read me

• 너는 필요(즉, 코드를 분할하기 위해)에 의해 파일을 추가할 수 있다. 이런 할당은 프로그램에서 확인하지 않으므로, 필수 파일을 제출하는 한 자유롭게 추가하면 된다.
• 때때로 과제의 가이드라인이 짧아보이지만, 명시적으로 작성되지 않은 요구사항들을 example에서 보여줄 수 있다.
• 시작 전에 꼭 모듈의 과제를 읽어야만 한다. 정말이다 !

많은 클래스를 구현해야 한다. 좋아하는 텍스트 편집기를 스크립팅할 수 없다면 이 작업은 지루해 보일 수 있다.

예제를 완료할 수 있는 어느 정도의 자유가 주어진다. 그러나 필수 규칙을 따르고 게으르지 마라. 많은 유용한 정보를 놓칠 것이다! 이론적 개념에 대해 읽는 것을 주저하지 말아라.

Chapter 3

Module-specific rules

이 모듈의 각 연습을 수행하려면 표준 컨테이너를 사용해야 한다. 컨테이너가 사용되면 모듈의 나머지 부분에 사용할 수 없다.

예제를 하기 전에 주제 전체를 읽는 것이 좋다.

두 개의 컨테이너를 사용해야 하는 예제 02를 제외하고 각 실습에 대해 적어도 하나의 컨테이너를 사용해야 한다.

-Wall, -Wextra 및 -Werror 플래그를 사용하여 소스 파일을 필요한 출력으로 컴파일할 각 프로그램에 대한 Makefile을 제출해야 한다.

C++를 사용해야 하며 Makefile은 리링크되면 안된다.

Makefile은 최소한 $(NAME), all, clean, fclean 및 re 규칙을 포함해야 한다.

Chapter 4

Ex00

문제

너는 특정 날짜에 일정량의 비트코인 값을 출력하는 프로그램을 만들어야 한다.

이 프로그램은 시간 경과에 따른 비트코인 가격을 나타내는 csv 형식의 데이터베이스를 사용해야 한다. 이 데이터베이스는 이 주제와 함께 제공된다.

프로그램은 평가할 다양한 가격/날짜를 저장하는 두 번째 데이터베이스를 입력으로 사용한다.

프로그램은 다음 규칙을 준수해야 한다.

• 프로그램 이름은 btc이다.
• 프로그램은 파일을 인수로 받아야 한다.
• 이 파일의 각 라인은 다음 형식을 사용해야 한다: "date | value"
• 유효한 날짜는 항상 "연-월-일" 형식이다.
• 유효한 값은 부동 소수점이거나 0에서 1000 사이의 양의 정수여야 한다.

이 예제의 유효성을 검사하려면 코드에서 하나 이상의 컨테이너를 사용해야 한다. 적절한 오류 메시지로 가능한 오류를 처리해야 한다.

다음은 input.txt 파일의 예시이다.

프로그램은 입력 파일의 값을 사용한다.

프로그램은 데이터베이스에 표시된 날짜에 따라 환율을 곱한 값의 결과를 표준 출력에 표시해야 한다.

입력에 사용된 날짜가 DB에 없으면 DB에 포함된 가장 가까운 날짜를 사용해야 한다. 상단 날짜가 아닌 하단 날짜를 사용하도록 주의해라.

다음은 프로그램 사용 예시이다.

경고: 이 예제의 유효성을 검사하는 데 사용하는 컨테이너는 이 모듈의 나머지 부분에서 더 이상 사용할 수 없다.

풀이

이 문제를 풀기 위해 다음과 같은 순서로 구현을 진행해주었다.

• 주어지는 data.csv에 대한 파싱 및 자료구조에 저장
• 입력되는 input.txt에 대한 파싱 및 유효성 판단
• 유효한 입력값에 대해서는 주어진 조건에 맞는 날짜의 값과 매칭
• 유효하지 않은 입력값은 적절한 에러 출력

먼저, 이 문제에서는 map이라는 자료구조를 사용해주었다. 그 이유로는 map의 주요 이점은 키를 기반으로 값을 효율적으로 검색할 수 있다는 것이고, 삽입, 삭제 및 검색 작업에 특화되어 시간복잡도를 줄일 수 있기 때문이다.

std::map - cppreference.com

다음은 map 데이터 구조와 관련된 몇 가지 중요한 속성 및 기능이다.

• Ordered: 맵의 요소가 키를 기준으로 자동으로 정렬된다. 기본적으로 키는 보다 작음 연산자를 사용하여 오름차순으로 정렬되며, 다른 정렬 순서가 필요한 경우 사용자 지정 비교 기능을 제공할 수도 있다.
• 고유 키: 맵의 각 키는 고유하다. 맵에 이미 존재하는 키로 새 키-값 쌍을 삽입하려고 하면 키와 연결된 기존 값이 업데이트된다.

1. 삽입: 키-값 쌍을 삽입하려면 insert() 함수를 사용하거나 연산자 []를 사용할 수 있다. insert() 함수는 쌍 또는 반복자를 취하고 삽입된 요소에 대한 반복자와 삽입이 발생했는지 여부를 나타내는 부울을 포함하는 쌍을 반환한다.

std::map<int, std::string> my_map;
my_map.insert(std::make_pair(1, "one"));
my_map.insert(std::make_pair(2, "two"));
my_map[3] = "three";

2. 검색: 키를 기준으로 값을 검색하려면 find() 기능을 사용할 수 있다. 이 함수는 키를 받아 해당 키가 있는 요소를 가리키는 반복자를 반환하고 키가 없으면 end() 반복자를 반환한다.

auto it = my_map.find(2);
if (it != my_map.end()) {
    std::cout << "Value for key 2: " << it->second << std::endl;
} else {
    std::cout << "Key 2 not found" << std::endl;
}

3. 삭제: 지도에서 키-값 쌍을 삭제하려면 erase() 함수를 사용할 수 있다. 이 함수는 키, 반복자 또는 반복자의 범위를 인수로 사용할 수 있다.

my_map.erase(1); // Erase the key-value pair with key 1
my_map.erase(my_map.find(2)); // Erase the key-value pair pointed to by the iterator

• 크기 및 용량: size() 함수는 맵에서 키-값 쌍의 수를 반환하고 empty() 함수는 맵이 비어 있는지 확인한다.

4. 반복: 반복자를 사용하여 맵의 요소를 반복할 수 있습니다. 맵이 정렬되어 있으므로 요소는 키별로 정렬된 순서로 방문된다.

for (auto it = my_map.begin(); it != my_map.end(); ++it) {
    std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
}

일단, 클래스의 구조는 다음과 같이 설계했다.

class BitcoinExchange {
  private:
    std::map<std::string, float> bitcoinData;

    int validateDate(std::string s);
    int validateInput(std::string s);
    void checkCsvFile();
    void checkInputFile(char *file);
    void bitcoin(char *file);
    void checkInfo(std::string);
    int checkDate(const std::string&);
    int checkValue(const std::string&);
    void printBit(std::string date, float n);
  public:
    BitcoinExchange();
    BitcoinExchange(const BitcoinExchange& ref);
    BitcoinExchange&    operator=(const BitcoinExchange& ref);
    ~BitcoinExchange();

    void play(char *file);

    class Error : public std::exception {
      public:
        const char* what() const throw();
    };
};

void BitcoinExchange::play(char *file) {
  try {
    checkCsvFile();
    checkInputFile(file);
  } catch (...) {
    return ;
  }
  bitcoin(file);
}

외부에서는 play 메서드를 통해서만 클래스에 접근이 가능하도록 구성했는데, 그 이유로 클래스 내부에서 에러 발생에 대한 처리를 해주기 위함이었다. 입력값과 주어진 데이터에 대한 유효성 판단을 통해 에러가 발생할 수 있는데, 이 경우 프로그램이 동작하지 않고 에러만 발생하고 종료해줄 수 있도록 처리해주었고, 입력값과 주어진 값이 모두 유효하다면, 프로그램이 실행될 수 있도록 구현했다.

먼저, 이 문제를 풀기위해서는 주어지는 data.csv와 input.txt의 구조를 파악한 뒤, 파싱을 적절하게 해주는것이 중요하다.

data.csv는 다음과 같은 구조이다.

date,exchange_rate
2009-01-02,0
2009-01-05,0
2009-01-08,0
2009-01-11,0
2009-01-14,0
2009-01-17,0
2009-01-20,0

첫줄을 제외한 각 줄이 날짜와 값으로 이루어져있으며, 콤마로 구분되어 있다. 이 데이터를 map 자료구조를 통해 날짜와 값을 각각 키와 값으로 구분해 저장해줄 수 있다.

이 파일을 저장해주기위해 아래 코드를 작성해주었다.

void BitcoinExchange::checkCsvFile() {
  std::ifstream csv("data.csv");
  std::string read;
  size_t date_size;
  float value;

  if (!csv) {
    std::cout << "Error: could not open database file" << std::endl;
    throw Error();
  }

  if (std::getline(csv, read).eof()) {
    std::cout << "Error: file empty or no data in." << std::endl;
    throw Error();
  }

  while(std::getline(csv, read)) {
    if (read != "date,exchange_rate") {
      date_size = read.find(',');
      if (validateDate(read.substr(0, date_size)) == FALSE) {
        std::cout << "Error: include invalid date." << std::endl;
        throw Error();
      }
      if (validateInput(read.substr(date_size + 1, read.length())) == FALSE) {
        std::cout << "Error: include invalid value." << std::endl;
        throw Error();
      }
      std::istringstream(read.substr(date_size + 1, read.length())) >> value;
      bitcoinData[read.substr(0, date_size)] = value;
    }
  }
}

이 코드로 csv 파일에 대한 검사와 파일 내부의 입력값에 대한 검사를 해주었다. 하단부 while문에서는 ','을 기준으로 문자열을 분리해주는데, 날짜와 값에 해당하는 문자열들이 유효한 값을 가지는지 검사를 진행한 뒤, map에 넣어주었다.

각 값의 유효함은 다음 함수들로 검증해주었다.

int BitcoinExchange::validateDate(std::string s) {
  if (s.length() != 10) return FALSE;
  std::string date_split;
  std::istringstream ss(s);
  int    year, month, day;
  int idx = 0;

  while (std::getline(ss, date_split, '-')) {
    if (idx == 0) {
      std::istringstream(date_split) >> year;
      if (year < 1000 || year > 9999) return FALSE;
    } else if (idx == 1) {
      std::istringstream(date_split) >> month;
      if (month < 1 || month > 12) return FALSE;
    } else if (idx == 2) {
      std::istringstream(date_split) >> day;
      if (day < 1 || day > 31) return FALSE;
      if (day == 31 && (month == 4 || month == 6 || month == 9 || month == 11)) return FALSE;
      if (year % 4 == 0 && (year % 100 != 0 || year % 400 == 0)) {
        if (day > 29 && month == 2) return FALSE;
      } else if (day > 28 && month == 2) return FALSE;
    }
    idx++;
  }

  if (idx != 3) return FALSE;
  return TRUE;
}

int BitcoinExchange::validateInput(std::string s) {
  char *ptr = NULL;
  double value = std::strtod(s.c_str(), &ptr);
  if (value == 0.0 && !std::isdigit(s[0])) return FALSE;
  if (*ptr && std::strcmp(ptr, "f")) return FALSE;
  if (value < 0) return FALSE;
  return TRUE;
}

각각의 유효성 체크 함수는 다음과 같은 조건을 검사한다.

• validateDate
  • 문자열의 길이가 정확히 10자인지 확인 ("YYYY-MM-DD" 형식이기 때문에)
  • '-'를 구분자로 입력받은 문자열을 분리해서 연, 월, 일 부분을 개별적으로 검사
  • 연도는 4자리 (1000 - 9999), 월은 1월부터 12월까지, 일은 1일부터 31일 내에 있는지 검사
  • 월과 일을 함께 검사해서 31일이 아닌 달에 31일이 입력되어있는지 검사 (4, 6, 9, 11월)
  • 2월이 28일인지 29일인지 검사 (윤년 처리)
• validateInput
  • double로 변환을 시도
  • 변환에 실패하면 FALSE 반환
  • 변환에 성공했지만, ptr 변수가 null이 아닐 경우 문자가 포함되어있다고 간주하고, ptr이 "f"가 아닐 경우 FALSE 반환. ("f"일 경우는 float형이 될 수 있음)
  • 변환된 값이 음수이면 FALSE 반환
    위 조건을 모두 통과하면 TRUE를 반환한다.

그 다음은 입력값으로 받아오는 파일의 유효성을 검사해주었다.

void BitcoinExchange::checkInputFile(char *file) {
  std::fstream fs;
  std::string str;

  fs.open(file, std::ifstream::in);
  if(!fs.is_open()) {
    std::cout << "Error : could not open file." << std::endl;
    throw Error();
  }

  if (std::getline(fs, str).eof()) {
    std::cout << "Error : File empty or no data in." << std::endl;
    throw Error();
  }

  if(str.compare("date | value") != 0) {
    std::cout << "Error : File format error." << std::endl;
    throw Error();
  }

  str.erase();
  fs.close();
}

이 함수에서 파일이 성공적으로 열렸는지, 파일의 첫 줄이 "date | value"와 같은지 등을 확인해준다.

void BitcoinExchange::bitcoin(char *file) {
  std::ifstream configfile(file);

  std::string read;
  getline(configfile, read);
  while(getline(configfile, read))
    checkInfo(read);
}

입력값과 주어진 값에 대한 검증이 완료되었다면, bitcoin 메서드에서 한 줄씩 읽어주면서 각 줄에 대한 처리를 해주게 된다. 입력값에 대한 오류가 존재한다면, 에러 발생 후 종료가 아닌 에러를 포함하여 출력주어야 하기 때문에, 에러 발생을 시켜주지 않고 표준출력으로만 에러를 처리해주었다.

void    BitcoinExchange::checkInfo(std::string info) {
  // istringstream -> string을 입력 받아 공백을 기준으로 파싱하여 변수 형식에 맞게 변환
  std::string date, str;
  std::istringstream formats(info);
  float    value;
  int idx = 0;

  while (std::getline(formats, str, ' ')) {
    if (idx == 0) {
      if (checkDate(str) == 0) return ;
      date = str;
    }

    if (idx == 1 && str != "|") {
      std::cout << "Error: bad input  => " << info << std::endl;
      return ;
    }

    if (idx == 2) {
      if (checkValue(str) == 0) return ;
      value = std::strtod(str.c_str(), NULL);
      if (value > 1000) {
        std::cout << "Error: too large a number." <<std::endl;
        return ;
      }
    }
    idx++;
  }

  if (idx != 3) {
    std::cout << "Error: bad input => " << info << std::endl;
    return ;
  }

  printBit(date, value);
}

int BitcoinExchange::checkDate(const std::string &dates) {
  std::string date_split;
  std::istringstream ss(dates);
  int    year, month, day;
  int idx = 0;

  if (dates.find('-', dates.length() - 1) != std::string::npos) {
    std::cout << "Error: incorrect date formate => " << dates << std::endl;
    return FALSE;
  }
  while (std::getline(ss, date_split, '-')) {
    if (idx == 0) {
      std::istringstream(date_split) >> year;
      if (year < 2009 || year > 2022) {
        std::cout << "Error: invalid year => " << dates <<std::endl;
        return FALSE;
      }
    }

    if (idx == 1) {
      std::istringstream(date_split) >> month;
      if (month < 1 || month > 12) {
        std::cout << "Error: invalid month => " << dates << std::endl;
        return FALSE;
      }
    }

    if (idx == 2) {
      std::istringstream(date_split) >> day;
      if (day < 1 || day > 31) {
        std::cout << "Error: bad input => " << dates << std::endl;
        return FALSE;
      }

      if (day == 31 && (month == 4 || month == 6 || month == 9 || month == 11)) {
        std::cout << "Error: incorrect days => " << dates << std::endl;
        return FALSE;
      }

      if (year % 4 == 0 && (year % 100 != 0 || year % 400 == 0)) {
        if (day > 29 && month == 2) {
          std::cout << "Error: incorrect days => " << dates << std::endl;
          return FALSE;
        }
      } else if (day > 28 && month == 2) {
        std::cout << "Error: incorrect days => " << dates << std::endl;
        return FALSE;
      }
    }
    idx++;
  }

  if (idx != 3) {
    std::cout << "Error : Wrong format => " << dates <<std::endl;
    return FALSE;
  }
  return TRUE;
}

int BitcoinExchange::checkValue(const std::string& str) {
  char *ptr = NULL;
  double value = std::strtod(str.c_str(), &ptr);

  if (str.find('.', 0) == 0 || str.find('.', str.length() - 1) != std::string::npos) {
    std::cout << "Error: not a Number" << std::endl;
    return FALSE;
  }

  if (value == 0.0 && !std::isdigit(str[0])) {
    std::cout << "Error: not a Number" << std::endl;
    return FALSE;
  }

  if (*ptr && std::strcmp(ptr, "f")) {
    std::cout << "Error: not a Number" << std::endl;
    return FALSE;
  }

  if (value < 0) {
    std::cout << "Error: not a positive number." << std::endl;
    return FALSE;
  }

  if (str.length() > 10 || (str.length() == 10 && value > 2147483647)) {
    std::cout << "Error: too large a number."<< std::endl;
    return FALSE;
  }
  return TRUE;
}

void    BitcoinExchange::printBit(std::string date, float n) {
  std::map<std::string, float>::const_iterator iter;
  float res;

  res = 0;
  iter = bitcoinData.find(date);
  if (iter != bitcoinData.end()) res = (iter->second) * n;
  else {
    iter = bitcoinData.lower_bound(date);
    if (iter == bitcoinData.begin()) {
      std::cout << "Error : invalid date" << std::endl;
      return;
    }
    --iter;
    res = (iter->second) * n;
  }

  (n == static_cast<int>(n)) ?
    std::cout << date << " => " << static_cast<int>(n) << " = " << res << std::endl :
    std::cout << date << " => " << n << " = " << res << std::endl;
}

checkInfo 메서드는 입력 줄의 유효성을 검사하고 날짜와 값을 추출해준다. checkDate() 메서드를 사용하여 날짜 형식을 확인하고 checkValue() 메서드를 사용하여 값을 확인한다. 입력이 유효하면 printBit() 메서드를 호출하여 변환된 값을 출력한다.

checkDate 메서드는 주어진 날짜 문자열이 올바른 형식이고 유효한 날짜를 나타내는지 확인한다. 연, 월, 일이 유효한 범위 내에 있는지 확인하여 유효성을 검사한다.(validateDate와 동일한 방법이다.)

checkValue 메서드는 주어진 입력 문자열 str이 음수가 아닌 부동 소수점 숫자로 성공적으로 변환될 수 있는지 확인한다.

printBit 메서드는 bitcoinData 맵에 저장된 비트코인 환율을 사용하여 변환된 값을 인쇄해준다. 먼저 지도에서 주어진 날짜를 검색하고, 날짜를 찾을 수 없는 경우 이전 날짜 중 주어진 날짜와 가장 근접한 날짜를 찾아 해당 날짜의 환율을 사용한다. 그런 다음 입력 값 'n'에 환율을 곱하여 변환된 값을 계산하고 그 결과를 인쇄한다.

여기까지 작성하면, date-value 쌍이 포함된 파일을 읽고, 입력값 검증 후, 비트코인 환율을 이용한 변환된 값들을 출력할 수 있다.

Ex01

문제

다음 제약 조건으로 프로그램을 생성해야 한다.

• 프로그램 이름은 RPN이다.
• 프로그램은 역폴란드어 수학 표현식을 인수로 취해야 한다.
• 이 작업에 사용되고 인수로 전달되는 숫자는 항상 10보다 작다. 계산 자체와 결과는 이 규칙을 고려하지 않는다.
• 프로그램은 이 식을 처리하고 표준 출력에 올바른 결과를 출력해야 한다.
• 프로그램 실행 중 오류가 발생하면 표준 출력에 오류 메시지가 표시되어야 한다.
• 프로그램은 다음 토큰을 사용하여 작업을 처리할 수 있어야 한다: "+ - * /"

이 예제의 유효성을 검사하려면 코드에서 하나 이상의 컨테이너를 사용해야 한다.

괄호나 십진수를 관리할 필요가 없다.

다음은 표준 사용의 예시이다.

경고: 이 예제의 유효성을 검사하는 데 사용하는 컨테이너는 이 모듈의 나머지 부분에서 더 이상 사용할 수 없다.

풀이

일단, 역폴란드 표기법에 대해 알아보자. 이 표기법은 후위 표기법이라고도 하며, 연산자를 연산 대상의 뒤에 쓰는 연산 표기법이다.

역폴란드 표기법 - 위키백과, 우리 모두의 백과사전

이 표기법의 방식은 수식을 계산할 때 특별한 변환이 필요없이, 수식을 앞에서부터 읽어 나가면서 스택에 저장하면 된다는 장점이 있다. 또한, 중위 표기법에서는 연산자의 우선순위가 모호해서 괄호가 필요한 경우가 있지만, 역폴란드 표기법에서는 그러한 문제점이 발생하지 않는다. 그러나 인간의 눈으로 쉽게 이해하거나 계산하기 힘들다는 문제점이 있어 눈에 보이는 표기보다는 주로 프로그램 내부의 표기법으로 사용한다.

이 문제를 풀기 위해, 예외를 먼저 처리해주었다.

• 입력값은 한 개의 문자열만 받는다
• 숫자는 10 미만의 수만 들어올 수 있다. 단, 음수가 들어올 경우, 연산자와 혼동이 일어날 수 있으므로 음수 또한 예외를 발생시켜주었다.
• 숫자와 연산자를 제외한 다른 모든 문자는 들어올 수 없다. (단, 소수를 나타내기 위한 '.'은 가능하다.)

일단, 클래스의 구조는 다음과 같이 작성해주었다.

class RPN {
  private:
    std::string stringArgv;
    std::stack<double> rpn;
    std::stack<std::string> splitString;
    int numberOfValues;

    RPN();

    void split();
    void validateInput(std::string s);
    bool isOperator(char op);
    void calculate();
    double calculator(double a, double b, char op);
  public:
    RPN(char *av);
    RPN(const RPN& ref);
    RPN&    operator=(const RPN& ref);
    ~RPN();

    void play();

    class Error : public std::exception {
      public:
        const char* what() const throw();
    };
};

이번 예제에서는 스택을 활용해주었다. 스택(Stack)은 후입선출(Last-In-First-Out, LIFO) 원리를 따르는 자료구조로, 데이터를 일시적으로 저장하기 위한 자료구조이다. 스택은 가장 최근에 추가된 항목이 가장 먼저 제거되는 구조를 가지고 있다.

std::stack - cppreference.com

스택은 기본적으로 두 가지 주요 동작을 수행할 수 있다. 첫 번째는 push 동작으로, 스택의 맨 위에 항목을 추가한다. 두 번째는 pop 동작으로, 스택에서 가장 최근에 추가된 항목을 제거한다. 스택은 항목을 추가할 때마다 스택의 크기를 늘리고, 항목을 제거할 때마다 스택의 크기를 줄인다.

스택은 다양한 알고리즘과 데이터 구조에서 사용된다. 예를 들어, 함수 호출 시 함수 호출 정보를 저장하는 스택 프레임(Stack Frame)을 구현하는 데 사용됩니다. 또한, 스택은 괄호 검사(Parenthesis Matching)와 같은 문제를 해결하는 데에도 유용하게 사용된다.

또한, 문자열을 분리해주기 위한 split 멤버함수, 분리된 문자열을 검증해주기 위한 validateInput, 문자열 중 연산자인지 확인하기 위한 isOperator, 역폴란드 표기법을 계산해주기 위한 calculate, calculator 함수로 구성되어있다.

void RPN::split() {
  std::istringstream ss(this->stringArgv);
  std::string stringBuffer;
  std::stack<std::string> tmp;
  while (std::getline(ss, stringBuffer, ' ')) {
    if (stringBuffer.empty()) continue;
    tmp.push(stringBuffer);
  }

  this->numberOfValues = 0;
  while (!tmp.empty()) {
    this->splitString.push(tmp.top());
    validateInput(tmp.top());
    tmp.pop();
  }

  if (2 * this->numberOfValues - this->splitString.size() != 1) throw RPN::Error();
}

이 함수로 입력받은 문자열을 분리해줄 수 있다. 분리된 문자열을 스택에 담아 보관해주고 싶었다. 스택에 들어갈 때는 맨 처음 들어간 요소가 가장 마지막에 나오기 때문에, tmp스택을 하나 만들어주어 분리된 문자열을 차례대로 넣어준 뒤, 클래스의 멤버 변수로 가지고 있는 splitString 스택에 다시 마지막부터 차례대로 넣어주었다. tmp 스택에 넣어줄 때는, stringBuffer에 공백이 들어갈 수도 있으므로, empty 메서드로 공백을 판단한 뒤, 공백이 아닌 문자들만 tmp 스택에 넣어주었다.

splitString 스택에 넣어주면서, 분리된 문자열을 validateInput 함수를 통해 검증해주었다.

void RPN::validateInput(std::string s) {
  if (s.length() == 1 && (s[0] == '+' || s[0] == '-' || s[0] == '*' || s[0] == '/'))
    return ;
  char *ptr = NULL;
  double value = std::strtod(s.c_str(), &ptr);
  if (value == 0.0 && !std::isdigit(s[0])) throw RPN::Error();
  if (*ptr && std::strcmp(ptr, "f")) throw RPN::Error();
  if (value < 0 || value >= 10) throw RPN::Error();
  ++this->numberOfValues;
}

여기서는 다음과 같은 검증을 하게 된다.

• 문자열의 길이가 1이면서 그 문자가 연산자인지
• 연산자가 아니라면 숫자이므로 숫자 검증
  • strtod 함수를 이용해 문자열을 double형으로 변환
  • 만약 값이 0이고 문자열의 처음이 숫자가 아니라면 에러 발생
  • double형으로 변환되었지만 필요없는 문자가 섞여있는 경우 에러 발생 -> ex. 9.5a
  • 변환된 double형의 값이 0 미만이거나 10 이상인 경우 에러 발생

여기서 numberOfValues라는 멤버 변수로 숫자의 갯수를 세어주는 이유는 역폴란드 표기법은 항상 숫자와 연산자의 갯수가 1개 차이가 나기 때문이다. 만약 1개 차이가 아니라면, 에러를 발생시킨다.

bool RPN::isOperator(char op) {
  return (op == '+' || op == '-' || op == '*' || op == '/');
}

double RPN::calculator(double a, double b, char op) {
  if (op == '+') return (a + b);
  if (op == '-') return (a - b);
  if (op == '*') return (a * b);
  if (b == 0) throw RPN::Error();
  return (a / b);
}

void RPN::calculate() {
  while (!this->splitString.empty()) {
    std::string tmp = this->splitString.top();
    if (isOperator(tmp[0])) {
      if (this->rpn.size() < 2) throw RPN::Error();
      double a, b;
      b = this->rpn.top();
      this->rpn.pop();
      a = this->rpn.top();
      this->rpn.pop();
      this->rpn.push(this->calculator(a, b, tmp[0]));
      this->splitString.pop();
    }
    else {
      double value = std::strtod(this->splitString.top().c_str(), NULL);
      this->rpn.push(value);
      this->splitString.pop();
    }
  }
  std::cout << this->rpn.top() << std::endl;
}

입력값에 대한 검증이 완료되었다면, 계산을 해주었다. 계산은 다음과 같은 로직으로 진행된다.

• splitString의 맨 위 값이 숫자라면
  • rpn 스택에 넣어준다.
  • splitString의 맨 위 값은 제거해준다.
• splitString의 맨 위 값이 연산자라면
  • rpn 스택의 크기가 2 미만이라면 에러가 발생한다.
  • rpn 스택의 크기가 2 이상이라면 rpn 스택의 맨 위 두 값을 빼준 뒤, 연산자에 맞는 계산 수행 후 rpn 스택에 다시 넣어준다.
• splitString 스택이 비었다면, rpn의 맨 위 값을 출력해준다.

이 모든 과정을 관리해주고 외부에서 호출되는 함수를 만들어주었다.

void RPN::play() {
  try {
    split();
    calculate();
  } catch (std::exception& e) {
    std::cout << e.what() << std::endl;
  }
}

이 함수에서 split과 calculate 함수에서 발생하는 모든 에러에 대한 처리를 해주었다.

결과적으로, 만들어진 RPN 클래스는 다음과 같은 멤버 함수와 변수를 포함하고 있다.

1. 생성자:

• RPN(): 기본 생성자
• RPN(char *av): 문자열을 입력으로 받아 RPN 계산기를 초기화하는 생성자
• RPN(const RPN& ref): 복사 생성자

2. 할당 연산자 오버로드:

• operator=(const RPN& ref): 대입 연산자를 오버로드하여 RPN 객체의 값을 복사

3. 소멸자:

• ~RPN(): 소멸자

4. 멤버 함수:

• play(): 전반적인 로직이 담겨있고, 에러가 발생한다면 에러를 발생시켜줌
• split(): 문자열을 공백으로 구분하여 피연산자와 연산자를 스택에 저장
• validateInput(std::string s): 입력된 문자열이 유효한지 확인하고, 피연산자의 개수를 업데이트
• isOperator(char op): 문자가 연산자인지 확인
• calculator(double a, double b, char op): 두 피연산자와 연산자를 사용하여 연산을 수행
• calculate(): RPN 표현식을 계산하고 결과를 출력

5. 멤버 변수:

• std::stackstd::string splitString: 입력 문자열을 공백으로 구분하여 저장하는 스택
• std::stack<double> rpn: RPN 계산에 사용되는 실수 값을 저장하는 스택
• int numberOfValues: 입력 문자열에서 발견된 피연산자의 개수

6. 예외 클래스:

• Error: RPN 클래스에서 발생하는 오류를 처리하기 위한 예외 클래스. std::exception을 상속받음.

Ex02

문제

다음 제약 조건으로 프로그램을 생성해야 한다.

• 프로그램 이름은 PmergeMe 이다.
• 프로그램은 양의 정수 시퀀스를 인수로 사용할 수 있어야 한다.
• 프로그램은 병합-삽입 정렬 알고리즘을 사용하여 양의 정수 시퀀스를 정렬해야 한다.
• 프로그램 실행 중 오류가 발생하면 표준 출력에 오류 메시지가 표시되어야 한다.

이 예제의 유효성을 검사하려면 코드에서 두 개 이상의 컨테이너를 사용해야 한다. 프로그램은 적어도 3000개의 서로 다른 정수를 처리할 수 있어야 한다.

각 컨테이너에 대해 알고리즘을 구현하여 일반 함수를 사용하지 않는 것이 좋다.

다음은 표준 출력에 표시해야 하는 정보에 대한 추가 지침이다. 이 정보는 다음과 같이 줄 단위로 표시되어야 한다.

• 첫 번째 줄에는 명시적인 텍스트와 함께 정렬되지 않은 양의 정수 시퀀스를 표시해야 한다.
• 두 번째 줄에는 명시적인 텍스트와 함께 정렬된 양의 정수 시퀀스를 표시해야 한다.
• 세 번째 줄에는 알고리즘이 사용한 시간을 첫 번째 컨테이너를 사용하여 양의 정수 시퀀스를 정렬하는 데 걸린 시간을 명시하는 명시적인 텍스트를 표시해야 한다.
• 마지막 줄에는 알고리즘이 사용한 시간을 두 번째 컨테이너를 사용하여 양의 정수 시퀀스를 정렬하는 데 걸린 시간을 명시하는 명시적인 텍스트를 표시해야 한다.

분류를 수행하는 데 사용되는 시간 표시 형식은 자유지만 선택한 정밀도는 사용된 두 컨테이너 간의 차이를 명확하게 볼 수 있어야 한다.

다음은 표준적인 사용 예시이다.

이 예제에서 시간 표시는 고의적으로 이상하게 되어 있다. 당연히 모든 작업을 수행하는 데 걸린 시간을 표시해야 한다. 정렬 부분과 데이터 관리 부분 모두 포함된다.

주의: 이전 예제에서 사용한 컨테이너들은 여기서 사용이 금지되어 있다.

중복과 관련된 오류 처리는 너의 재량에 따라 결정해라.

풀이

먼저, 입력값을 받아주기 위해 벡터를 사용해 주었다.

bool validateInput(std::string s) {
  char *ptr = NULL;
  double value = std::strtod(s.c_str(), &ptr);
  if (value == 0.0 && !std::isdigit(s[0])) return false;
  if (*ptr && std::strcmp(ptr, "f")) return false;
  if (value < 0) return false;
  return (value == static_cast<int>(value));
}

int main(int ac, char **av) {
  if (ac < 2) {
    std::cout << "Error" << std::endl;
    return 1;
  }
  std::vector<int> originalData;
  int i = 1;
  while (i < ac) {
    std::string stringTmp(av[i]);
    std::istringstream ss(stringTmp);
    std::string stringBuffer;
    while (std::getline(ss, stringBuffer, ' ')) {
      if (!stringBuffer.empty() && validateInput(stringBuffer) == false) {
        std::cout << "Error" << std::endl;
        return 1;
      }
      if (stringBuffer.empty()) continue;
      originalData.push_back(static_cast<int>(strtod(stringBuffer.c_str(), NULL)));
    }
    ++i;
  }
  return 0;
}

나는 입력값 처리를 main에서 처리해주었는데, PmergeMe 클래스에 벡터값을 생성자의 인자로 넣어주기 위함이었다.

validateInput함수를 통해 문자열 s가 유효한 숫자인지 확인해주었다. 다음 조건을 만족하면 true를 반환하고, 그렇지 않으면 false를 반환한다.

• 문자열 s가 올바른 숫자 형식이어야 한다.(예: "12.0", "42" 등)
• 문자열 s가 소수점을 포함할 경우, 소수부가 없어야 한다.(예: "12.0"은 유효하나 "12.5"는 유효하지 않습니다)
• 문자열 s가 음수일 경우 유효하지 않는다.

유효한 숫자들을 originalData 벡터에 저장해준다.

• std::istringstream을 사용하여 현재 인자를 공백을 기준으로 분리한다.
• std::getline 함수를 사용하여 공백을 기준으로 분리된 각 문자열을 처리한다.
• 만약 분리된 문자열이 비어있지 않고 validateInput 함수를 통과하지 못할 경우, "Error"를 출력하고 프로그램을 종료한다.
• 비어있지 않은 문자열이 유효한 경우, strtod 함수를 사용하여 문자열을 double로 변환한 다음 static_cast를 사용하여 정수로 변환하고 originalData 벡터에 추가해준다.

그리고 PmergeMe 클래스를 만들어주었다.

class PmergeMe {
  private:
    std::vector<int> originalData;
    std::vector<int> vectorData;
    std::list<int> listData;
    std::deque<int> dequeData;

    PmergeMe();

    void printBefore();
    void printAfter();

    void vectorSort();
    void listSort();
    void dequeSort();

    void mergeInsertionSortVector(int left, int right, int k);
    void mergeInsertionSortList(int left, int right, int k);
    void mergeInsertionSortDeque(int left, int right, int k);

    void insertionSortVector(int left, int right);
    void insertionSortList(int left, int right);
    void insertionSortDeque(int left, int right);

    void mergeVector(int l, int m, int r);
    void mergeList(int l, int m, int r);
    void mergeDeque(int l, int m, int r);

    int getValueOfList(std::list<int> list, int idx);
    void setValueOfList(int idx, int value);

    int getValueOfDeque(std::deque<int> deque, int idx);
    void setValueOfDeque(int idx, int value);

  public:
    PmergeMe(std::vector<int> vec);
    PmergeMe(const PmergeMe& ref);
    PmergeMe&    operator=(const PmergeMe& ref);
    ~PmergeMe();
    void sort();
};

메서드가 조금 많아졌다.

이번 과제에서는 벡터, 리스트, 덱을 사용했다.

std::vector - cppreference.com

std::list - cppreference.com

std::deque - cppreference.com

각 자료구조의 특징과 장단점을 알아보자면 다음과 같다.

1. 벡터(Vector)

• 구현: 동적 배열
• 특징
  • 연속된 메모리 공간에 요소를 저장
  • 원소에 대한 랜덤 액세스가 가능
• 장점
  • 빠른 임의 접근
  • 메모리 할당이 효율적
• 단점
  • 크기 조정에 상대적으로 느림 (실제 크기가 할당된 용량을 초과하면 전체를 다시 할당해야 함)
  • 중간에 원소를 삽입하거나 삭제하는데 시간이 오래 걸림 (뒤에 있는 원소들을 이동해야 함)

2. 리스트(List)

• 구현: 이중 연결 리스트
• 특징
  • 각 요소가 다음 요소와 이전 요소에 대한 포인터를 가짐
  • 원소들이 메모리 상에서 불연속적으로 저장
• 장점
  • 원소의 삽입 및 삭제가 빠름 (포인터만 변경하면 됨)
  • 크기가 가변적이며 메모리를 효율적으로 사용
• 단점
  • 임의 접근이 느림 (선형 검색이 필요)
  • 포인터를 저장하기 위한 추가 메모리 사용

3. 덱(Deque)

• 구현: 동적 배열의 배열
• 특징
  • 여러 개의 연속된 메모리 블록에 요소를 저장
  • 양쪽 끝에서의 원소 삽입 및 삭제가 빠름
• 장점
  • 벡터처럼 빠른 임의 접근 가능
  • 리스트처럼 양쪽 끝에서의 원소 삽입 및 삭제가 빠름
• 단점
  • 메모리 오버헤드가 있음 (여러 메모리 블록 관리)
  • 중간 원소의 삽입 및 삭제가 비교적 느림

요약하자면, 각 자료구조의 선택은 사용 사례에 따라 다르다.

벡터(Vector)는 랜덤 액세스와 효율적인 메모리 사용이 중요한 경우에 적합하다. 하지만, 중간 원소의 삽입 및 삭제가 빈번하게 발생하는 경우에는 부적합하다.
리스트(List)는 원소의 삽입 및 삭제가 빈번하게 발생하며, 랜덤 액세스가 상대적으로 덜 중요한 경우에 적합하다. 하지만, 메모리 사용에 더 많은 오버헤드가 발생하며, 랜덤 액세스가 느리다는 단점이 있다.
덱(Deque)는 양쪽 끝에서의 삽입 및 삭제가 빈번하게 발생하고, 빠른 랜덤 액세스도 필요한 경우에 적합하다. 하지만, 메모리 오버헤드가 있으며, 중간 원소의 삽입 및 삭제가 비교적 느리다는 단점이 있다.
결국, 사용 사례와 요구 사항에 따라 가장 적합한 자료구조를 선택하는 것이 중요하다. 또한, C++ 표준 라이브러리에서 제공하는 이 자료구조들은 모두 템플릿 기반으로 작성되어 있어, 다양한 데이터 타입을 저장할 수 있어 유연성이 높다.

병합 삽입 정렬은 병합 정렬과 삽입 정렬의 원리를 결합하여 정렬 프로세스의 성능을 향상시키는 하이브리드 정렬 알고리즘이다. 이 알고리즘의 기본 아이디어는 두 알고리즘의 강점을 활용하여 전반적인 효율성을 높이는 것이다.

병합 삽입 정렬 알고리즘에 대한 자세한 설명은 다음과 같다.

1. 입력 배열 나누기: 병합 정렬과 마찬가지로 하위 배열의 크기가 작아질 때까지(예: 임계값 k보다 작거나 같음) 입력 배열을 재귀적으로 두 개의 동일한 절반으로 나눠준다. k 값은 입력 데이터의 크기와 특정 시스템의 삽입 정렬 효율성에 따라 실험적(혹은 임의적)으로 결정할 수 있다.

2. 기본 사례 - 삽입 정렬 사용: 하위 배열 크기가 임계값 k보다 작거나 같은 경우 삽입 정렬을 적용하여 이러한 작은 하위 배열을 정렬한다. 삽입 정렬은 작은 크기의 배열과 거의 정렬된 배열에 효율적이다. 이러한 작은 하위 배열에서 삽입 정렬을 사용하면 작은 크기의 입력에 대해 우수한 성능을 활용할 수 있다.

3. 정렬된 하위 배열 병합: 정렬된 하위 배열을 병합하여 정렬된 배열을 형성한다. 병합 단계는 요소를 비교하고 더 작은 요소를 정렬된 순서로 결과 배열에 배치하여 두 개의 정렬된 하위 배열을 병합하는 병합 정렬과 동일하다.

병합 삽입 정렬의 시간 복잡도는 입력 배열의 크기와 임계값 k에 따라 다르다. 임계값 k를 현명하게 선택하면 시간 복잡도는 Merge Sort의 시간 복잡도인 O(n log n)에 가까워질 수 있다.

요약하면 병합 삽입 정렬은 병합 정렬과 삽입 정렬의 장점을 모두 활용하는 하이브리드 정렬 알고리즘이며, 입력 배열을 더 작은 하위 배열로 나누고 삽입 정렬을 사용하여 작은 하위 배열을 정렬한 다음 병합 정렬의 병합 단계를 사용하여 정렬된 하위 배열을 병합한다. 이 조합은 병합 정렬 또는 삽입 정렬을 단독으로 사용할 때보다 성능을 향상시킬 수 있다.

병합 삽입 정렬 알고리즘을 한번 짜면 사용하는 자료구조가 살짝 바뀔 뿐이지, 알고리즘 자체가 변하지는 않으므로 벡터를 기준으로 코드를 보자.

void PmergeMe::vectorSort() {
  clock_t start = clock();
  mergeInsertionSortVector(0, this->vectorData.size() - 1, 5);
  clock_t end = clock();
  printAfter();
  std::cout << "Time to process a range of " << std::setw(4) << this->vectorData.size() << " elements with std::vector : " << end - start << "ms" << std::endl;
}

void PmergeMe::insertionSortVector(int left, int right) {
  for (int i = left + 1; i <= right; i++) {
    int key = this->vectorData[i];
    int j = i - 1;
    while (j >= left && this->vectorData[j] > key) {
      this->vectorData[j + 1] = this->vectorData[j];
      j--;
    }
    this->vectorData[j + 1] = key;
  }
}

void PmergeMe::mergeVector(int l, int m, int r) {
  int n1 = m - l + 1;
  int n2 = r - m;

  std::vector<int> left(n1), right(n2);

  for (int i = 0; i < n1; i++) left[i] = this->vectorData[l + i];
  for (int j = 0; j < n2; j++) right[j] = this->vectorData[m + 1 + j];

  int i = 0;
  int j = 0;
  int k = l;

  while (i < n1 && j < n2) {
    if (left[i] <= right[j]) {
      this->vectorData[k] = left[i];
      i++;
    } else {
      this->vectorData[k] = right[j];
      j++;
    }
    k++;
  }

  while (i < n1) {
    this->vectorData[k] = left[i];
    i++;
    k++;
  }

  while (j < n2) {
    this->vectorData[k] = right[j];
    j++;
    k++;
  }
}

void PmergeMe::mergeInsertionSortVector(int left, int right, int k) {
  if (right - left + 1 <= k) {
    insertionSortVector(left, right);
  } else if (left < right) {
    int m = left + (right - left) / 2;
    mergeInsertionSortVector(left, m, k);
    mergeInsertionSortVector(m + 1, right, k);
    mergeVector(left, m, right);
  }
}

 

1. vectorSort(): 이 메서드는 병합 삽입 정렬 알고리즘을 사용하여 vectorData 멤버 변수를 정렬하기 위한 진입점이다. 현재 시간을 기록하여 타이머를 시작하고 좌우 경계와 임계값 k로 mergeInsertionSortVector() 메서드를 호출한 다음 경과 시간을 계산하여 출력해준다.

2. insertionSortVector(int left, int right): 이 메서드는 left에서 right 인덱스까지 vectorData의 하위 배열에 대한 삽입 정렬 알고리즘을 구현한다.

3. mergeVector(int l, int m, int r): 이 메서드는 vectorData의 정렬된 두 하위 배열을 병합한다. 여기서 l은 왼쪽 인덱스, m은 중간 인덱스, r은 올바른 지수이다. 왼쪽 하위 배열은 vectorData[l..m]이고 오른쪽 하위 배열은 vectorData[m+1..r]이다.

4. mergeInsertionSortVector(int left, int right, int k): 이 메서드는 병합 삽입 정렬 알고리즘의 기본 구현이다. 정렬할 하위 배열의 'left' 및 'right' 인덱스와 임계값 'k'를 입력으로 받는다. 하위 배열 크기가 임계값 k보다 작거나 같으면 insertionSortVector()를 호출하여 하위 배열을 정렬하고, 그렇지 않으면 하위 배열을 두 개의 절반으로 재귀적으로 나누고 각 절반에서 mergeInsertionSortVector()를 호출한다. 두 반쪽이 정렬된 후 mergeVector()를 호출하여 정렬된 반쪽을 병합한다.

나는 k를 5로 설정해주었는데, 이 값은 정말 임의로 설정해도 좋다. 기회가 된다면 k를 벡터 길이의 절반으로 설정해서 프로그램을 실행해보자. 극명한 시간차이가 나타날 것이다.

벡터는 인덱스 접근이 가능하기 때문에, 병합 삽입 정렬을 수행할 때 꽤 좋은 성능을 발휘할 수 있다. 하지만 리스트나 덱의 경우, 인덱스 접근을 할 수 없으므로 반복자를 이용해 접근을 해야한다.

int PmergeMe::getValueOfList(std::list<int> list, int idx) {
  std::list<int> tmpList;

  tmpList.assign(list.begin(), list.end());
  std::list<int>::iterator iter = tmpList.begin();
  while (idx--) ++iter;
  return *iter;
}

void PmergeMe::setValueOfList(int idx, int value) {
  std::list<int>::iterator iter = this->listData.begin();
  while (idx--) ++iter;
  *iter = value;
}

나는 이 두 메서드를 통해 리스트의 값들을 인덱스로 접근하는 것처럼 설정하고 참조할 수 있었다.(덱 또한 동일한 메서드를 만들어주었다.) 하지만 코드를 보면 알 수 있듯이 n번째 인덱스에 접근하기 위해서는 처음부터 n번째까지 반복자를 증가시키는 방식으로 구현해주었다.

여기서 ++연산자는 단순히 iter = iter + 1이 아닌 연결리스트로써 다음 요소로 접근하기 위한 방식이다. 따라서, iter = iter + idx와 같은 식은 동작하지 않는다.

이 부분에서 반복문의 사용이 많아지기 때문에, 필연적으로 리스트의 사용은 벡터보다 시간이 더 걸릴 수 밖에 없다.

간단하게 인자를 넣어줬음에도 유의미한 시간 차이가 존재함을 알 수 있다.

마치며

여기까지 cpp module 09를 진행해보았는데, 여러 자료구조를 사용해보는 시간을 가질 수 있었고, 문제들이 해결하기 쉽지도 어렵지도 않은 적당한 난이도로 구성되어 있어 더 재미있게 코드를 작성했었다. 다음은 인셉션과 웹서브로 돌아오도록 하겠다..