[Algorithm] 유클리드 호제법; 최대공약수 찾기

알고리즘을 풀다보면 최대공약수를 구할 수 있는지 요구하는 문제가 많다. 딱히 알고리즘이 아니더라도, 코딩을 하다보면 최대공약수가 필요한 경우가 많다.

이럴때 쓰이는 알고리즘이 유클리드 호제법이다.

 

\(a, b ∈ Z\)이고 \(a≥b\)라면 \(a = bq + r\)를 만족하는 유일한 정수 \(q, r\)이 존재한다.\((0≤r<b)\)

\(GCD(a, b) = d\)일 때, \(a\)와 \(b\)는 \(a = αd, b = βd\)로 표현이 가능하며 이 때 \(α\)와 \(β\)는 서로소이다.

위의 식 \(a = bq + r\)은 \(αd = βdq + r\)로 표현할 수 있으며, \(r = (α – βq)d\)가 된다.

\(b = βd, r = (α – βq)d\)에 의해 \(d\)는 \(r\)과 \(b\)의 공약수 중 하나라는 것을 알 수 있다.  이 때 \(b\)와 \(r\)의 최대공약수를 \(c\)라고 하면 \(c≥d\)임을 알 수 있다.

\(b = mc, r = nc\) (\(m, n\)은 서로소)라 하면 위의 식 \(a = bq + r\)은 \(a = mcq + nc = (mq + n)c\)이다.

위에서 구한 두 식 \(b = mc\)와 \(a = (mq + n)c\)에 의해 \(c\)는 \(a, b\)의 공약수 중 하나라는 것을 알 수 있다.

따라서 \(c\)는 \(a, b\)의 최대공약수 \(d\)보다 같거나 작아야 한다. \((d≥c)\)

위에서 구한 두 식 \(c≥d, d≥c\)에 의해 \(c=b\)가 성립하고, 따라서 \(GCD(a, b) = GCD(b, r)\)이 성립한다.

 

예시로 1071과 1029의 최대공약수를 구해보자.

위의 증명에 따라 GCD(1071, 1029) = GCD(1029, 42) = GCD(42, 21) = GCD(21, 0)이 성립하고 GCD(X, 0) = X라는 성질에 의해 GCD(21, 0) = 21이다.

따라서 1071과 1029의 최대공약수는 21이다.

 

이 식을 코드로 표현하면 아래와 같다. gcd함수의 매개변수 x, y의 대소관계는 중요치 않은데, x < y라면 첫번째 루프를 돌면서 swap이 되므로, x > y가 되기 때문이다.

#include <stdio.h>

int gcd(int a, int b) {
	int temp;

	while (b) {
		temp = a % b;
		a = b;
		b = temp;
	}
	
	return a;
}

int main() {
	int a = 1071, b = 1029;

	printf("gcd(%d, %d) = %d\n", a, b, gcd(a, b));

	return 0;
}
gcd(1071, 1029) = 21

 

유클리드 호제법의 나머지 연산은 최악의 경우라도 b의 자릿수의 5배를 넘지 않는다는 것이 라메의 정리에 의해 증명되었다.

 

따라서 재귀적으로 프로그래밍을 해도 크게 문제가 되지 않는다.

int gcd(int a, int b){
	return b ? gcd(b, a%b) : a;
}

 

 

[C/C++] SSD 판별 소스

https://stackoverflow.com/questions/23363115/detecting-ssd-in-windows/33359142

꽤 오래전에 대학 선배가 C언어로 SSD를 판별할 수 있냐고 물어봤다. 찾아보니 MSDN과 stackoverflow에 이미 잘 정리된 코드가 있었다. 사실 검색하면 바로 나오는데, 한글로 정리된 자료는 별로 없는 듯했다. 이에 소스코드를 공유하고자 한다.

 

#include <windows.h>
#include <WinIoCtl.h>
#include <Ntddscsi.h>
#include <tchar.h>
#include <cstddef>
#include <stdio.h>
 
#define ATA_FLAGS_DATA_IN   (1 << 1)
 
#define FILE_DEVICE_CONTROLLER  0x00000004
#define IOCTL_SCSI_BASE         FILE_DEVICE_CONTROLLER
 
#define METHOD_BUFFERED 0
#define FILE_READ_ACCESS    ( 0x0001 )
#define FILE_WRITE_ACCESS   ( 0x0002 )
 
#define kNominalMediaRotRateWordIndex 217
 
struct ATAIdentifyDeviceQuery
{
    ATA_PASS_THROUGH_EX header;
    WORD data[256];
};
 
void deviceInfo(TCHAR param[]) {
    TCHAR defaultPath[8] = _TEXT("\\\\.\\");
    TCHAR letter = param[0];
    TCHAR path[256] = _TEXT("");
    BOOL bIsSSD = FALSE;
    WORD wRPM = 0;
    DWORD bytesReturned;
    HANDLE hDevice = NULL;
     
    _stprintf(path, _TEXT("%s%c:"), defaultPath, letter);
     
    hDevice = CreateFile(path,
        0,
        0,
        NULL,
        OPEN_EXISTING,
        FILE_ATTRIBUTE_NORMAL,
        NULL);
 
    if (hDevice != INVALID_HANDLE_VALUE){
        _tprintf(_TEXT("TRIM="));
 
        STORAGE_PROPERTY_QUERY spqTrim;
        spqTrim.PropertyId = (STORAGE_PROPERTY_ID)StorageDeviceTrimProperty;
        spqTrim.QueryType = PropertyStandardQuery;
 
        bytesReturned = 0;
        DEVICE_TRIM_DESCRIPTOR dtd = { 0 };
        if (::DeviceIoControl(hDevice, IOCTL_STORAGE_QUERY_PROPERTY,
            &spqTrim, sizeof(spqTrim), &dtd, sizeof(dtd), &bytesReturned, NULL) &&
            bytesReturned == sizeof(dtd)){
            _tprintf(_TEXT("%s"), dtd.TrimEnabled ? _TEXT("Y (is SSD)") : _TEXT("N (is HDD)"));
        }
        else{
            int err = ::GetLastError();
            _tprintf(_TEXT("?"));
        }
 
        _tprintf(_TEXT(", seekPenalty="));
 
        STORAGE_PROPERTY_QUERY spqSeekP;
        spqSeekP.PropertyId = (STORAGE_PROPERTY_ID)StorageDeviceSeekPenaltyProperty;
        spqSeekP.QueryType = PropertyStandardQuery;
 
        bytesReturned = 0;
        DEVICE_SEEK_PENALTY_DESCRIPTOR dspd = { 0 };
        if (::DeviceIoControl(hDevice, IOCTL_STORAGE_QUERY_PROPERTY,
            &spqSeekP, sizeof(spqSeekP), &dspd, sizeof(dspd), &bytesReturned, NULL) &&
            bytesReturned == sizeof(dspd)){
            _tprintf(_TEXT("%s"), dspd.IncursSeekPenalty ? _TEXT("Y (is HDD)") : _TEXT("N (is SSD)"));
        }
        else{
            int err = ::GetLastError();
            _tprintf(_TEXT("?"));
        }
 
 
        _tprintf(_TEXT(", RPM="));
 
        ATAIdentifyDeviceQuery id_query;
        memset(&id_query, 0, sizeof(id_query));
 
        id_query.header.Length = sizeof(id_query.header);
        id_query.header.AtaFlags = ATA_FLAGS_DATA_IN;
        id_query.header.DataTransferLength = sizeof(id_query.data);
        id_query.header.TimeOutValue = 5;
        id_query.header.DataBufferOffset = offsetof(ATAIdentifyDeviceQuery, data[0]);
        id_query.header.CurrentTaskFile[6] = 0xec; 
 
        bytesReturned = 0;
        if (::DeviceIoControl(hDevice, IOCTL_ATA_PASS_THROUGH,
            &id_query, sizeof(id_query), &id_query, sizeof(id_query), &bytesReturned, NULL) &&
            bytesReturned == sizeof(id_query)){
            _tprintf(_TEXT("%d"), (UINT)id_query.data[kNominalMediaRotRateWordIndex]);
        }
        else{
            int err = ::GetLastError();
            _tprintf(_TEXT("?"));
        }
 
        _tprintf(_TEXT("\n"));
        ::CloseHandle(hDevice);
    }
    else {
        _tprintf(_TEXT("No Directory\n"));
    }
}
 
void main() {
    TCHAR filepath[256];
 
    while (true) {
        ZeroMemory(filepath, sizeof(filepath));
        _tprintf(_TEXT("\n\nInput filepath : "));
        _tscanf(_TEXT("%s"), filepath);
 
        if (isalpha(filepath[0]) && filepath[1] == ':') {
            deviceInfo(filepath);
        }
        else {
            _tprintf(_TEXT("\n\nWrong Path!!\nfilepath example : C:\\YOUR_DIRECTORY\n\n"));
        }
 
        fflush(stdin);
    }
}