To Do 순열을 사전순으로 나열 했을 때, 사전순으로 Next or Prev 순열을 찾는 방법에 대해 알아보자. 1) STL 함수 사용 2) 직접 구현 같은 Logic Problem : 10973 이전 순열 / 10974 모든 순열 Key Point n값에 따라 앞에서 부터 n자리까지만 순열을 구한다. do ~ while이 아닌 while문을 사용하게되면 다음과 같은 문제가 발생한다. 123 132가 아닌 즉 123상태에서 이미 swap을 시키게 된다. 132부터 시작한다. next or prev permutation의 Return Value에 대해 알아보자. next_permutation(v.begin(),v.end()); /* 만약 vector에 1 2 3 4 가 있다면 1 2 4 3 으로 순열을 ..
Binary Exponentiation(exponentiation by squaring)은 a의 n제곱을 O(n) 대신 O(logn) 의 곱셈만 사용하여 계산할 수 있는 트릭이다. 이 트릭은 수리적인 일 이외의 다양한 분야에 적용할 수 있고, 때문에 결합법칙을 갖는 모든 연산에 사용될 수 있다. 알고리즘 a의 n제곱은 단순히 a에 a를 n-1번 만큼 곱해주는 것으로 표현할 수 있다. 하지만 이런 방식은 a나 n이 큰 경우 효율적이지 못하다. Binary Exponentiation의 핵심은, 제곱수 n의 이진표현이다. 다음은 n을 이진수로 변경을 한 예시이다. 적용 기존의 재귀 방식으로 제곱을 계산하는 코드. long long binpow(long long a, long long b) { if (b == ..
#include #include #include using namespace std; bool solution(vector phone_book) { bool answer = true; sort(phone_book.begin(), phone_book.end()); for(int i = 0 ; i < phone_book.size() - 1;i++) { if (phone_book[i] == phone_book[i+1].substr(0, phone_book[i].length())) answer = false; } return answer; }
#include #include using namespace std; vector solution(vector heights) { vector answer; answer.resize(heights.size(), 0); // 제일 오른쪽에 있는 타워부터 탐색 for (int curr = heights.size() - 1; curr >= 0; --curr) { int currHeight = heights[curr]; for (int compare = curr - 1; compare >= 0; --compare) { if (heights[compare] > currHeight) { answer[curr] = compare + 1; break; } } } return answer; }
