Coding/CPP 삽질기2023. 7. 3. 23:53

보기 > 도구 상자 (X) 클릭 

단축키: Ctrl +Atl +X 

Posted by chobocho
Coding/CPP 삽질기2023. 7. 1. 18:03

주말 동안 C# 을 공부 하기로 하고, 첫 프로그램을 작성해 보았다.

언어을 배우면 누구나 만들어 보는 Word Count 프로그램.

class WordCount
{
    private readonly string fileText;

    WordCount(string fileText)
    {
        this.fileText = fileText;
    }

    private void printInfo()
    {
        var wordCount = getWordCount(fileText);
        var lineCount = getLineCount(fileText);

        Console.WriteLine($"LineCount: {lineCount}");
        Console.WriteLine($"WordCount: {wordCount}");
        Console.WriteLine($"Character Count: {fileText.Length}");
    }

    private int getWordCount(string fileText)
    {
        return fileText.Split(new[] { ' ', '\t', '\n', '\r' }, StringSplitOptions.RemoveEmptyEntries).Length;
    }
    
    private int getLineCount(string fileText)
    {
        return fileText.Split(new[] { '\n' }).Length;
    }
    
    static void Main(string[] args)
    {
        if (args.Length == 0)
        {
            Console.WriteLine("Usage: WordCount [FileName]");    
            return;
        }

        string filePath = args[0];
        if (!File.Exists(filePath))
        {
            Console.WriteLine($"{filePath} not exist!");
            return;
        }

        string fileText = File.ReadAllText(filePath);
        WordCount wc = new WordCount(fileText);
        wc.printInfo();
    }
}

'Coding > CPP 삽질기' 카테고리의 다른 글

[C#] Visual studio 도구 상자 활성화 방법  (0) 2023.07.03
Intellij Code snippet 사용법  (0) 2023.06.13
[CPP] 펜윅 트리 (Fenwick Tree)  (0) 2023.06.09
Posted by chobocho
Coding/CPP 삽질기2023. 6. 13. 23:50
Coding/CPP 삽질기2023. 6. 9. 23:14
#include <iostream>

const int MAX_SIZE = 10;

void update(int* TREE, int idx, int value) {
    for (++idx; idx <= MAX_SIZE+1; idx += (idx & -idx))
        TREE[idx] += value;
}

int sum(int *TREE, int s) {
    int r = 0;
    for (++s; s > 0; s &= (s-1))
        r += TREE[s];
    return r;
}

int main(int argc, char **argv) {
    int TBL[MAX_SIZE] = {0};
    int TREE[MAX_SIZE+1] = {0, };

    for (auto i = 0; i < MAX_SIZE; i++) {
        TBL[i] = i+1;
        update(TREE, i, TBL[i]);
    }

    // GET SUM from 1 ~ N
    for (auto i = 0; i < MAX_SIZE; i++)
        std::cout << sum(TREE, i) << ", ";
    std::cout << std::endl;
    
    return 0;
}
Posted by chobocho
Coding/CPP 삽질기2023. 6. 7. 00:59

문득 기초 코딩(?) 실력이 떨어진것 같아서, 프로그래머스의  Level 0 문제를 C로 모두 풀어 보았다.

중간 중간 예상외로 막히는(?) 문제를 만나면서, 잊고 있었던 것들이 많았다는 걸 배웠다.

심심하신 분들에게 추천합니다.

'Coding > CPP 삽질기' 카테고리의 다른 글

[CPP] 펜윅 트리 (Fenwick Tree)  (0) 2023.06.09
[ChatGPT에게 묻다] Fast sqrt 함수  (0) 2023.02.26
별 그리기  (0) 2021.06.08
Posted by chobocho
Coding/CPP 삽질기2023. 2. 26. 20:08

요즘 핫 한 ChatGPT를 유료 결제 하고, 이것 저것 질문을 해보았습니다.

Q) please explain about the John Carmack's q_sqrt function as Korean

A) 존 카맥의 q_sqrt 함수는 양의 부동 소수점 수에 대한 빠른 제곱근 근사치 함수입니다. 이 함수는 제한된 범위의 입력에 대해 빠르고 정확하게 작동하도록 설계되었습니다.

다음은 q_sqrt 함수의 C 코드입니다:

float q_sqrt(float x) {
    int i = *(int *)&x;
    i = 0x1fbd1df5 + (i >> 1);
    return *(float *)&i;
}

q_sqrt 함수는 x라는 하나의 인자를 취합니다. 이 인자는 우리가 제곱근을 계산하려는 양의 부동 소수점 수입니다. 함수는 x의 근삿값인 제곱근을 반환합니다.

함수는 먼저 포인터 캐스트를 사용하여 float 인자를 int로 변환합니다. 그런 다음 부동 소수점 수의 정수 표현은 하나의 비트만큼 오른쪽으로 시프트됩니다.

그 다음 0x1fbd1df5라는 정수 값이 오른쪽으로 시프트된 정수 값에 더해집니다. 이 값은 제곱근 함수의 근사치를 제한된 범위의 입력에 대해 얻기 위해 선택된 매직 상수입니다. 덧셈의 결과는 포인터 캐스트를 사용하여 다시 float로 변환되고 반환됩니다.

q_sqrt 함수는 [0, 2^30] 범위의 입력에 대해 빠르고 정확합니다. 그러나 입력이 커질수록 정확도가 낮아집니다. 이 함수는 표준 라이브러리의 sqrt 함수보다 정확도가 떨어지지만 더 빠르며 근사 오차는 여전히 많은 응용 프로그램에 충분히 작습니다.


  ChatGPT 가 알려준 코드는 매우 잘 돌아가는데, 코드가 이해가 가지 않아서, 이리 저리 구글링을 해보았다.

 먼저 그 유명한, 존 카맥의 고속 역 제곱근을 코드를 보고,  

https://ko.wikipedia.org/wiki/%EA%B3%A0%EC%86%8D_%EC%97%AD_%EC%A0%9C%EA%B3%B1%EA%B7%BC

 

고속 역 제곱근 - 위키백과, 우리 모두의 백과사전

위키백과, 우리 모두의 백과사전. 고속 역 제곱근(高速逆-根, fast inverse square root)은 때때로 Fast InvSqrt()나 16진수 0x5f3759df라고도 하는, IEEE 754 부동소수점 체계의 32비트 실수에 대한 제곱근의 역

ko.wikipedia.org

아래와 같은 방식으로  sqrt(x)를 구할 수 있다는 것을 알 수 있다.

그래서 아래와 같은 코드가 나오게 됩니다.

 i = 0x1fbd1df5 + (i >> 1);

그럼 이 코드를 실행 보면,

#include <iostream>

float q_sqrt(float x) {
    int i = *(int *)&x;
    i = 0x1fbd1df5 + (i >> 1);
    return *(float *)&i;
}

float q_sqrt_new_magic_number(float x) {
    int i = *(int *)&x;
    i = 0x1fbd3ee7 + (i >> 1);
    return *(float *)&i;
}


int main(int argc, char **argv) {
    std::cout << q_sqrt(9) << std::endl;
    std::cout << q_sqrt_new_magic_number(9) << std::endl;
    return 0;
}

존 카맥 형님의 매직 넘버를 사용한게 오차률이 낮습니다. ㅠㅜ

결론:   ChatGPT가 똑똑 합니다.


 

 

'Coding > CPP 삽질기' 카테고리의 다른 글

프로그래머스 사이트 기초 문제 풀기  (0) 2023.06.07
별 그리기  (0) 2021.06.08
Stack과 Heap  (0) 2021.02.25
Posted by chobocho
Coding/CPP 삽질기2021. 6. 8. 22:21

오픈 챗에서 누구나 다 해보는 "별 그리기" 문제를 물어 보길래, 한 번 짜봤다.

#include <stdio.h>
#include <string.h>

int main(int argc, char **argv) {
    char star[] = "*****";

    for (int i = 0; i < strlen(star); i++) {
         printf("%s\n", &star[strlen(star)-i-1]);
    }

    return 0;
}

 

chobocho@Chobocho-Mint:~/github/cpp_study/src/sandbox$ ./a.out
*
**
***
****
*****

'Coding > CPP 삽질기' 카테고리의 다른 글

[ChatGPT에게 묻다] Fast sqrt 함수  (0) 2023.02.26
Stack과 Heap  (0) 2021.02.25
[C] Binary search  (0) 2020.12.06
Posted by chobocho
Coding/CPP 삽질기2021. 2. 25. 23:52

1. Stack과 Heap 영역에 변수 생성 시간 테스트

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_COUNT 1000000


void do_nothing_test() {
    clock_t start = clock();

    for (int i = 0; i < MAX_COUNT; i++)
    ;

    printf("Empty: %f\n", ((float)(clock()-start)/CLOCKS_PER_SEC));
}


void stack_create_test() {
    clock_t start = clock();

    for (int i = 0; i < MAX_COUNT; i++) {
        int arr[10] = { 0, };
    }

    printf("Stack: %f\n", ((float)(clock()-start)/CLOCKS_PER_SEC));
}


void heap_create_test() {
    clock_t start = clock();

    for (int i = 0; i < MAX_COUNT; i++) {
        int *arr = malloc(sizeof(int)*10);
        free(arr);
    }

    printf("Heap:  %f\n", ((float)(clock()-start)/CLOCKS_PER_SEC));
}

int main(int argc, char **argv) {
    do_nothing_test();
    stack_create_test();
    heap_create_test();
    return 0;
}

결과

chobocho@Chobocho-Mint:~/github/cpp_study/src/memory$ ./a.out
Empty: 0.003636
Stack: 0.003976
Heap:  0.015938

'Coding > CPP 삽질기' 카테고리의 다른 글

별 그리기  (0) 2021.06.08
[C] Binary search  (0) 2020.12.06
Quick sort  (0) 2017.07.13
Posted by chobocho
Coding/CPP 삽질기2020. 12. 6. 16:41

이진검색 설명:

ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%EA%B2%80%EC%83%89_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

 

이진 검색 알고리즘 - 위키백과, 우리 모두의 백과사전

위키백과, 우리 모두의 백과사전. 이진 검색 알고리즘(binary search algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여,

ko.wikipedia.org

구현 예제

#include <stdio.h>
#include <assert.h>


/*
 * high must be length of arr -1
 * /
int binary_search(int value, int low, int high, int* arr) {
	while (low <= high) {
		int mid = (low+high)/2;
		if (arr[mid] == value) {
			return mid;
		} else if (arr[mid] < value) {
			low = mid+1;
		} else {
			high = mid-1;
		}
	}
	return -1;
}

/*
 * high must be length of arr -1
 * /
int binary_search_recursive(int value, int low, int high, int *arr) {
	if (low > high) return -1;

	int mid = (low + high) / 2;
	if (arr[mid] == value) {
		return mid;
	} else if (arr[mid] < value) {
		return binary_search_recursive(value, mid+1, high, arr);
	} else {
		return binary_search_recursive(value, low, mid-1, arr);
	}
}

void test() {
	int number[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};

	int arr_size = (int) sizeof(number)/sizeof(int);

	assert(binary_search(11, 0, arr_size-1, number) == 11);
	assert(binary_search(2, 0, arr_size-1, number) == 2);
	assert(binary_search(12, 0, arr_size-1, number) == -1);
	
	assert(binary_search_recursive(11, 0, arr_size-1, number) == 11);
	assert(binary_search_recursive(2, 0, arr_size-1, number) == 2);
	assert(binary_search_recursive(12, 0, arr_size-1, number) == -1);
}

int main(int argc, char **argv) {
    test();
    return 0;
}

 

'Coding > CPP 삽질기' 카테고리의 다른 글

Stack과 Heap  (0) 2021.02.25
Quick sort  (0) 2017.07.13
Bit 연산 정리  (0) 2016.08.20
Posted by chobocho
Coding/CPP 삽질기2017. 7. 13. 01:09

#include <iostream>

using namespace std;


class CPoint {

public:

void set(int a_, int b_) { a = a_; b = b_; }

bool small(const CPoint &p) {

unsigned long long int la = b;

unsigned long long int lb = p.a;

unsigned long long int lb2 = p.b;

unsigned long long int l = la * lb + lb2;

la = p.b;

lb = a;

lb2 = b;

unsigned long long int r = la * lb + lb2;

return l < r;

}

bool big(const CPoint &p) {

unsigned long long int la = b;

unsigned long long int lb = p.a;

unsigned long long int lb2 = p.b;

unsigned long long int l = la * lb + lb2;

la = p.b;

lb = a;

lb2 = b;

unsigned long long int r = la * lb + lb2;

return l > r;

}

int a, b;

};



void qsort(CPoint* arr, int start, int end) {

CPoint p = arr[(start + end) / 2];

int s = start;

int e = end;


while (s <= e) {

while (arr[s].small(p)) { s++; }

while (arr[e].big(p)) { e--; }

if (s <= e) {

CPoint t = arr[s];

arr[s] = arr[e];

arr[e] = t;

s++;

e--;

}

}


if (start < e) {

qsort(arr, start, e);

}

if (s < end) {

qsort(arr, s, end);

}

}


CPoint p[200001];


int main()

{

int TC = 0;

cin >> TC;


for (int tc = 1; tc <= TC; tc++) {

int N = 0;

cin >> N;

for (int i = 0; i < N; i++) {

cin >> p[i].a >> p[i].b;

}

qsort(p, 0, N - 1);

cout << "# " << tc << " " << N <<  endl;

for (int i = 0; i < N; i++) {

cout << p[i].a << " " << p[i].b << endl;

}

}


    return 0;

}



'Coding > CPP 삽질기' 카테고리의 다른 글

[C] Binary search  (0) 2020.12.06
Bit 연산 정리  (0) 2016.08.20
가장 넓은 직사각형 구하는 알고리즘 ( O(MN) )  (0) 2016.04.13
Posted by chobocho