C++ 기반 PS 스터디 시작
PS, 시간복잡도, 정렬알고리즘, 이분탐색
#include<algorithm> ; #include<vector> ; vector<int>vec ; vector<pair<int, int>>vec ; 이진탐섹(Binary Search) ; 부동소수점 오차
재귀호출: 종료조건, 사이클X, 종료조건과 가까워지는 방향으로 설계 ; 순열: std::next_permutation(begin, end)
nPm 출력 ; next_permutation(nums.begin(), nums.end()) ; reverse(nums.begin() + m, nums.end())
prev_permutation(check.begin(), check.end()) ; 2^n 하고 싶을 때: 1 << n
vector 최대값/최소값 : *max_element(v.begin(), v.end()) ; *min_element(v.begin(), v.end())
벡터의 멤버함수: v.front(), v.back(), v.begin(), v.end(), v.size() ; 벡터 2차원 배열 입력받기
에라토스테네스의 체 - 소수 찾기 문제
소인수분해 문제 - 시간초과 잡는 과정이 오래 걸림
유클리드 호제법: 나눗셈 연산 만을 통해서 최대공약수, 최소공배수를 구할 수 있음. GCD(a,b) == GCD(b, a%b) ; 최대공약수&최소공배수: a * b == GCD(a,b) * LCM(a,b)
동적 계획법: 복잡한 문제를 간단한 문제들로 나누고, 간단한 문제들을 해결한 뒤, 간단한 문제들의 답을 이용해 복잡한 문제의 답을 구함 ; 최적 부분 구조: 큰 문제의 최적해가 작은 문제의 최적해를 포함 ; 중복되는 부분 문제: 작은 문제의 답을 여러 번 참조
동적 계획법
그리디로 푸는 문제
수학적 귀납법: 자연수에 대한 명제 P(n)이 모든 자연수에 대해 성립함을 증명 ; 분할 정복(Divide And Conquer): 큰 문제를 여러 개의 작은 문제로 쪼갠 다음(분할), 작은 문제들의 답을 이용해 큰 문제의 답을 구함(정복)
C++ 표준 라이브러리 및 멤버 함수 - 스택, 큐, 덱
그래프 표현 방식: 인접 행렬, 인접 리스트, 간선 리스트 ; DFS: stack, 재귀 ; BFS: queue
그리디: 현재 상태에서 가장 좋은 선택을 하는 방법 ; 최소 동전 개수 문제, 가방 문제