GetComponent<('0')>

요약재귀 + dp풀이과정시간복잡도를 보기위해 최악의 경우를 본다면 숫자 2000, 질문 100만이며 0.5초를 요구한다.숫자 2000 기준으로 본다면 O(n^2)는 가능한 범위에 들어온다.즉 2중 반복문으로 모든 숫자에 대해 팰린드롬인지 아닌지를 확인하고 이를 저장한다면이후 무슨 질문이 나오던지간에 O(1)으로 팰린드롬 여부를 확인할 수 있기 때문에 위배되지 않을 것이다. 모든 숫자의 조합에 접근하는 순간 O(n^2)를 충족하기 때문에범위에 대한 펠린드롬 파악 방법은 무조건 O(1)이어야 함.이는 팰린드롬의 특성을 고려하면 쉽게 해결가능하다. 일단 dp[n+1][n+1](1부터 시작하니까..)에 저장한다고 치고 질문에서 요구하는 답의 형식(1:팰린드롬임, 0:팰린드롬아님)으로 보면숫자가 1개일때 -> 1..

요약bottom-up 방식이면 O(n)으로 가능하고, top-down이면 O(n^2)풀이과정일단 시간복잡도를 가늠해보면 n은 150만이다.O(n^2) 불가능하고, O(nlongn), O(n)정도 가능해 보인다. 수익의 최대는 일단 고려하지 않는다면, 아래와 같이 생각할 수 있다.내가 오늘 상담을 한다면? : 이 상담이 끝나는 날 : 오늘 수익 + 오늘 상담 수익내가 오늘 상담을 하지 않는다면? : 아무것도 변하지 않음 i번째 날 수익을 버는 경우의 수는 다양하며, 이 경우의 수 중에서 최대의 수익을 버는 경우를 고려하려면...최대 수익을 저장하는 행렬(이든 벡터든) dp에 접근할때마다 max값으로 갱신한다.내가 오늘 상담을 한다면? : dp[상담끝나는날] = max(기존수익, 오늘수익+오늘상담수익) 문제..

요약처음에 문제 이해가 안갔는데, 앞뒤앞뒤 이렇게 제거한다는 얘기였다stack 2개를 사용하여 문자열 그대로 / 리버스 문자열 2개를 대상으로 앞 뒤 제거를 진행하였다.서로 제거 범위가 겹치지 않도록 index를 저장해서 관리해줘야 한다!풀이과정첫시도 - 스택 활용(시간초과)1. 검열 문자열과, 신문 문자열을 뒤집어서도 저장 - right stack을 위해서2. left stack point + right stack point의 합이 신문 문자열의 크기보다 작은 동안만 stack에 넣으며 검사를 진행3. 앞뒤로 문자열을 나누었기 때문에, 마지막에 이 문자열을 합치면서 나오는 검열 문자열이 있는지 한 번 검사 - 겸사겸사 문자열을 합치기 위해 right stack에 있는 것들을 left stack에 넣으면..

요약 stack을 이용한 조건 체크 풀이과정 괄호 체크 문제는 전형적인 stack 문제이다. string에서 모든 char에 대해 아래의 조건을 검사한다. 1. (, [ 일 때 - stack에 해당 char push 2. )일 때 - stack이 비어있지 않고, top 값이 ( 라면 PUSH - else : no 출력하고 break 3. ]일 때 - stack이 비어있지 않고, top 값이 [ 라면 PUSH - else : no 출력하고 break 모든 검사가 끝난 후 stack이 비어있지 않다면 - no 출력 여기서 주의할 점은 stack.top() 을 호출할 때 stack이 비어있다면 segmentation fault가 발생하니, top은 비어있지 않은지 앞쪽에 AND 조건으로 검사해준다. 코드 #d..

요약 맵을 통한 중복값 처리 풀이과정 1. 데이터 처리 시간초과가 나지 않고 중복값을 처리하기 위해 맵 구조를 사용한다. 정렬될 필요가 있고, 사전순 정렬이기 때문에 map을 그대로 쓴다. (혹은 unordred_map을 사용하고 추후에 sort해주는 방법도 있다.) int n, m; cin >> n >> m; cin.ignore(); map map; vector both_str; for(int i = 0 ; i < n+m; i++) { string str; getline(cin,str); map[str]++; } cin.ignore() 해주지 않으면 공백값이 처음으로 들어가서 그걸 무시하기 위해 넣었다. 이렇게 map에 예쁘게 저장되고, 중복된 값은 value가 2이다. 2. vector에 재처리 및 ..

요약 위 조건에 맞는 문자열 자르기 - 정규 표현식 사용 덧셈의 합이 최소가 되기 위한 괄호의 조건 파악하여 매커니즘 구현 풀이과정 1. 정규표현식으로 문자열 정제하기 정규표현식 문제는 55-50+40과 같은 형태를 띄고 있다. 추후 내가 생각한 방식으로 문제를 풀기 위해, 55-50+40과 같은 문자열이 주어지만 55, -50, 40 으로 문자열을 분리하길 원했다. 이를 위해 정규표현식을 사용했다. 내가 추출하고자 하는 패턴은 다음과 같다. -로 시작할수도 있다. 숫자로 구성되며 1~5자리이다. 이를 위한 정규표현식은 /[-]?\d{1,5}/g 이다. [-]? [-] - '하나' ? 해당 token이 1 또는 0 하나 나올수도(1) 안나올수도(0) \d{1,5} \d digit (0-9) {1,5} 해..

요약 sort를 이용한 vector 정렬 풀이과정 1. 값 입력 주어지는 값을 string으로 저장하여 한자리씩 vector에 넣는다. 이때 저장은 int로 다시 바꾸기 위해 '0'을 빼준다. string num = ""; getline(cin,num); vector vec; for(char c : num) { vec.push_back(c-'0'); } 2. 값 정렬 이후 벡터를 정렬하기 위해 sort를 사용한다. sort sort는 algorithm STL Header에 속해있다. sort(vec.begin(),vec.end(),greater()); 두 인자(시작과 끝)만 넣으면 default로 오름차순 정렬이 된다. 이 문제는 내림차순을 요구하기 때문에 세번째 parameter로 greater()를 ..

요약 비교 커스텀 함수를 짜서 주어지는 값을 담은 컨테이너를 요구조건에 맞게 정렬한다. 1) 길이 오름차순 2) 사전순 ✔️ 중복 제거 자료형 vector 을 사용했다. 풀이 순서 1. 값 입력 int n; cin >> n; cin.ignore(); // getline을 위한 첫 \n 무시 vector strvec; for(int i = 0; i < n; i++) { string str = ""; getline(cin,str); if(strvec.end() == find(strvec.begin(),strvec.end(),str)) { //중복 제거 strvec.push_back(str); } } if문에서 find를 이용해 중복일 경우 push_back을 하지 않게끔 한다. 2. 값 정렬 algorith..

주어진 값 범위 내에서 소수를 구하고, 주어진 값에서 소수를 뺀 값도 소수인지 검사하는 방식으로 생각했다. 다만 골드바흐 파티션이 여럿이라면 이 값의 차이가 가장 적은 것을 반환해야 한다. 작은 숫자부터 검사하게 되면 골드바흐 파티션을 찾았더래도 차잇값이 더 작은 파티션을 찾기 위해 계속 반복문을 진행해야 할 것이다. 그래서 범위 내 소수 검사를 값이 큰 것부터 내림차순으로 진행하도록 바꿔보기로 했다. 예를 들어, 16이 주어졌다면 소수 검사는 2부터 16/2=8까지만 내림차순으로 진행한다. (덧셈이기때문에 /2 범위) 그러면 7 5 3 2의 값이 나온다. 7부터 내림차순으로 16에서 뺀 값이 소수인지 검사한다는 의미. Prime 검사 함수는 이전에 쓴 것을 그대로 사용했다. int main(int ar..

단순하게 반복문을 돌려서는 시간초과가 난다. 시도 1) 나누기 검사 범위를 주어지는 값 a의 절반까지만 수행하기 bool isPrime(int a) { if(a == 1) { return false; } else { for(int i = 2; i < a/2; i++) { if(a % i == 0) { return false; } } } return true; } 시도 2) 2의 배수 배제하기 bool isPrime(int a) { if(a == 1 || a % 2 == 0) { return false; } else { for(int i = 3; i < a/2; i+=2) { if(a % i == 0) { return false; } } } return true; } 1 검사문에 짝수인지도 검사하게끔 했다..