분류 전체보기
-
백준 2293번: 동전 1다이나믹프로그래밍(DP) 2020. 11. 27. 13:49
https://www.acmicpc.net/problem/2293 1. 문제 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. (각각의 동전은 몇 개라도 사용할 수 있다.) 2. 알고리즘 키워드 - 다이나믹 프로그래밍 https://www.youtube.com/watch?v=2IkdAk1Loek #include #include #include using namespace std; #include #include // min #include #include #include #include #include #include #include #define MAX_SIZE 100 int coin[..
-
백준 12847번: 꿀 아르바이트다이나믹프로그래밍(DP) 2020. 11. 27. 12:05
www.acmicpc.net/problem/12847 12847번: 꿀 아르바이트 월세를 내기 바로 전 날 까지 인 n (0 < n ≤ 100,000) 일과 일을 할 수 있는 날 m (0 ≤ m ≤ n) 일이 주어진다. 그 다음 줄 에는 1일부터 n일 까지 일급 Ti가 순서대로 주어진다. (0 < Ti ≤ 1,000,000) www.acmicpc.net #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define MAX_SIZE 100 #define INF 0x7fffffff #define ..
-
백준 11053번: 가장 긴 증가하는 부분 수열다이나믹프로그래밍(DP) 2020. 11. 26. 18:30
https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 히스토리 2020-03-22 ..
-
백준 1932번: 정수 삼각형다이나믹프로그래밍(DP) 2020. 11. 26. 18:30
https://www.acmicpc.net/problem/1932 키워드 - 다이나믹프로그래밍, 구현 #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define MAX_SIZE 100 #define INF 0x7fffffff #define CENDL "\n" #define ll long long #define c_reverse(s) reverse(s.begin(), s.end()) #define c_sort(s) sort(s.begin(), s.end()) #define print_vect..
-
LEETCODE - 1415. The k-th Lexicographical String of All Happy Strings of Length n릿코드(LEETCODE) 2020. 6. 7. 20:27
https://leetcode.com/problems/the-k-th-lexicographical-string-of-all-happy-strings-of-length-n/ consists only of letters of the set ['a', 'b', 'c']. 문자열 배열에 a b c 세개의 문자가 있고 입력으로 들어오는 n 은 문자열의 길이 k 는 n 길이 만큼이 조합으로 만들어진 무자열 배열의 크기를 뜻 한다. (아아~ 한국말 어렵다) 문제의 조건에서 s[i] != s[i + 1] for all values of i from 1 to s.length - 1 (string is 1-indexed). 이전의 글자는 그 다음 글자와 같을 수 없다. 만약 N 이 2일때 a,b,c 의 조합 문자는{aa,..
-
LEETCODE - 1461. Check If a String Contains All Binary Codes of Size K릿코드(LEETCODE) 2020. 6. 7. 20:17
https://leetcode.com/problems/check-if-a-string-contains-all-binary-codes-of-size-k/ 해당문제는 k 개의 이진 문자를 만드는 것이 키포인트이다. k의 값이 2 일때 2^2 임으로 총 4개의 이진 문자를 만들 수 있다. k의 값이 1 일때 2^1 = 2 class Solution { public: bool hasAllCodes(string s, int k) { if (k > s.length()) return false; unordered_mapmp; for (int i = 0; i < s.length()-k+1; i++) mp[s.substr(i, k)]++; return mp.size() == pow(2, k); } }; 모두다 만들고 k..
-
LEETCODE - 1089. Duplicate Zeros릿코드(LEETCODE) 2020. 6. 7. 20:09
https://leetcode.com/problems/duplicate-zeros/ vector int 어레이에 원소의 값이 0 이면 한칸식 0으로 채우주고 shift 하는 문제 1101 -> 1100 12012001 -> 12001200 class Solution { public: void duplicateZeros(vector& arr) { // 임시 vector int 를 만들고 0 이면 한번더 넣어 준다. // 괜히 머리아프게 shift 하지 말자 쉽게 풀리면 쉽게 풀리는 방법으로 풀자 vector tmp; for (int i = 0; i < arr.size(); i++) { int value = arr[i]; tmp.push_back(value); if (value == 0) { tmp.push..
-
LEETCODE - 1470. Shuffle the Array릿코드(LEETCODE) 2020. 6. 7. 19:38
https://leetcode.com/problems/shuffle-the-array/ 어레이에 있는 요소를 shuffle 하는 문제 입력으로 들어오는 인자 n 위치와 current 위치에 넣어 주면 된다. class Solution { public: vector shuffle(vector& nums, int n) { vector arr; const int size = nums.size(); for(int i=0; i