this.code();

※ 리스트

리스트는 다른 언어의 배열과 같은 역할을 하며 다음과 같이 사용한다.

리스트형 변수 = [요소1, 요소2, ... ]

a = [1, 2, ['a', 'b', ['Life', 'is']]]

print(a[-1][-1][0])
print(a[2][2][0])

#--------출력--------#
# 둘 다 Life가 출력됨

※ 리스트 슬라이싱(slicing)

문자열 슬라이싱과 동일한 방법으로 진행된다.

a = [1, 2, 3, 4, 5]

print(a[1:3])   #출력: [2, 3]

※ 리스트 연산

§ 리스트 덧셈

a = [1, 2, 3]
b = [4, 5, 6]

print(a+b)

#--------출력--------#
[1, 2, 3, 4, 5, 6]

리스트는 같은 자료형의 집합이기에 다른 리스트간의 덧셈을 위해서는 형변환이 필요하다.

이때, str함수는 정수,실수를 문자열형태로 바꿔주는 내장함수이다.

a = [1, 2, 3]

print(str(a[2]) + "hi")   # 3hi

§ 리스트 반복

a = [1, 2, 3]

print(a*3)

#--------출력--------#
[1, 2, 3, 1, 2, 3, 1, 2, 3]

§ 리스트 길이(len)

a = [1, 2, 3]

print(len(a))   # 3출력

§ 리스트 수정과 삭제(del)

a = [1, 2, 3]

a[2]=4
print(a)    #출력: [1, 2, 4]

del a[1]
print(a)    #출력: [1, 4]

arr = [1,2,3,4,5]
del arr[2:]
print(arr)  #출력: [1, 2]

§ 리스트 복사

a = [1,2,3]
b = a

print(id(a))
print(id(b))

#-----출력-----#
2423373358208
2423373358208

a와 b의 값이 동일함을 알 수 있는데, 이를 아래와 같이 알 수 있다.

a = [1,2,3]
b = a

print(a is b)   # True

따라서 a객체와 b객체가 동일한 주소값을 갖고 있음을 알 수 있기에

아래와 같은 양상이 일어날 수 있다.

a = [1,2,3]
b = a

a[1] = 4
print(a)    # [1, 4, 3]
print(b)    # [1, 4, 3]

그렇다면 a값을 가져오지만 a와 다른 주소를 가리키도록 할 수는 없을까?

1. slicing 이용

a = [1,2,3]
b = a[:]

a[1] = 4

print(a)    # [1, 4, 3]
print(b)    # [1, 2, 3]

2. copy()함수나 copy를 import하여 사용 

a = [1,2,3]
b = a.copy()

a[1] = 4

print(a)    # [1, 4, 3]
print(b)    # [1, 2, 3]

from copy import copy

a = [1,2,3]
b = copy(a)

a[1] = 4

print(a)    # [1, 4, 3]
print(b)    # [1, 2, 3]

※ 리스트 관련 함수(append, sort, reverse, index, insert, remove, pop, count, extend)

§ 리스트 요소 추가 (append)

a = [1, 2, 3]

a.append(4)
print(a)    # [1, 2, 3, 4] 출력

a.append([5, 6])
print(a)    # [1, 2, 3, 4, [5, 6]] 출력

§ 리스트 정렬과 뒤집기 (sort ,reverse)

a = [1, 4, 3, 2]

a.sort()
print(a)    # [1, 2, 3, 4] 출력

a = [1, 4, 3, 2]

a.reverse()
print(a)    # [2, 3, 4, 1] 출력

§ 리스트 위치반환 (index)

a = [1, 4, 3, 2]

print(a.index(4))    # 1출력

§ 리스트 요소 삽입 ( insert(i, x) )

insert(i, x)는 i번째에 x를 삽입하는 함수이다.

a = [1, 4, 3, 2]
a.insert(4, 5)

print(a)    # [1, 4, 3, 2, 5] 출력

§ 리스트 요소 삭제 (remove)

첫 번째로 나오는 값을 삭제

a = [1, 2, 3, 1, 2, 3]
a.remove(2)

print(a)    # [1, 3, 1, 2, 3] 출력

§ 리스트 요소 끄집어내기 (pop)

리스트 마지막 값을 pop(출력 후 삭제)

pop(i)로 i번째 index를 출력 후 삭제

a = [1, 2, 3, 1, 2, 3]

a.pop()
print(a)         # [1, 2, 3, 1, 2] 출력

print(a.pop(2))  # 3출력
print(a)         # [1, 2, 1, 2] 출력

§ 리스트에 포함된 요소x 개수 세기 ( count (x) )

a = [1, 2, 3, 1, 1, 1]

print(a.count(1))   # 4출력

§ 리스트 확장 (extend(리스트))

a.extend(x)에서는 x값은 리스트만 올 수 있으며 원래 리스트 a에 x를 더한다.

a = [1, 2, 3]
b = [4, 5]

a.extend(b)
a.extend([6, 7])
print(a)   # [1, 2, 3, 4, 5, 6, 7] 출력

※ 튜플

리스트와 몇가지를 제외하면 거의 비슷하다.

<리스트와 다른점>

- 리스트는 [ ]이고 튜플은 ( )이며 (생략가능) 한 개의 요소만 가질 때는 쉼표가 필요하다.

- 리스트는 값의 생성, 삭제, 수정이 가능

- 튜플은 위와 같은 값의 변경이 불가능하다.

따라서 이런 값의 불변성 때문에 평균적으로는 리스트를 더 많이 사용한다.

리스트형 변수 = [요소1, 요소2, ... ]

a = [1, 2, ['a', 'b', ['Life', 'is']]]

print(a[-1][-1][0])
print(a[2][2][0])

#--------출력--------#
# 둘 다 Life가 출력됨

※ 튜플의 인덱싱과 슬라이싱(slicing)

a = (1, 2, 'a', 'b')

print(a[0])     # 1출력
print(a[0:3])   # (1, 2, 'a') 출력

※ 튜플의 덧셈, 곱셈, 길이구하기

t1 = (1, 2, 'a', 'b')
t2 = (3, 4)

print(t1+t2)    # (1, 2, 'a', 'b', 3, 4)
print(t2 * 3)   # (3, 4, 3, 4, 3, 4)
print(len(t1))  # 4 출력

※ unique 함수

- 벡터에서 중복원소를 제거할 때, sort, erase, unique 기능을 적절히 활용하여 제거할 수 있기에

 unique 함수의 사용은 익혀야 할 필요성이 두드러진다 생각한다. 

- 또한 int가 아닌 char형도 가능하다는 점에서 대단히 유용하다.

cf. 만약, sort하지말고 중복원소를 제거하라면 set + assign함수를 사용한다.

(set은 중복 원소를 허용하지 않는 컨테이너기 때문이다.)

https://scarlettb.tistory.com/70

[백준 13915번: https://www.acmicpc.net/problem/13915]

§ unique의 원리

- "정렬된" 원소에 대해 vector의 제일 뒷부분으로 쓰레기값으로 보내버린다.

- 따라서 "정렬"되어야 하므로 sort를 사용해야한다.

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

int main() {
    int N;  cin >> N;
    vector<int> v;
    for(int i = 0; i < N; i++){
        int num;    cin >> num;
        v.push_back(num);
    }

    sort(v.begin(), v.end());

    unique(v.begin(), v.end());

    for(auto x:v)
        cout << x << " ";
}

input >>  1 4 3 2 2 3 1 5 3 5 4
output << 1 2 3 4 5 3 3 4 5 5

앞에 1 2 3 4 5가 정렬된 이후 뒤 숫자는 아무렇게나 쓰레기값이 들어간 것을 알 수 있다.

§  중복원소제거 정렬

따라서 정렬 후 erase와 unique로 삭제할 수 있다.

다음과 같이 작성하면 된다.

sort(v.begin(), v.end());
v.erase( unique(v.begin(), v.end()), v.end() );

※ 중복된 원소 제거 => sort, erase(unique())

[백준 10867번: https://www.acmicpc.net/problem/10867]

[숫자벡터에 대한 중복 원소 제거]

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

int main() {
    int N;  cin >> N;
    vector<int> v;
    for(int i = 0; i < N; i++){
        int num;    cin >> num;
        v.push_back(num);
    }

    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    for(auto x:v)
        cout << x << " ";
}

[문자벡터에 대한 중복 원소 제거]

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

int main() {
    vector<char> s;
    for (int i = 0; i < 10; i++) {
        char c;     cin >> c;
        s.push_back(c);
    }
    sort(s.begin(), s.end());
    s.erase(unique(s.begin(), s.end()), s.end());

    for(auto x:s)
        cout << x << " ";
}

vector / pair / stack ,queue, deque, priority queue / map / set  / algorithm / iterator / bitset

※ vector(std::vector) _가변배열 / 가장 기본이 되는 컨테이너 (★★★★★)

#include <vector>
using namespace std;

vector<자료형> 변수명(숫자)    //숫자만큼 벡터 생성 후 0으로 초기화
vector<자료형> 변수명(숫자, 변수1);   //숫자만큼 벡터 생성 후 변수1으로 모든 원소 초기화
vector<자료형> 변수명{숫자, 변수1, 변수2, 변수3, ...};    // 벡터 생성 후 오른쪽 변수 값으로 초기화
vector<자료형> 변수명[]={ {변수1, 변수2}, {변수3, 변수4}, ...}   //2차원 벡터생성 (열은 고정, 행 가변)
vector<vector <자료형>> 변수명   //2차원 벡터생성 (열, 행 가변)

ex);
vector<int> vec1; // 크기가 0인 벡터 선언
vector<int> vec2(10); // 크기가 10인 벡터 선언
vector<int> vec3(10, 3); // 크기가 10이고 모든 원소가 3으로 초기화된 벡터
vector<int> vec4 = { 1,2,3,4,5 }; // 크기가 지정한 초기값으로 이루어진 벡터
vector<int> vec5[] = { {1,2},{3,4} }; // 벡터 배열 생성(행은 가변인지만, 열은 고정)
vector<vector<int>> vec6; // 2차원 벡터 생성(행과 열 모두 가변)

※ vector 요소 삽입, 제거, 변경

#include <vector>
using namespace std;

int main() {
    vector<int> vec; // 크기가 0인 벡터 선언

    vec.push_back(10);
    vec.push_back(20); // vec = {10, 20}

    vec.insert(vec.begin() + 1, 100);  // vec = {10, 100, 20}

    vec.pop_back();       // vec = {10,100}

    vec.emplace_back(1);   // vec = {10, 100, 1}
    vec.emplace_back(2);   // vec = {10, 100, 1, 2}
    vec.emplace(vec.begin() + 2, -50); // vec = {10, 100, -50, 1, 2}

    vec.erase(vec.begin() + 1);    // vec = {1, -50, 1, 2}
    vec.resize(6); // vec = {1, -50, 1, 2, 0, 0}
    vec.clear();   // vec = empty()
}

※ vector의 index 접근

※ vec.at(i)와 vec.[i]의 차이점

- at은 범위를 검사하여 범위 밖의 요소에 접근 시 예외처리를 발생시킨다. (std::out_of_range)

- [ ]은 범위검사를 하지 않으며 예외처리를 발생시키지 않는다. (범위 밖 요소에 접근하면 디버깅 발생)

vector는 효율에 중점을 두기에 보통 [ ]를 권장한다.

※ vector의 크기 size, capacity

- size: vector의 크기, 즉 벡터에 실제로 저장된 원소의 개수를 뜻한다.

- capacity: vector의 용량, 즉 벡터의 최대 할당 크기를 뜻한다.

만약 벡터의 크기가 용량을 초과한다면 재할당이 발생한다. (기존 값 새 메모리에 복사 후 파괴)

if (size > capacity) {
    reallocate <- 모든 값 새 메모리에 복사 후 기존 벡터 파괴
}

Problem 1. 새 메모리의 복사과정에서 복사생성자가 발생해 성능이 저하될 수 있다.

Solution 1. reserve()라는 함수를 사용해서 벡터의 용량을 충분히 크게 생성할 수 있다.

Problem 2. reserve()를 너무 크게 잡으면 벡터가 불필요하게 늘어나 메모리를 많이 차지할 수 있다.

Solution 2. clear()로 벡터의 값을 지울 때, 벡터의 요소를 삭제할 수 있다.

Problem 3. clear()로 벡터의 요소는 없어지지만 capacity는 그대로 남아있다.

Solution 3. 이를 해결하기 위해 swap()을 사용하는데 이는 아래와 같다.

#include <vector>
using namespace std;

int main() {
    vector<int> vec = { 1,2,3,4,5 };
    vec.clear();
    cout << vec.capacity() << endl;  // 5 출력
    vector<int>().swap(vec);
    cout << vec.capacity() << endl;  // 0 출력
}

https://chan4im.tistory.com/19?category=1076581 

★★★★★ vector에 값 입력받기  (cin >> vec[i]는 안된다??) ★★★★★

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

vector<int> v;

int main() {
    int num;
    for (int i = 0; i < 5; i++){
        //cin >> v[i];  // Err!
        cin >> num;
        v.push_back(num);
    }
    vector<int>::iterator it;
    sort(v.begin(), v.end(), greater<int>());

    for (it = v.begin(); it != v.end(); it++){
        cout << *it << ' ';
    }
}

※ pair

★★★개인적으로 굉장히 유용하다고 생각되는 라이브러리★★★

feat. vector, sort

• 두 자료형을 하나의 쌍(pair)으로 묶는다.
• 첫번째 데이터는 first, 두번째 데이터는 second로 접근, make_pair(val1, val2)로 pair를 생성해준다.
• vector, algorithm 의 헤더파일에 include 하고 있기에 별도의 헤더를 include할 필요가 없다.

#include <iostream>
using namespace std;

#include <vector>

int main(){
    pair<int, int> p1;
    cout << p1.first << ' ' << p1.second << endl; // 0 0 출력

    p1 = make_pair(1, 2);
    cout << p1.first << ' ' << p1.second << endl; // 1 2 출력

    pair<pair<int, int>, pair<int, int>> p2 = make_pair(make_pair(1, 2), make_pair(3, 4));

    cout << p2.first.first << ' ' << p2.first.second << endl;   // 1 2 출력
    cout << p2.second.first << ' ' << p2.second.second << endl; // 3 4 출력
}

pair로  vector, typedef, sort  다루기

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

using namespace std;

int main(){
    pair<int, int> p1;
    cout << p1.first << ' ' << p1.second << endl; // 0 0 출력

    p1 = make_pair(1, 2);
    cout << p1.first << ' ' << p1.second << endl; // 1 2 출력

    pair<pair<int, int>, pair<int, int>> p2 = make_pair(make_pair(1, 2), make_pair(3, 4));

    cout << p2.first.first << ' ' << p2.first.second << endl;   // 1 2 출력
    cout << p2.second.first << ' ' << p2.second.second << endl; // 3 4 출력

    //vector와 pair
    vector<pair<int, int>> v;
    v.push_back(make_pair(10, 20));
    v.push_back(make_pair(30, 40));
    v.push_back(make_pair(50, 60));
    cout << v[0].first << ' ' << v[2].second << endl;

    // typedef를 이용한 방식
    typedef pair<int, int> P;
    vector<P> v1;
    v1.push_back(make_pair(300, 500));
    v1.push_back(make_pair(600, 400));
    v1.push_back(make_pair(100, 200));

    // first 따로, second 따로 정렬
    sort(v1.begin(), v1.end());
    vector<P>::iterator it;

    for (int i = 0; i < 3; i++)
        cout << v1[i].first << " " << v1[i].second << endl;
}

※ stack

#include <stack>

stack<데이터타입> 이름;

https://chan4im.tistory.com/22?category=1076581 

※ stack, queue, deque priority queue, priority queue

※ queue 선언방식

#include <queue>

queue<데이터타입> 이름;

※ deque 선언방식

#include <deque>

deque<데이터타입> 이름;

https://chan4im.tistory.com/29?category=1076581 

※ priority queue 선언방식

#include <queue>

priority_queue<int> pq;
priority_queue<int, vector<int>, greater<int> > pq;
priority_queue<int, vector<int>, less<int> > pq;

가장 기본적인 것 부터 시작해 여러 방식으로 변형하며 사용할 수 있다.

※ map

map은 각 node가 [key - value] 의 쌍(pair)으로 이루어진 트리이다. 

특히나 map의 가장 큰 특징은 중복을 허용하지 않는다는 것이다! => key가 중복되면 insert가 수행되지 않음

C++의 map 내부구현은 삽입, 삭제, 검색의 시간복잡도가 O(logn) 인 레드블랙트리로 구성되어 있다.

unordered_map은 해시 테이블이다.

※ map 선언방식 (삭제)

#include <map>

map<key_type, value_type> 이름;

※ map 삭제

※ map에서 찾고자 하는 데이터 확인 (search, find)

map에서 원하는 값을 찾고자 할 때, iterator를 사용한다.

만약 끝까지 원하는 값을 찾지 못하면, iterator는 map.end()를 반환한다.

find(k) 로 사용하며 key값 k에 해당하는 iterator를 반환한다.

map<string, int> mapset;

if (mapset.find("V2LLAIN") != mapset.end()){
    cout << "find!" << endl;
}
else
    cout << "not find!" << endl;

※ 반복문 데이터 접근 (first, second)

※ index 기반 iterator 활용 예제

map<string, int> mapset;

for (auto it = mapset.begin(); it != mapset.end(); it++) {
    cout << it->first << " " << it->second << endl;
}
cout << endl;

※ 범위기반 반복문 활용 예제

map<string, int> mapset;

for (auto it : mapset){
    cout << it.first << " " << it.second << endl;
}

※  map 사용 예제 (insert, search, iterator 구현)

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

map<string, int> mapset;

int main() {

    mapset.insert({ "Alice", 100 });
    mapset.insert({ "Bob", 200 });

    if (mapset.find("Alice") != mapset.end())
    {
        cout << "find" << endl;
    }
    else {
        cout << "not find" << endl;
    }

    //인덱스기반
    for (auto iter = mapset.begin() ; iter !=  mapset.end(); iter++)
    {
        cout << iter->first << " " << iter->second << endl;
    }
    cout << endl;

    //범위기반
    for (auto iter : mapset) {
        cout << iter.first << " " << iter.second << endl;
    }
}

참고) https://life-with-coding.tistory.com/305?category=808106

※ set

- set은 연관 컨테이너로 삽입, 삭제, 검색의 시간복잡도가 O(logn) 인 Binary Search Tree로 구현되어 있다.

- key라는 원소들의 "집합"으로 key값은 중복되지 않는다!

- insert()를 통한  자동적으로 오름차순 정렬이 가능하다.

∴ 중복을 피하면서 정렬까지 사용할 때 매우 유용하다!

insert(k) : 원소 k 삽입
begin() : 맨 첫번째 원소를 가리키는 iterator를 반환
end() : 맨 마지막 원소를 가리키는 iterator를 반환
find(k) : 원소 k를 가리키는 iterator를 반환
size() : set의 원소 수
empty() : 비어있는지 확인

※ algorithm

※ STL 알고리즘의 분류

find()는 2개의 입력 반복자로 지정된 범위에서 특정 값을 가지는 첫 번째 요소를 가리키는 입력 반복자를 반환 

for_each()는 2개의 입력 반복자로 지정된 범위의 모든 요소를 함수 객체에 대입한 후, 대입한 함수 객체를 반환 

copy()는 2개의 입력 반복자로 지정된 범위의 모든 요소를 출력 반복자가 가리키는 위치에 복사

swap()은 2개의 참조가 가리키는 위치의 값을 서로 교환

transform()은 2개의 입력 반복자로 지정된 범위의 모든 요소를 함수 객체에 대입후, 출력 반복자가 가리키는 위치에 복사

sort()는 2개의 임의 접근 반복자로 지정된 범위의 모든 요소를 비교, 오름차순정렬.

stable_sort()는 2개의 임의 접근 반복자로 지정된 범위의 모든 요소를 비교, 값이 같은 요소들의 상대적인 순서는 유지,  오름차순으로 정렬합니다.

binary_sort()는 정렬되어있는 경우(오름차순)에 한해서 탐색효율이 매우 좋고 적은 시간에 소요된다.

accumulate()는 두 개의 입력 반복자로 지정된 범위의 모든 요소의 합을 반환합니다.

※ 벡터의 오름차순과 내림차순 정렬 (feat. greater<int> 키워드)

§ sort() 함수 형식

단, custom_func()은 0 또는 1이 나오도록 해야해서 보통 bool형 함수를 많이 넣는다.

sort(v.begin(), v.end()); //형식이나
sort(v.begin(), v.end(), custom_func); //형식으로 사용가능하다.

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


int main() {
    vector<int> v;
    for (int i = 0; i < 5; i++) {
        int num; cin >> num;
        v.push_back(num);
    }
    sort(v.begin(), v.end());   // 오름차순
    sort(v.rbegin(), v.rend()); // 내림차순

    for (auto x: v) {
        cout << x;
    }
}

※ 벡터의 이진탐색 

※ iterator

STL에 저장된 요소를 반복적으로 순회해여 각각의 요소에 대한 접근을 제공하는 객체.

즉, 컨테이너의 구조,요소의 타입과 상관없이 컨테이너에 "저장된 요소"를 순회하는 과정을 일반화한 표현

[iterator를 쓰기 위한 요건]

1. 가리키는 요소의 값에 접근할 수 있어야 한다. => 참조 연산자(*)가 정의되어야 합니다.

2. 반복자 사이의 대입 연산, 비교 연산이 가능해야 합니다. => 대입, 관계 연산자가 정의되어야 합니다.

3. 가리키는 요소의 주변 요소로 이동할 수 있어야 합니다. => 증가 연산자(++)가 정의되어야 합니다.

int main() {
    vector<int> v(5);

    v.push_back(20);
    v.push_back(50);
    v.push_back(10);

    for (int i = 0; i < 5; i++)
        cin >> v[i];

    vector<int>::iterator it;
    for (it = v.begin(); it != v.end(); it++) {
        cout << *it << ' ';
    }
    
    //1 2 3 4 5 20 50 10 출력
}

※ bitset

비트연산의 간편화를 위해 사용하는 라이브러리

#include <bitset>

int main() {
    bitset<100000> a(76),b(44); // 각각 76, 44의 비트가 입력됨
    cout << (a & b) << '\n';
    cout << (a | b) << '\n';
    cout << (a ^ b) << '\n';
    cout << (~a) << '\n';
    cout << (~b) << '\n';
    return 0;
}