본문 바로가기

분류 전체보기351

[c++] 문자열을 특정 문자 기준으로 자르기2 getline & stringstream 정석은 아니지만... getline을 사용하면 문자열을 손쉽게 자를 수 있다. getline(&istream is, &string str, char delim) - is는 cin이나 stringstream - str은 자른 문자열 - delim은 기준점이다. 원래 정의대로 라면 delim 문자를 만나면 문자열 추출이 중단된다. 이걸 이용해서 tokenize해보자. 일단 is 자리에 들어갈 stringstream이 필요하다. #include #include #include using namespace std; int main(void){ string s = "This,is,the,test!"; char delim = ' '; stringstream ss(input); string buffer; while(.. 2020. 10. 10.
[leetcode 221] Maximal Square Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area. Example: Input: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 Output: 4 풀이 : 최대 길이를 return 하게 만들자. dp[i][j]는 dp[i][j]를 포함하여 만들 수 있는 최대 정사각형 길이 dp[i-1][j-1]을 중심으로 1 1 자신을 제외한 주변 숫자들이 0이상의 수로 동일하면 +1 1 2 class Solution { public: int maximalSquare(vector& matrix) { int row = matrix.size(); i.. 2020. 10. 8.
[leetcode 300] Longest Increasing Subsequence Given an unsorted array of integers, find the length of longest increasing subsequence. Example: Input: [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. 풀이: -lower bound 사용 - dp는 가장 긴 수열을 저장하는 배열이다. (오름차순) - nums[i]를 dp의 마지막 숫자와 비교해서 nums[i]가 크면 dp에 집어 넣는다. - 작다면 dp배열에서 nums[i] 이상의 숫자의 위치를 찾는다. -> lower bound 사용 lower_boun.. 2020. 10. 8.
[leetcode 279] Perfect Squares Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n. Example 1: Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4. Example 2: Input: n = 13 Output: 2 Explanation: 13 = 4 + 9. 주어진 n을 제곱수의 합으로 표현할 때 가장 적은 숫자의 제곱수 - 풀이: dp[n]은 return값이다. bottom-up으로 update해나간다. dp[i] = i로 초기화하고 i보다 작거나 같은 제곱수를 빼서 값을 update한다. 제곱수는 dp[j*j] = 1 .. 2020. 10. 8.

티스토리툴바