알고리즘을 위한 CPP - garyGitgit/mywiki GitHub Wiki

endl 을 사용하지 말자

endl 은 버퍼를 비우는 역할을 하기 때문에 단지 줄바꿈(newline)을 위해서 endl 을 사용하지는 말 것. 대신 "\n" 또는 '\n' 을 사용하자

cout << "Hello world" << endl; (:x:)
cout << "Hello world" << "\n"; (:o:)

The only difference is that std::endl flushes the output buffer, and '\n' doesn't. If you don't want the buffer flushed frequently, use '\n'. If you do (for example, if you want to get all the output, and the program is unstable), use std::endl.

설명 참고 : https://github.com/garyGitgit/mywiki/wiki/_new

vector

vector 의 loop : 벡터를 for loop 처럼 사용하고 싶을 때.

iterator 를 사용하는 것이 코드의 유연성을 높여준다. (array 의 for 문처럼 사용해도 사실 상관없다)

#include <iostream>
#include <vector>
using namespace std;
int main(int argc, const char * argv[]) {
    vector<int> groups;
    groups.push_back(1);
    groups.push_back(2);
    groups.push_back(3);
    
    //1,2,3 을 출력한다
    for(vector<int>::iterator it = groups.begin(); it != groups.end(); ++it) {
        cout << (*it) << "\n";
    }
    return 0;
}

벡터에서 index 를 확인하고 싶을 때

int index = iterator - myvector.begin();

코드 참고 : https://stackoverflow.com/questions/409348/iteration-over-stdvector-unsigned-vs-signed-index-variable
코드 스타일 참고 : https://stackoverflow.com/questions/12702561/iterate-through-a-c-vector-using-a-for-loop
벡터 인덱스 참고 : http://www.cplusplus.com/forum/general/71342/

vector 로 2D 배열

vector< vector<int> > matrix(N+1,vector<int>(N+1));

2d vector 를 넘기는 방법은 여러가지가 있지만, reference(참조자) 라는 개념을 이용하여 구현했다.

//메인함수
catchMaxflies(matrix, M);

//catchMaxflies 함수
void catchMaxflies(vector<vector<int> > &matrix, int M){ }

vector 에 초깃값 설정하기

vector<bool> myVector(N ,false);

vector의 insert

이 문제를 풀면서 vector 의 insert, delete, append 에 대해서 배우게 됐다
vector의 insert
- iterator 를 잘 이용할 줄 알아야한다. index 로 접근하는게 아니라 일단 iterator 로 접근
- vector 의 첫 번째 자리를 업데이트하면 iterator 도 다시 할당받아야한다

vector<int>::iterator it = myvector.begin();
myvector.insert (it,2,300);
// "it" no longer valid, get a new one:
it = myvector.begin();

💡 시간복잡도 : insert 된 자리에서 업데이트(copy / move)되는 element의 갯수 + insert 되는 element 의 갯수 참고자료 : http://www.cplusplus.com/reference/vector/vector/insert/

vector 안에 다른 vector 를 한 번에 insert 할 수 있다

vector<int> new_vector {0, 0, 0, 0};
myvector.insert(it + 5, new_vector.begin(), new_vector.end());

vector 안에 array 를 한 번에 insert 할 수 있다

int new_arr[4] {0, 0, 0, 0};
myvector.insert(it + 5, new_arr, new_arr+4);

vector의 delete

erase(시작 iterator, 끝 iterator) 함수를 쓴다

myvector.erase(it, it+5);

💡 시간복잡도 : delete 되는 element 갯수 + delete 한 후 업데이트 되는 element들의 갯수

string

string 뒤에 char 추가하는 법

str.push_back((char)something);
//또는
str += (char)something;

⚠️ 주의 : char array 를 만들고 그 뒤에 append(char array) 하면 된다했는데, 이건 잘 안 먹혔다.

string capacity 와 max_size

capacity : 메모리를 재할당할 필요없이 사용할 수 있는 문자열의 길이. 문자열이 증가했을 때, capacity 보다 더 크면, 메모리를 재할당해준다.
max_size : 최대로 만들 수 있는 문자열의 길이

string str = "hello world";
str.capacity();
str.max_size();

string 의 특정 위치에 있는 char 가져오기

string.at() 또는 string[index] 로 쓴다

string str = "hello world";
str.at(1); // e
str[1]; // e

string 안에 있는 단어 검색

string.find("word") 를 사용한다. 단어가 등장하는 첫 번째 위치(string 의 index)를 반환한다.
string::npos 라는 것이 있는데, 탐색에 실패했을 경우 반환을 한다.

string sentence = "Hello this is gary noh. Nice to meet you, gary";
if(sentence.find("gary") != string::npos){
  //do something
}

string 의 복사

c++ 에서 = 연산자는 복사를 하는 기능을 가지고 있다. 단순히 주소값만 복사하는게 아니다. 이것을 deep copy라고 부른다.

string A = "A";
string B = A;
cout << "A : " << A << "B : " << B << "\n";
B = "B";
//A 값은 바뀌지 않은 것을 볼 수 있다
cout << "A : " << A << "B : " << B << "\n";

string 의 비교

연산자 비교 (==, >, < ...)
string1.compare(string2) 사용 : string1 이 사전상으로 앞이면 음수, 사전상으로 뒤면 양수

string k1 = "kkk";
string k2 = "kk";
cout << k1.compare(k2) << "\n";
//1을 출력한다

혹시 소팅도 가능할까?

vector<string> v {"a", "c", "z", "e", "d", "g", "w", "l"};
sort(v.begin(), v.end()); //begin, end 로 하는 게 포인트 : array 는 sort(array, array+N); 으로 해야함 
for(int i = 0 ; i < (int)v.size(); i++){
  cout << v[i] << " ";
}
cout << "\n";

string 의 대체 (replace)

string.replace(position, thisword.length, replaceword) : 교체할 단어의 위치와 단어의 길이, 그리고 교체할 단어를 파라미터로 넘긴다

string sentence = "Hello this is gary noh. Nice to meet you, gary";
    string findword = "gary";
    int findword_len = (int)findword.length();
    string replaceword = "GARY";
    size_t pos = 0;
    while( (pos = sentence.find(findword)) != string::npos) {
        sentence.replace(pos, findword_len, replaceword);
        pos += replaceword_len;
    }
    cout << sentence << "\n";

만약에 함수를 구성했을 때 파라미터를 string str 으로 선언했으면, immutable replace 라 하고, string &str 으로 선언했으면, mutable replace 라 부른다.
💡 mutable : 변경 가능 객체
std::string 은 mutable 이다. 💡 immutable : 변경 불가능 객체 c++ 에서 string 은 immutable 이고, Java 에서는 mutable 이다.
참고 : string 을 선언하는 다른 방법이 있다. char str = "hello world"; 인데 c++ 은 literal("hello word")를 char(str)로 변환하는 것을 허용하지 않는다 한다. 그렇기 때문에 const char *str = "hello word" 로 선언을 해야한다.
참고자료 mutable vs immutable : http://ledgku.tistory.com/54
참고자료 c++ string 에 대해서 : http://makerj.tistory.com/127

string 의 형 변환

c++ 11에서는 정수에서 문자열로 형변환을 할 때 std::to_string 이라는 함수를 쓸 수 있고, 문자열을 문자열을 정수로 변환할 때는 stoi()를 사용한다. c++11 을 지원하지 않으면 어쩔 수 없이 직접 짜야한다.

#include <sstream>
int main(){
  int num = 12345;
  string num_str;
  sstream ss;
  ss << num;
  num_str = ss.str();
  return 0;
}

cout 으로 formatting (반올림) 하기

cout.precision(2); //소수 셋째자리에서 반올림 (두번째 자리까지만 출력)

참고 : http://repilria.tistory.com/243

정렬하기

STL library : algorithm 을 사용하자.
오름차순으로 정렬하는 방법

int N;
int arr[N];
cin >> N;
int arr[N];
sort(arr, arr+N);

내림차순으로 정렬을 하고 싶다, 또는 특정 기준에 의해서 정렬을 하고 싶다면
1. cmp 함수를 넣는다 (반환값이 true/false 인 function을 넣어주면된다)

bool myFunc(int a, int b){
    return a > b;
}
///...main() 
sort(arr, arr+N, myfunc);

1. 또다른 방법 : STL 을 적극적으로 활용하면

#include <functional>
sort(arr, arr+N, greater<int>());
sort(arr, arr+N, less<int>());

참고 : plus, minus 라는게 있는데 더해주고 빼주는 것 같다. 기본적으로 int 에 쓸 수 있는데, plus 의 경우 string 에도 적용할 수 있다.

cout << plus<string>()("a", "c") << "\n"; // ac 가 출력 
cout << minus<int>()(1, 1) << "\n"; //string 은 에러를 유발하고, int 는 0이 출력된다.

자료구조 map

map 은 pair 를 동반한다
map 은 중복 key 를 가지지 않는다
set 은 key 하나만 저장하지만, map 은 key, value를 저장한다
map 은 기본적으로 정렬이 되어있다. (key 를 기준으로)

map 의 정렬은?

예를 들어, 문장에서 단어의 빈도 수에 따라서 출력을 하고 싶을 때, value 에 따라서 정렬을 하고 같은 value에 대해서는 key를 기준으로 정렬을 해야한다. 이 부분을 어떻게 해결할 것인가? (NHN 문제)
vector 를 써서 해결을 해야하나? 나의 최선은 vector 에 pair<string, int> 로 저장을 하고 그것을 새로 정의한 비교 함수로 소팅을 했다.

//
//  main.cpp
//  0919nhn_mo2-4
//
//  Created by GaryNoh on 2017. 9. 19..
//  Copyright © 2017년 Macbook. All rights reserved.
//

#include<string>
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;

map<string, int> hashmap;
void toLowerCase(string &str){
    int len = (int)str.length();
    for(int i = 0 ; i < len; i++){
        //소문자로 바꾼다
        if(str[i] >= 'A' && str[i] <= 'Z') str[i]+=32;
    }
}

void parse(string &str, vector<string> &words){
    int len = (int)str.length();
    string word = "";
    for(int i = 0 ; i < len ; i++){
        if(str[i] >= 'a' && str[i] <= 'z') word += str[i];
        else{
            if(word!=""){
                //못찾음
                if(hashmap.find(word) == hashmap.end()) hashmap.insert(pair<string, int> (word, 1));
                else hashmap[word]++;
                word = "";
            }
        }
    }
    //마지막 단어 처리해주기
    if(word != ""){
        if(hashmap.find(word) == hashmap.end()) hashmap.insert(pair<string, int> (word, 1));
        else hashmap[word]++;
    }
}

void readAllLines(vector<string> &words)
{
    words.clear();
    string line;
    while (getline(cin, line))
    {
        toLowerCase(line);
        parse(line, words);
    }
}

auto cmp = [](std::pair<string,int> const & a, std::pair<string,int> const & b)
{
    return a.second != b.second?  a.second > b.second : a.first < b.first;
};


int main(int argc, const char * argv[]) {
    vector<string> words;
    readAllLines(words);
    vector<pair<string, int> > v;
    
    
    for(map<string, int>::iterator it = hashmap.begin(); it != hashmap.end(); ++it){
        v.push_back(*it);
    }
    sort(v.begin(), v.end(), cmp);
    for(int i = 0; i < (int)v.size(); i++){
        cout << v[i].first << " " << v[i].second << "\n";
    }
}

make_pair()

make_pair 는 pair 를 생성해주는 함수이다.

set

set 은 중복되지 않는 key 값 하나를 가지고 이미 정렬되어있는 상태로 저장이 된다.

숫자 거꾸로 저장하기

루프 돌 때마다 new_num 에 10 씩 곱하고 N / 10 의 나머지를 곱해준다

int myreverse(int N){
    int new_num = 0;
    while(N > 0){
        new_num = new_num*10 + (N%10);
        N /= 10;
    }
    return new_num;
}

Array 를 동적으로 할당

char *matrix = new char*[N]();

#include find

vector 에서 원하는 값을 찾고 싶을 때 find 를 쓰면 된다
이 문제를 통해서 find 에 대해서 공부할 수 있었다. Java 에서는 contains 라는 함수가 있다면, cpp 에서는 find(vector.begin(), vector.end(), "value") 를 사용해서 원하는 값을 찾을 수 있다.
find 가 반환하는 값은 iterator 를 반환한다. 이 iterator 는 포인터 타입으로 (1) 값을 출력할 수 있고, (2) 값을 제거할 수 있고, (3) 인덱스를 찾을 수 있다.
값을 출력하기

vector<int>::iterator it;
int find_value = 0;
vector<int> v;
//...
it = find(v.begin(), v.end(), find_value);
//출력/////////////////
cout << *it << "\n";

값을 제거하기

v.erase(it);

인덱스를 출력하기

cout << it - v.begin() << "\n";

자료형의 중요성

이 문제를 풀면서 자료형의 중요성에 대해서 생각해본다!

알고리즘은 기본이다. 알고리즘은 생활이다.