https://www.acmicpc.net/problem/12869 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net 풀이 과정 scv는 최대 3개가 있을 수 있고, scv의 체력은 최대 60이다. 따라서 각 scv의 체력의 조합은 61의 3승이다. 약 20만의 경우의 수가 있으므로, 전부 탐색해도 큰 문제가 없이 풀 수 있다. D[a][b][c] = 체력의 조합이 (a, b, c) 일 때 모두 파괴하는 최소 공격 횟수 총 세 가지 SCV에 대해서 체력을 감소시킬 때는 3!의 경우의 수가 있으므로, 아래와 같이 점화식을 ..
https://www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 마지막곡을 연주할 때 k인 볼륨을 설정하는 것이 가능한지 ? 를 기준으로 문제를 풀 수 있게 다이나믹 프로그래밍 알고리즘을 적용해보았다. dp(n, k) = max(sol(n-1, k - v[n]),sol(n-1, k+v[n])) 코드는 위와 같다. 둘 중에 하나라도 가능하면 dp[n][k], 즉 k 크기의 볼륨으로 n번째 곡을 연주할 수 있으므로 첫 번째 곡..
Map 순회하기 1. iterator 을 이용한 순회 // iterator를 사용하여 순회 for (auto it = myMap.begin(); it != myMap.end(); ++it) { std::cout
스택(stack) #include // 스택 클래스 정의 class Stack { private: static const int MAX_SIZE = 100; // 스택의 최대 크기 int arr[MAX_SIZE]; // 스택을 저장할 배열 int top; // 스택의 가장 위에 있는 요소의 인덱스 public: Stack() : top(-1) {} // 생성자, 스택 초기화 // 스택이 비어있는지 확인 bool isEmpty() { return (top == -1); } // 스택이 가득 찼는지 확인 bool isFull() { return (top == MAX_SIZE - 1); } // 스택에 요소 추가 void push(int value) { if (isFull()) { std::cout
이분 탐색으로 lower_bound 구현하기 lower_bound는 어떤 수보다 크거나 같은 수가 처음 나오는 위치를 의미한다. 반대로, upper_bound는 어떤 수보다 큰 수가 처음 나오는 위치를 의미한다. vector v = {0, 1, 2, 3, 4, 5}; int target = 3; int left = 0, right = v.size() -1 ; while(left
String 부분 문자열 substr https://modoocode.com/235 C++ 레퍼런스 - string 의 substr 함수 modoocode.com basic_string substr(size_type pos = 0, size_type count = npos) const; 첫 번째 인자는 시작 위치, 두 번째 인자는 부분 문자열의 길이를 의미한다. 인자를 하나만 넣게 되면, 자동으로 문자열의 마지막 위치까지 잘라서 리턴하게 된다. 소문자를 대문자로, 대문자를 소문자로 ! Transform 함수 https://artist-developer.tistory.com/28 [C++] transform 함수 안녕하세요. 개발자 김모씨입니다. C, C++ 탭을 새로 만들었습니다~~~~~~ 여기에는 실무..
자료구조를 사용하지 않지만, 수학적 계산을 이용해 구하는 간단하고 다양한 예제들을 정리하려 한다. 양수, 음수에 대한 올림/내림/반올림 https://blockdmask.tistory.com/112 [C언어/C++] 올림, 내림, 반올림 (floor, ceil) 함수 안녕하세요 BlockDMask 입니다. 오늘은 올림, 내림 을 할수있는 ceil, floor 함수에 대해서 알아보고. floor 함수를 통해서 반올림을 하는 것 까지 보도록 하겠습니다. C의 함수들이 C++에 호환이 되어서 C blockdmask.tistory.com 이 분의 글을 참고하였다. 양수, 음수인 경우 사용법은 동일하다. #include #include int main(){ double n = 1.0124; cout
우선순위 큐 우선순위가 가장 높은 자료가 먼저 꺼내진다는 특징이 있다. 이런 큐를 구현하기 위해서는, 모든 원소를 순회하며 우선순위가 가장 높은 원소를 찾는 방법이 있다. 그러나 여기서는 힙이라는 단순한 구조의 이진 트리를 사용해서 새 원소를 추가하고 꺼내는 연산을 O(logN)에 수행한다. 힙 힙의 대소 관계 규칙 부모 노드가 가진 원소는 자식 노드가 가진 원소보다 크거나 같다. 왼쪽/오른쪽 자식에 대한 크기 제약은 없다. 힙의 모양 규칙 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차있어야 한다. 마지막 레벨에 노드가 있을 때는 항상 왼쪽부터 순서대로 채워져 있다. STL priority_queue 사용법 #include priority_queue 변수명; ex) priority_queue pq; p..
비트마스크란 ? 이진수 표현을 자료구조로 쓰는 기법이다. 비트 연산자 a & b : AND 연산 a | b : OR 연산 a ^ b : XOR 연산 ~a : NOT 연산 a > b 정수 a를 오른쪽으로 b비트 Shift 비교 연산자 → 비트 연산자의 우선순위 집합의 구현 int noPizza = 0; // 공집합 int fullPizza = (1
