MrCodeMania

2의 보수 이용하기! c = a - b; c >> 31; c가 1이면 음수 c가 0이면 양수

순열을 출력하는 함수

유클리드 호제법 (- 互除法, Euclidean algorithm)은 2개의 자연수 또는 정식(整式)의 최대공약수 를 구하는 알고리즘 의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 이는 명시적으로 기술된 가장 오래된 알고리즘이다. 78696과 19332의 최대공약수를 구하면, 78696 ＝ 19332 ×4 ＋ 1368 19332 ＝ 1368×14 ＋ 180 1368 ＝ 180×7 ＋ 108 108 ＝ 72×1 ＋ 36 180 ＝ 108×1 + 72 72 ＝ 36 ×2 최대 공약수는 36

# define P 1000000007 long long power ( long long x , long long y ) { long long ReturnValue = 1 ; while ( y > 0 ) { if ( y % 2 ) { ReturnValue * = x ; ReturnValue % = P ; } x * = x ; x % = P ; y / = 2 ; } return ReturnValue ; }

해 탐색 알고리즘 중 하나. 해를 찾는 도중에 해가 아니면 되돌아가서 다시 해를 찾아 가는 기법 백트래킹 기법 은 최적화(optimization) 문제와 결정(decision) 문제를 해결 결정 문제 : 문제의 조건을 만족하는 해가 존재하는지의 여부를 ‘yes’ 또는 ‘no’가 답하는 문제 -미로 찾기 -해밀턴 경로 문제 (모든 꼭짓점을 한번씩 지나는 경로) -부분 집합의 합 문제(집합의 부분집합 중에서 원소를 다 더한 값이 0이 되는 경우 있는지) 백트래킹 알고리즘 은 기본적으로 상태공간트리 를 이용한다. 어떤 노드의 유망성 을 점검한 후, 유망하지 않다고 판단이 되면  그 노드의 후손노드들에 대한 탐색을 중지 하고, 부모노드로 돌아가서( Backtracking ) 다른 후손노드에 대한 탐색을 계속하는 절차 깊이우선탐색(DSP)과 다른 점! 깊이우선탐색은 완결탐색 백트래킹 기법은 가지치기 를 하여 완결탐색보다 효율적! 다시 정리하면, Backtracking Algorithm ->기본 알고리즘 ①상태공간트리에서 깊이우선탐색을 실시 ②각 노드가 유망한지를 점검 ->유망하지 않은 노드들은 검색을 하지 않음 (가지치기) ->유망한 노드에 대해서만 그 노드의 자식노드를 탐색 ->깊이우선탐색(DSP)보다는 빠르지만 여전히 지수시간을 가짐 예로는 여행자 문제, N개의 퀸 문제(2의 n승의 체스판에 n개의 퀸을 놓는 문제) ================================================== N개의 퀸 문제 BLANK, FILLED, CHECKED, QUEEN 1.모두 BLANK로 표시(Init) 2.행마다 CHECKED 표시(Check) 3.CHECKED마다 QUEEN 표시.(IsTherePossible) 4.QUEEN을 못 놓는 부분을 FILLED 표시(Fill) 5.QUEEN의 개...