본문 바로가기

알고리즘55

백준 1106 호텔 C++ 2차원 dp로 할려다가, 기존의 배낭문제처럼 최댓값을 이어서 받는 것은 고객 수의 idx가 배수가 아닐 경우, 문제가 생겨서 1차원 dp로 해결하였다. 주석을 상세히 다시 달아보았다. 적어도 c명 이상이므로, 도시당 고객의 수가 최대 100명이다. 그러므로 c+100 명 이상까지 계산해야 한다. 반례 100 3 7 12 20 30 30 60답 : 57 답 #include #include #include using namespace std; int main(){ cin.tie(0); ios_base::sync_with_stdio(0); int c,n; cin>>c>>n; vector v(n); // 고객 수, 비용 for(int i=0;i>v[i].second>>v[i].first; } sort(v.beg.. 2024. 4. 15.
페르마의 소정리 c++ 수식 글자 깨지니까 github에서 보는 것을 추천 https://github.com/ash9river/algorithm/blob/main/%ED%8E%98%EB%A5%B4%EB%A7%88%EC%9D%98_%EC%86%8C%EC%A0%95%EB%A6%AC/readme.md 모듈러 연산 성질 $$ (a+b)\ mod\ M =((a\ mod\ M)+(b\ mod\ M))\ mod\ M $$ $$ (a-b)\ mod\ M =((a\ mod\ M)-(b\ mod\ M))\ mod\ M $$ 이 때, $a>b$ , $a\ mod \ M < b\ mod\ M$ 인 경우에는 음수로 반환할 수 있어서, 코딩할때는 M을 추가로 더해줄 수도 있다. $$ (a-b)\ mod\ M =((a\ mod\ M)-(b\ mod\ M.. 2024. 4. 9.
오일러 피함수(오일러 토션트 함수) c++ 글자 깨지니까 그냥 깃허브에서 보세요... https://github.com/ash9river/algorithm/tree/main/math/%EC%95%BD%EC%88%98%20%EA%B4%80%EB%A0%A8 오일러 피함수 오일러 토션트 함수라고도 불린다. 자연수 $n$과 $n$보다 작은 자연수 $x$에 대하여 $gcd(x,n)=1$인 $x$들의 수를 구하는 방법 $$ \phi (n) = \phi \left( \prod_{i=1}^r p_{i}^{k_{i}} \right) = \prod_{i=1}^r \phi ( p_{i}^{k_{i}} ) = \prod_{i=1}^r { \left[ p_{i}^{k_{i}} \left( 1 - \frac{1}{p_{i}} \right) \right] } $$ $10^.. 2024. 4. 9.
C++ 문제 해결을 위한 STL 야매 정복 - set, map 은근히 중요한 set과 map 해시를 사용하고 싶으면 unordered_set, unordered_map 사용 BBST를 사용하고 싶으면 set, multiset, map, multimap 사용 set #include 그냥 집합 set s; //선언 s.insert(3); //삽입 // set 순회 for(auto it=s.begin();it!=s.end();++it){ cout 2024. 4. 9.
C++ 문제 해결을 위한 STL 야매 정복 - stack, queue 그리고 deque stack #include FILO 스택은 사실 스택을 활용해야하는 문제가 아니면, 다른 문제들에서 활용도가 높지 않은 것 같다. dfs할 때, 쓰긴 하나 재귀로 하는 게 더 가독성이 좋으면서 편하고, 굳이 말한다면 SCC정도...? 게다가 C++에서는 vector, deque, list를 기반으로 내부적으로 구현하는데, 기본적으로 deque를 이용하여 구현이 되기 때문에, 생각보다 메모리를 더 잡아먹을 수 있다. stack s; s.push(3); cout 2024. 4. 9.
C++ 문제 해결을 위한 STL 야매 정복 - vector와 pair, tuple 알아야 할 것 vector, pair, tuple, list, queue, priority_queue, map, set ,stack, deque array는 vector가 있어서 잘 안쓰는 경향이... Vector 동적 배열 할당하는데 편하다. vector의 초기화 #include vector v1; //1차원 배열 생성 vector v1_init(10,987654321); //1차원 배열 [10]생성, 각 배열의 원소를 987654321로 초기화 vector v2; //2차원 배열 생성 vector v2_init(10,vector(11,987654321)); // [10][11] 생성, 987654321로 초기화 v1[9]=987654321; v2_init[3][4]=145; //원소 접근은 배열처럼 .. 2024. 4. 9.

티스토리툴바