알고리즘 문제

DP

DFS, DP

백트래킹, 브루트포스 알고리즘

DP

DFS

DFS, BFS, 그래프

DP - 테이블을 역으로 채워가는 발상

이분 탐색으로 가방의 수를 줄여가면서 각 사탕의 종류 나누기 가방 수를 검사하는 로직

중복을 허용하지 않는 key와 value 쌍으로 이루어진 map 라이브러리

배울 점 algorithm 라이브러리의 unique 함수 vactor 배열에서 중복되지 않는 원소들을 앞에서부터 채워나가는 함수 중복되어 밀리게 된 원소의 시작부분의 주소를 return 중복되는 값은 인접해 있어야 제거됨 이 문제는 이미 인접해 있으므로 정렬할 필요가

에라토스테네스의 체

배울 점 vector는 deep copy가 가능하므로 간단하게 대입만으로 복사 가능

배울 점 A~Z의 배열 vector 대신 map<char, int>를 활용 MBTI 순서를 위한 vector 대신 2차원배열 활용 코드가 깔끔해지는 효과를 볼 수 있음

배울 점 에라토스테네스의 체를 활용하여 사전에 미리 기록

배울 점 algorithm 라이브러리의 max_element 함수 최댓값을 찾기 위한 pStack 스택이 필요가 없어짐 코드가 깔끔해짐 But, 시간복잡도에서는 stack 사용이 더 빠를 것으로 예상됨

배울 점 algorith 라이브러리의 sort 함수 string 배열을 대상으로 정렬을 실행하면 사전 순으로 정렬된다.

배울 점 max, min 함수로 if문을 대체할 수 있다 -> 깔끔해짐 But, 실행속도는 같을 것으로 예상

unordered_set 사용 방법은 set과 같음 set과 다르게 정렬되지 않으며 해시 함수를 사용하여 원소를 탐색한다.

배울 점 C, C++은 Python의 split 메소드와 같은 기능의 메소드가 없기 때문에 사용자 정의 split 함수를 정의하여 사용한다. 따라서 split 함수 로직을 외워놓는 것이 좋다.

배울 점 string 헤더의 stoll 함수 string을 받아 long long 정수형으로 반환 받은 string이 정수형으로 변환 불가능하면 core dump 오류 발생! 따라서 try catch문이나 별도의 처리가 필요함

배울 점 비트 연산을 활용하여 홀,짝수를 빠르게 구분할 수 있다 짝수 : 1bit -> 0 홀수 : 1bit -> 1

배울 점 long long 자료형을 제곱하는 cmath 라이브러리의 powl 함수로 간단하게 구현 가능

## 배울 점 기존 split 함수 정의를 바꾸어서 빠르게 활용 > algorithm 헤더의 max,min_element 함수

배울 점 > 두 수 사이의 정수를 더하는 시그마 공식

배울 점 내적 numeric 헤더의 inner_product 함수 T inner_product( InputIt1 first1, InputIt1 last1,InputIt2 first2, T init );

배울 점 less<T>(), greater<T>() // 자료형에 따라 대소 비교한 bool return

배울 점 Long Long 빠르게 변환 > `1LL` : Long Long 1을 간단하게 표현 가능 1부터 n까지의 합 > `1+2+3+...+n-1+n` : n*(n+1) / 2

배울 점 > `<algorithm>` 헤더의 **sort**함수를 `sort(B.rbegin(), B.rend())`으로 정렬하면 내림차순으로 정렬 > `<numeric>` 헤더의 **inner_prouct** 함수로 내적 계산 간편화

cin, getc 등과 같은 입력 방식으로는 공백이 있는 문자열 입력 불가 > `getline` - 공백이 있는 문자열 한 줄 입력 ex) `getline(cin, string)`

다음과 같이 역방향 `iterator`를 써서 인덱스 위치를 구하고자 할 때는 `rend()` 값을 기준으로 빼줘야 함

string 라이브러리의 stoi() 함수

algorithm 라이브러리의 swap() 함수

algorithm 라이브러리의 greater<int>()

utility 라이브러리의 pair & sort() default 정렬 함수

vector 중복 원소 제거 방법 : sort & unique & erase

algorithm 라이브러리의 stable_sort() 함수

불필요한 소수 검사 필요 없이 2부터 나머지가 0이 되는 동안만 반복해 주면 됨

algorithm 라이브러리의 이진 탐색 lower_bound & upper_bound

DP, LIS

이분탐색

이분탐색

이분탐색

정렬

이분탐색

greedy

문자열 split, 구현, hash, 이분탐색

greedy

조합, DP

greedy

greedy

구현, 순열 & 조합