Before Gettign Into Karatsuba Algorithm

When I was a graduate student, I worked on a project related to Addition, Subtraction, Division, and Multiplication operations. The focus was on how to perform each operation more efficiently, primarily from a hardware perspective (including topics like adding multiplexers).

Let’s first examine example code for Addition, Subtraction, and Multiplication. These are implemented in C++, with the assumption that the first digit is always larger than the second digit. The key characteristic is that all operations are handled as strings.

Addition

string Add(string str1, string str2)
{
	if (!str1.size() && !str2.size())
		return "0";

	int N = max(str1.size(), str2.size());
	str1 = string(N - str1.size(), '0') + str1;
	str2 = string(N - str2.size(), '0') + str2;

	string result(N, '0');
	int carry = 0;
	for (int i = N - 1; i >= 0; i--)
	{
		int n1 = str1[i] - '0';
		int n2 = str2[i] - '0';

		int sum = n1 + n2 + carry;

		carry = sum / 10;
		result[i] = char(sum % 10 + '0');
	}

	if (carry > 0)
	{
		result.insert(0, string(1, carry + '0')); // carry insert '1'
	}

	return result;
}

I have performance metrics for this code based on N. Considering the time complexity, it’s approximately T(N) ≈ N. Of course, when an insert occurs, there might be a constant factor multiplied.

Subtraction

string Subtract(string str1, string str2)
{
	if (!str1.size() && !str2.size())
		return "0";

	int N = max(str1.size(), str2.size());
	str1 = string(N - str1.size(), '0') + str1;
	str2 = string(N - str2.size(), '0') + str2;

	string result(N, '0');
	int carry = 0;
	for (int i = N - 1; i >= 0; i--)
	{
		int n1 = str1[i] - '0';
		int n2 = str2[i] - '0';

		int sum = n1 - n2 + carry + 10;
		carry = sum / 10;
		result[i] = char(sum % 10 + '0');
		carry -= 1;
	}

	if (result[0] == '0')
	{
		result.replace(0, 1, "");
	}

	return result;
}

Similarly, I have performance metrics for this code based on N. The time complexity is approximately T(N) ≈ N.

Multiplication

string Multiply(string str1, string str2)
{
	if (!str1.size() && !str2.size())
		return "0";


	int N = max(str1.size(), str2.size());
	str1 = string(N - str1.size(), '0') + str1;
	str2 = string(N - str2.size(), '0') + str2;

	string result(2 * N, '0');

	for (int i = N - 1; i >= 0; i--)
	{ 
		int carry = 0;
		int n1 = str1[i] - '0';
		int k = N + i;
		for (int j = N - 1; j >= 0; j--)
		{
			int n2 = str2[j] - '0';
			int sum = n1 * n2 + int(result[k] - '0') + carry;
			carry = sum / 10;
			result[k] = char(sum % 10 + '0');
			k -= 1;
			std::cout << n1 << " " << n2 << " " << carry << " " << result << endl;
		}

		result[k] = char(carry + '0');
	}

	int i = 0;
	while (result[i] == '0') i += 1;
	result = result.substr(i, 2 * N - i);

	return result;
}

This case might be a bit different. Since there are two loops, we can express the complexity as (N-1) * (N-1) = N². In the process of finding the index of ‘0’, it can be expressed as constant * N². Of course, we might not always discuss the constant factor, but the main point here is to identify what has a major impact.

Karatsuba Algorithm

The Karatsuba algorithm is an efficient multiplication algorithm that uses a divide-and-conquer approach to multiply large numbers. Developed by Anatoly Karatsuba in 1960, it reduces the complexity from O(n²) in the standard multiplication algorithm to approximately O(n^(log₂3)) ≈ O(n^1.585).

Let’s analyze the implementation:

string KaratsubaHelper(string str1, string str2, int level) // level은 디버깅용
{
	cout << "Level " << level << " : " << str1 << " x " << str2 << endl;

	int N = max(str1.size(), str2.size());
	str1.insert(0, string(N - str1.size(), '0'));
	str2.insert(0, string(N - str2.size(), '0'));

	if (N == 1)
	{
		string result = to_string(stoi(str1) * stoi(str2));
		return result;
	}

	int mid = N / 2;

	string a = str1.substr(0, mid);
	string b = str1.substr(mid, N - mid);

	string c = str2.substr(0, mid);
	string d = str2.substr(mid, N - mid);

	string ac = KaratsubaHelper(a, c, level + 1);
	ac.append(string((N - mid) * 2, '0'));

	return string("0");
}

string Karatsuba(string str1, string str2)
{
	if (!str1.size() || !str2.size()) return "0";
	string result = KaratsubaHelper(str1, str2, 0); 
	int i = 0;
	while (result[i] == '0') i += 1;
	result = result.substr(i, result.size() - i);
	return result;
}

Key Insights

The implementation above is incomplete but demonstrates the core concept of the Karatsuba algorithm. Here’s how it works:

1. Padding: First, we ensure both numbers have the same number of digits by padding with leading zeros.
2. Base Case: If we’re down to single-digit numbers, we perform a direct multiplication.
3. Divide: For larger numbers, we split each number into two parts:
   • If we represent the numbers as X = a·10^(n/2) + b and Y = c·10^(n/2) + d Where a, b, c, and d are n/2-digit numbers
4. Recursive Multiplication: The complete algorithm would compute:
   • ac = a × c
   • bd = b × d
   • (a+b)(c+d) = ac + ad + bc + bd
   • ad + bc = (a+b)(c+d) - ac - bd
5. Combine: The result is ac·10^n + (ad+bc)·10^(n/2) + bd
   • The current implementation only calculates ac and appends the appropriate number of zeros, but is missing the calculations for bd and (ad+bc).

Optimizations

The key insight of Karatsuba is that we can compute the product of two n-digit numbers with only three recursive multiplications instead of four:

• ac
• bd
• (a+b)(c+d)

From these, we derive ad+bc = (a+b)(c+d) - ac - bd, reducing the number of recursive calls and improving efficiency.

Time Complexity

The time complexity is O(n^(log₂3)) ≈ O(n^1.585), which is significantly better than the O(n²) complexity of the standard multiplication algorithm for large numbers.

To complete this implementation, we would need to:

1. Calculate bd = b × d
2. Calculate (a+b)(c+d)
3. Derive ad+bc
4. Combine all terms with appropriate powers of 10

This algorithm is particularly useful for multiplying very large integers that exceed the capacity of built-in numeric types.

Resource

• Karatsuba Algorithm

일단 Imaging 이라는 의미에서 보면, High Dynamic Range 라는 말이 빛의 강도(level) 에 따라서, Scene 이 얼마나 변경되느냐? 라는 말이다. Wiki 에서도 “The dynamic range refers to the range of luminosity between the brightest area and the darkest area of that scene or image” 라고 한다.

실제 세상의 광도(Luminance) 범위는 넓다. 하지만 Digital Image 로서는 (JPEG, PNG, LDR) 같은 경우는 RGB 각 채널당 8 Bit 이고, 256 단계를 거치면서, 0 ~ 1 사이의 상대적인 밝기 값만 표현한다. 하지만 현실의 밝기는 그것보다 더넓으며, 표현하는데있어서 한계가 있기 때문에 HDR Imaging 이 나왔다.

그래서 비교를 하자면

이러한식으로 표현이 된다. 그래서 Graphics 에서는 어떻게 사용되고, Environment Mapping 할때 어떻게 설정이 되는지를 알아보는게 오늘 이 Post 의 목표이다.

그리고 아래의 그림이 조금더 자세하게 나타내준다.

기존 Enviornment Mapping 을 했을시에는 LDR 이나 SDR 에서 하나 Pixel 에 대한 색깔을 표현할때에, R8G8B8A8_UNORM 기본 적으로 32 bits(8 x 4) 를 사용했고, 0 - 255 까지의 unsigned integer 의 값을 사용했으며, 그 범위를 Normalize 해서 사용했었다. 그리고 기존에 문제라고 하면 문제가, 환경의 Light 들이 많아서, Pixel Shader 에서 값을 처리 Color 값을 Return 할때 1 보다 큰값들을 처리를 못했었다. 즉 내부적으로는 output.pixelColor = saturate(…, 0.0, 1.0) 이런식으로 처리가 된다고 보면 됬었다.

하지만 HDR (High Dynamic Range Rendering): HDRR 또는 High Dynamic Range Lighting 은 HDR 에서 Lighting 을 계산하는것이며, 더 넓은 범위에 대한 조명에 대해서 Rendering 을 할수 있다는 말… 넓은 범위라는건, 사용하는 숫자의 대한 범위가 넓고, DXGI_FORMAT_R16G16B16_FLOAT 이 포맷을 사용한다.

그래서 CPU 쪽에서 SwapChaing 을 생성할때, BufferDesc Format 옵션을 아래와 같이 설정을 해줘야한다.

DXGI_SWAP_CHAIN_DESC sd;
ZeroMemory(&sd, sizeof(sd));
sd.BufferDesc.Width = m_screenWidth;   // set the back buffer width
sd.BufferDesc.Height = m_screenHeight; // set the back buffer height
sd.BufferDesc.Format = DXGI_FORMAT_R16G16B16A16_FLOAT; // floats
sd.BufferCount = 2;                                // Double-buffering
sd.BufferDesc.RefreshRate.Numerator = 60;
sd.BufferDesc.RefreshRate.Denominator = 1;

이말은 BackBuffer 를 사용해서, Postprocessing 하는 Buffer Format 들은 전부다 Format 을 변경해줘야한다. (context->ResolveSubresource 하는곳)

HDRI Image Copy (참고)

float 은 기본적으로 32 bits wide 인데, 최근 들어서는 16 bit 로도 충분하기 때문에 Half precision floating point 도 있다. GPU 는 최종적으로 half precision floating point 에 최적화가 잘되어있다고 한다. 그래서 대부분은 아래와 같은 방식으로 f16 library 를 사용하면 된다

vector<float> f32(image.size() / 2);
uint16_t *f16 = (uint16_t *)image.data();
for(int i =0 ; i < image.size() / 2; i++){
    f32[i] = fp16_ieee_to_fp32_value(f16[i]);
}

f16 = (uint16_t *)image.data();
for (int i = 0; i < image.size(); i++)
{
    f16[i] = fp16_ieee_from_fp32_value(f32[i] * 2.0f);
}

Tone Mappings

Tone Mapping 은 Color Mapping 의 한 종류의 Technique 이라고 한다. 일단 Tone Mapping 을 하는 이유가 있다. 사실 HDRI 의 이미지는 요즘 HDR Camera 에서도 충분히 나온다. 하지만 우리가 사용하는 모니터 / 디스플레이 같은 경우 (0~1 또는 0 ~255(8bits)) 로 제한된 밝기를 표현한다. 아까 이야기 한것처럼 우리가 보는 세계는 넓은 밝기 정보를 가지고 있는데, 이걸 디스플레이에다가 다시 뿌리게 하려면, SDR(Standard Dynamic Range) 로 변환을 해줘야하는데, 현실세계의 밝기 정보를 디스플레이가 표현할수 있는 범위로 압축을 하면서도, 보기 좋은 Image 로 보정/변환 하는 작업을 Tone Mapping 이라고 한다.

Tone Mapping 이 안됬을 경우에는 어떤 Side Effect 가 있을까? 라고 물어본다면, 아래와 같이, 밝은 영역이 모두 하얗게 뭉게지거나, 너무 어두운영역도 뭉개지게 된다. 즉 숨어있는 이 Pixel 값을 잘 보정시켜서 조금 더 부드러운 Image 를 만들고, 그리고 이걸 잘? Rendering 하는게 관점이다.

Tone Mapping 도 아래와같이 여러개의 Operator 들이 있다.

Exposure

Exposure: 카메라의 어떤 현상, 렌즈를 오래 열어 놓으면, 빛을 더 많이 받아들이는 현상이다. 예를 들어서 예제 JPG 이미지 같은 경우 (즉 SDR) 일때는 Exposure 를 키우게 되면, 그냥 화면 자체가 밝아진다. 하지만 HDRI 같은 경우, 전체 Pixel 이 선명?해지는것과 밝아지는거의 차이가 있다. 그래서 Exposure 을 낮춘다고 했을때

아래의 그림처럼 진짜 태양 찾기가 가능해진다.

Gamma Correction

Gamma Correction : 어떤 영역에 색을 더 넓게 보여줄지를 의미한다. 옛날 모니터 같은 경우는 cathode-ray tube monitor 라고 하고, Input Voltage 를 두배로 컴퓨터에 줬을때, 2배로 Output 이 전혀 나오지 않았다. 즉 선형보다는 비선형으로 Gamma 지수에 따라서 비선형적으로 출력을 했고, 입력신호의 2.2 제곱에 해당하는 밝기를 출력 했다.

그래서 즉 모니터의 Gamma 가 2.2 라고 한다고 하면, Image 를 Display 하기전에 Pixel 값을 Input^1/2.2 저장하거나 변환을 해줘서 Linear Tonemapping 을 만들수 있다. 그리고 이 Gamma 값을 조정할수 있는게 Gamma Correction 이라고 말을 할수 있겠다.

HDRI Pipeline

결국 PBR 에 가까워지려면, 환경맵이 필요하고, 그 환경맵을 HDRI (High Dynamic Range Image) 를 이용할 수 있다.

Resource

• High Dynamic Range Rendering
• HDR Image Reconstruction and Tone Mapping
• Gamma Correction

Mipmap 이라는건 Main Texture Image 를 downsized 를 시킨 여러개의 사진이라고 생각하면 된다. 즉 여러개의 해상도를 조정하며 만든 여러개의 Image 라고 생각 하면 된다. Computer Vision 에서는 Image Pyramid 라고도 하는데, 여러개의 서로 다른 Resolution 의 Image 를 올려 놓았다고 볼수 있다. 아래의 이미지를 봐보자. 아래의 Image 를 보면 512, 512/2, 256/2… 절반씩 Resolution 이 줄어들고 있다.

그러면 어디서 이게 사용되까? 라고 한다면 바로 MIPMAP 이다. MIPMAP vs Regular Texture 라고 하면, 바로 문제가 Aliasing 이 문제이다. 아래의 Image 를 보면 이해할수 있을것 같다.

Unreal 에도 똑같은 기능이 있는데, 바로 RenderTargetTexture 를 생성시에 여러가지의 옵션이 보인다.

옵션을 보면, Texture RenderTarget 2D 라고 해서, DirectX 에서 사용하는 description 을 생성할때와 동일한 옵션이 된다. 여기에서 Mips Filter(Point Sampler / Linear Interpolation Sampler) 도 보인다. 결국에는 Texture 를 Mapping 한다는 관점에서, 우리는 Texture Coordinate 을 어떠한 사각형 박스 안에 Mapping 을 해서 사용했고, 그걸 사용할때, Texture Coordinate 도 명시를 했었다. 자 결국에는 Texture 를 Mapping 한다는 관점에서 봤을때, 확대도 가능하고, 축소도 가능하다. 그게 바로 Maginification 과 Minification 이다.

즉 Magnification 을 하기 위해서, Mag Filter (To interpolate a value from neihboring texel) 이말은 결국엔 Linear Filter / Pointer Filter 로 Interpolation 과 그리고 내가 그리려는 Texture (64, 64) 를 어떠한 박스 (512, 512) 에 붙인다고 상상했을때, 그림은 작고, 보여줘야하는 화면이 클경우, GPU 가 이 Texture 를 늘려서 보간을 해야하는 경우가 (그말은 화면 하나의 픽셀이 원래 텍스쳐의 중간쯤 위치에 거릴수 있다. texel / pixel < 1) Magnification 이라고 한다. 그리고 이 반대의 상황을 Minification 이라고 한다. 그리고 MipLevels = 0 으로 둔다는게 Max MipMap 즉 MipMap 을 Resolution 대로 만들고 이게 결국에는 LOD 와 똑같게된다.

Subresoruce Term 인데, Texture 의 배열로 각각 다른 Texture 에 대해서, 각각의 Mipmap 들을 생성한는것이 바로 Array Slice 이고, 여러개의 Texture 에서. 같은 Resolution 끼리, mipmap level 이 같은걸 MIP Slice 라고 한다. A Single Subresoruce(Texture) 즉 하나의 Resource 안에서, Subresource 를 선택해서 골라갈수 있다. (이걸 Selecting a single resource) 라고 한다. 자세한건, Subresource 를 확인하면 좋다.

아래의 코드를 보자면 추가된건 별로 없지만, Staging Texture 임시로 데이터를 놓는다. 그 이유는 MipMap 을 생성할때, 우리가 내부의 메모리가 어떻게 되어있는지 모르므로, 최대한 안전하게 Input Image 를 StagingTexture 를 만들어 놓고, 그리고 실제로 사용할 Texture 를 설정을 해준다. 이때 Staging 한거에대해서 복사를 진행하기에, D3D11_USAGE_DEFAULT 로 설정을 하고, 그리고 GPU 에게 결국에는 RESOURCE 로 사용할것이다 라는걸 Description 에 넣어주고, Mip Map 을 설정한다. (즉 GPU 에서 GPU 에서 복사가 이루어진다.) 즉 Staging Texture는 GPU 리소스에 직접 데이터를 쓸 수 없기 때문에, CPU 쓰기 전용 텍스처에 데이터를 쓴 후 GPU용 리소스로 복사하는 중간 단계라고 말을 할수 있겠다. 그리고 메모리만 잡아놓고, CopySubresourceRegion 을 통해서, StagingTexture 를 복사를 한다. 그리고 마지막에 그 해당 ResourceView 에, 이제 GenerateMips 를 하면 될것 같다.

CPU

ComPtr<ID3D11Texture2D> texture;
ComPtr<ID3D11ShaderResourceView> textureResourceView;

ComPtr<ID3D11Texture2D> CreateStagingTexture(ComPtr<ID3D11Device> &device,
                     ComPtr<ID3D11DeviceContext> &context, const int width,
                     const int height, const std::vector<uint8_t> &image,
                     const int mipLevels = 1, const int arraySize = 1) 
{
    D3D11_TEXTURE2D_DESC txtDesc;
    ZeroMemory(&txtDesc, sizeof(txtDesc));
    txtDesc.Width = width;
    txtDesc.Height = height;
    txtDesc.MipLevels = mipLevels;
    txtDesc.ArraySize = arraySize;
    txtDesc.Format = DXGI_FORMAT_R8G8B8A8_UNORM;
    txtDesc.SampleDesc.Count = 1;
    txtDesc.Usage = D3D11_USAGE_STAGING;
    txtDesc.CPUAccessFlags = D3D11_CPU_ACCESS_WRITE | D3D11_CPU_ACCESS_READ;

    ComPtr<ID3D11Texture2D> stagingTexture;
    HRESULT hr = device->CreateTexture2D(&txtDesc, nullptr, stagingTexture.GetAddressOf())
    if (FAILED(hr)) {
        cout << "Failed to Create Texture " << endl;
    }

    D3D11_MAPPED_SUBRESOURCE ms;
    context->Map(stagingTexture.Get(), NULL, D3D11_MAP_WRITE, NULL, &ms);
    uint8_t *pData = (uint8_t *)ms.pData;
    for (UINT h = 0; h < UINT(height); h++) {
        memcpy(&pData[h * ms.RowPitch], &image[h * width * 4],
               width * sizeof(uint8_t) * 4);
    }
    context->Unmap(stagingTexture.Get(), NULL);

    return stagingTexture;
}

ComPtr<ID3D11Texture2D> stagingTexture =
    CreateStagingTexture(device, context, width, height, image);

D3D11_TEXTURE2D_DESC txtDesc;
ZeroMemory(&txtDesc, sizeof(txtDesc));
txtDesc.Width = width;
txtDesc.Height = height;
txtDesc.MipLevels = 0; // Highest LOD Level
txtDesc.ArraySize = 1;
txtDesc.Format = DXGI_FORMAT_R8G8B8A8_UNORM;
txtDesc.SampleDesc.Count = 1;
txtDesc.Usage = D3D11_USAGE_DEFAULT; 
txtDesc.BindFlags = D3D11_BIND_SHADER_RESOURCE | D3D11_BIND_RENDER_TARGET;
txtDesc.MiscFlags = D3D11_RESOURCE_MISC_GENERATE_MIPS; 
txtDesc.CPUAccessFlags = 0;

// Copy the highest resolution from the staging texture
context->CopySubresourceRegion(texture.Get(), 0, 0, 0, 0, stagingTexture.Get(), 0, nullptr);

// Creating Resource View
device->CreateShaderResourceView(texture.Get(), 0, textureResourceView.GetAddressOf());

// Generate Mipmap reducing the resolution
context->GenerateMips(textureResourceView.Get()); 

GPU(Shader)

float dist = length(eyeWorld - input.posWorld);
float distMin = 1.0;
float distMax = 10.0f;
float lod = MAX_LOD * saturate((dist - distMin) / (distMax - distMin));
diffuse *= g_texture0.SampleLevel(g_sampler, input.texcoord, lod);
PixelShaderOutput output;
output.pixelColor = diffuse + specular;
return output;

GPU 에서는 결국에는 Mipmap 을 사용해줘야하므로, HLSL 에서는 그냥 Sample() 아니라 SampleLevel() 을 해줘야한다. 참고로 Sample() 과 SampleLevel 의 차이는 Sample 을 이용하면, lod Level 을 내부적으로 계산해서 샘플링을 한다고 한다. 그리고 LOD 가 0 이면 Quality 가 좋은 Texture 라고 정할수 있다. (Vertex 개수가 많음).

또, 이렇게 끝내면 좋지 않지 않느냐? 바로 RenderDoc 으로 부터 언제 MipMap 이 생성되는지 한번 봐야하지 않겠냐 싶어서 RenderDoc 을 돌려봤다. PostPorcessing 이 끄면 이 MipMap 들이 보이진 않을거다. 즉 한 Pass 와 다른 Pass 사이에 MipMap 을 내부적으로? 생성하는것 같아보인다. 제일 앞에 있는게 제일 높은 LOD 를 가지고 있다. 그리고 RenderDoc 에서 왜 클릭이 안되어있는지는 모르겠지만 Subresource 를 보면 Mip Level 들이 보이고, 내부적으로 해상도(Size) 를 계속 줄이는것 같이 보인다.

Result

Resources

• What is mipmapping
• Texture Magnification
• Texture - Slide

2024 년 6 월 3 일 부터 시작된 독일 출장 및 ADAS Testing Expo 전시회를 갔다. 솔직히 말하면, 출장 가는데 너무 준비할 서류도 많고, 여러가지로 오해도 많았어서, 하나하나 하는데 조금 힘겨웠었다. 물론 이런저런걸 따지기에는 에너지 소비가 많이됬다. 그리고 전시회를 가는 인원들이 전부다 high level 사람들이라서 교류하는것도 굉장히 힘들거라는 생각을 먼저 하다보니, 이것 저것으로 고민이 많았다. 하지만 결론적으로 말하면 그 무엇보다도 독일 사람들의 기본적인 성향과 Testing Expo 에서 우리 회사가 정말로 필요한게 무엇이 있는지와 내가 정말 좋아하는게 뭔지를 더욱더 잘알수 있게 되는 계기가 되지 않았을까 생각이 들었다.

물론 나는 이걸로 하여금, Simulation 이 되게 양날의 검이라는걸 너무 깨닫게 되었다. 물론 Simulation Environment 에서 할 수 있는 것들이 많지만, 그래도 한계가 분명 존재 할것이다. 특히나 상용 엔진을 계속 사용한다면과 우리 회사에서 하고 있는 여러 Project 들이 한 Product 에 녹아 들지 않으면, 이건 결국엔 잡다한 기능을 다가지고 있는 Simulator 라는 기능밖에 되지 않는다라는걸 알게 되었다. 이게 좋은 Career 이 될지는 굉장히 많은 의심이 되고, 하지만 결국엔 좋은 Product 를 가꾸기 위해서는 각 분야의 최고의 사람들과 일을 할수 있는 기회가 분명 필요하겠다라는 생각이 아주 많이 들었다. 특히나 한국 회사의 특성상 “이거 해줘! 기능은 일단 알아서 해줘봐 피드백 줄께” 이런식이 되버려서 참 어렵다는건 정말 알겠다. 하지만 이러한 방식으로 Hardware 의 Product 가 나온다고 했을때 분명 고장나고 사람들에 입맛에 맞지 않아서 결국엔 버려질 운명이다라는 생각밖에 안든다. 분명 Software Engineering 관점에서는 어떠한 Pipeline 이 구성되지 않은 상황속 및 Senior Engineer 가 없다고 한다면, 정말 Junior 들이 시간을 많이 투자하고, 공부하는데 정말 많은 Resource 가 필요할거다! 라는 생각 밖에 들지 않았다.

긍정적으로 봤을때는, 다른 회사와 경쟁할수 있다는 점과, 그리고 다른 회사 사람들의 의견이나 앞으로의 가능성 이런걸 판단했을때, 옳은 시장성을 가지고 있다는건 분명하다. 어떠한 분야에 몰입있기에는 정말 수많은 시간과 노력이 필요하다! 라는건 정말 뼈저리게 느껴버렸던 출장 이였다.

어쩌다보니 Logging System 을 만들고, 기록은 해놓아야 할 것 같아서, Singleton 패턴에 대해서 c++ 로 정리 하려고 한다. Singleton 이라는건 Class 를 딱 하나만 생성한다 라고 정의한다라는게 정의된다. static 으로 정의를 내릴수 있다. 그리고 객체가 복사가 이루어지면 안된다. 일단 싱글톤을 만든다고 하면, 하나의 설계 패턴이므로 나머지에 영향이 안가게끔 코드를 짜야된다. 일단 Meyer’s implementation 을 한번 봐보자.

class Singleton
{
public:
    static Singleton& getInstance();
    {
        static Singleton instance;
        return instance;
    }

private:
    Singleton(){}       // no one else can create one
    ~Singleton(){}      // prevent accidental deletion

    // disable copy / move 
    Singleton(Singleton const&) = delete;
    Signleton(Singleton&&) = delete;
    Singleton& operator=(Singleton const&) = delete;
    Singleton& operator=(Singleton&&) = delete
};

그렇다면 더확실하게 생성과 파괴의 주기를 확실하게 보기위해서는 아래와 같이 사용할수 있다.

class Singleton
{
public:
    static std::shared_ptr<Singleton> getInstance();
    {
        static std::shared_ptr<Signleton> s{ new Singleton };
        return s;
    }
private:
    Singleton(){}       // no one else can create one
    ~Singleton(){}      // prevent accidental deletion

    // disable copy / move 
    Singleton(Singleton const&) = delete;
    Signleton(Singleton&&) = delete;
    Singleton& operator=(Singleton const&) = delete;
    Singleton& operator=(Singleton&&) = delete
};

예제를 들어보자, 뭔가 기능상으로는 Random Number Generator 라고 하자. 아래와 같이 구현을 하면 좋을 같다.

class Random
{
public:
    static Random& Get()
    {
        static Random instance;
        return instance;
    }

    static float Float() { return Get().IFloat(); }
private:
    Random(){}
    ~Random();
    Random(const Random&) = delete;
    void operator=(Random const&) = delete;
    Random& operator=()
    float IFloat() { return m_RandomGenerator; } // internal
    float m_RandomGenerator = 0.5f;
};

int main()
{
    // auto& instance = Singleton::Get();   // this is good practice
    // Single instance = Singleton::Get();  // Copy this into new instance; Just want a single instance.

    float number = Random::Get().Float();
    return 0;
}

Resource

• Singleton Design Pattern
• Meyer’s Discussion
• Lecture Note
• The Cherno - Youtube

You are given an array prices where prices[i] is the price of a given stock on the ith day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.1

Implementation

• This is typical greey probelm, you select one, and compare it to get the maximum or the best output for goal once. This case, you want to maximize the profit, which in this case, you select one prices, and loop through to get the meximum prices.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int profit = 0;
        int buy = prices[0];
        for (int i = 1; i < prices.size(); i++) {
            int sell = prices[i];
            if (buy < sell) {
                profit = max(profit, sell - buy);
            } else {
                buy = sell;
            }
        }

        return profit;
    }
};

Resource

Best Time to Sell Stocks

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Approach

This is typically done in recursive fashion. But think of this. if i have steps 1, 2, 3, … i - 2, i - 1, i. Then, we need to use a step for i - 1 or i - 2 to get to i. This means I have several different steps to get to i. (this satisfies the optimal substructure). we can make a simple S(1) = 1, S(2) = 2, S(n) = S(n - 1) + S(n - 2).

First Implementation:

When I tested this on recursive way and submit, it exceed Time Limit!… Oh no…

class Solution {
public:
    int climbStairs(int n) {
        if (n < 1 || n > 46) return 0;
        if (n == 1) return 1;
        if (n == 2) return 2;
        return climbStairs(n - 1) + climbStairs(n - 2);
    }
};

Second Implementation:

Now, I need to use dynamic programming, for top-down approach, it exceed Memory Limit, which possibly because of recursive way of saving into cache won’t work very well.

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 0) return 0;
        else if (n == 1) return 1;
        else if (n == 2) return 2;
        vector<int> dp(n+1, 0);
        
        if (dp[n]) return dp[n];
        int result = climbStairs(n - 1) + climbStairs(n - 2);
        return dp[n] = result;
    }
};

Third Attempts:

Now I choose the bottom up approach, and it worked very well!

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 0) return 0;
        else if (n == 1) return 1;
        else if (n == 2) return 2;
        vector<int> dp(n+1, 0);
        dp[1] = 1;
        dp[2] = 2;
        
        for(int i = 3; i <= n; i++) {
            dp[i] = dp[i -1] + dp[i -2];
        }
        return dp[n];
    }
};

Resource

Climbing Stairs

Given an integer array arr and a 2D integer array queries, where each element of queries represents a query in the form of [s, e, k], perform the following operation for each query: For each query, find the smallest element in arr[i] that is greater than k for all i such that s ≤ i ≤ e. Return an array containing the answers for each query in the order they were processed. If no such element exists for a query, store -1 for that query.

Constraints:

The length of arr is between 1 and 1,000 (inclusive). Each element of arr is between 0 and 1,000,000 (inclusive). The length of queries is between 1 and 1,000 (inclusive). For each query [s, e, k], s and e are between 0 and the length of arr minus 1 (inclusive).

Implementation

vector<int> solution(vector<int> arr, vector<vector<int>> queries) {
    int INF = std::numeric_limits<int>::max();
    vector<int> answer(queries.size(), INF);
    for(int i = 0; i < queries.size(); i++) {
        int start = queries[i][0];
        int end = queries[i][1];
        int compare = queries[i][2];
        
        for (int j = start; j <= end; j++) {
            if (arr[j] > compare) {
                answer[i] = min(answer[i], arr[j]);
            }
        }
        
        if (answer[i] == INF) answer[i] = -1;
    }
    return answer;
}

Since, we’re looping through the queries n, which is O(n), but there is inner loop which is start time to end time. In the worst case, it can be O(n^2).

Given an integer array arr and a 2D integer array queries, where each element of queries represents a query in the form of [s, e], perform the following operation for each query: For each query, increment arr[i] by 1 for all i such that s ≤ i ≤ e. Return the array arr after processing all queries according to the above rule.

Constraints:

The length of arr is between 1 and 1,000 (inclusive). Each element of arr is between 0 and 1,000,000 (inclusive). The length of queries is between 1 and 1,000 (inclusive). For each query [s, e], s and e are between 0 and the length of arr minus 1 (inclusive).

Implementation

vector<int> solution(vector<int> arr, vector<vector<int>> queries) {
    for (int i = 0; i < queries.size(); i++) {
        int start = queries[i][0];
        int end = queries[i][1];
        for (int j = start; j <= end; j++) {
            arr[j]++;
        }
    }
    return arr;
}

instead of creating the output answer, we can just reduce the space, by writing into arr directly.

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i]. The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer. You must write an algorithm that runs in O(n) time and without using the division operation.

The major constraint is to calculate the product of array except itself. If you implement in brute force way, you will get O(n^2). However, this is the constraints! We need to solve this problem for O(n) time complexity with no extra space complexity.

Approach

This 2D structure represents the products of all numbers except the one at each index. The second and third lines show how we can calculate the left and right parts separately.

24, 2, 3, 4
1, 12, 3, 4
1,  2, 8, 4
1,  2, 3, 6

For the input array , the output array represents the prefix products, which are the products of all numbers to the left of each index. This prefix product is calculated by accumulating the numbers to the left at each iteration.

For instance, in the first iteration, there are no numbers to the left, so it’s just 1. In the second iteration, you have 1 to the left, so the output is 1 * 1 = 1. In the third iteration, you have 1 and 2 to the left, so the output becomes 1 * 2 = 2`, and so on.

This process continues until you have the prefix products for all indices. After calculating the prefix products, you can calculate the suffix products and multiply them with the prefix products to get the final result.

Then you do the right, which are going to be the product of suffix. You can do the same thing from right to left.

Implementation

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();

        std::vector<int> output(n, 1);

        // left
        for(int i = 1; i < n; i++) {
            output[i] = output[i - 1] * nums[i - 1];
        }
        
        // right
        int right = 1;
        for (int i = n - 1; i >= 0; i--){
            output[i] *= right;
            right *= nums[i];
        }
        
        return output;
    }
};