재귀

Archive

Binary Exponentiation

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 == ..

Archive

LeetCode - Swap Nodes in Pairs

요즘 재귀에 꽂혀있음. class Solution { public: ListNode* swapPairs(ListNode* head) { if(!head) { return head; } ListNode* first= head; ListNode* second = head->next; ListNode* dummy = new ListNode(-1); dummy->next = first; ListNode* prev = dummy; while(second){ ListNode* temp = second->next; first->next = second->next; second->next = first; prev->next = second; prev = first; if(temp){ first = temp; secon..

Archive

Recursion (재귀)

코딩인터뷰 단골손님. // 1부터 N까지의 합을 구하는 재귀함수 int sum(int N) { if (N

냉국
'재귀' 태그의 글 목록