'Coding/CPP 삽질기'에 해당되는 글 38건

  1. 2021.02.25 Stack과 Heap
  2. 2020.12.06 [C] Binary search
  3. 2017.07.13 Quick sort
  4. 2016.08.20 Bit 연산 정리
  5. 2016.04.13 가장 넓은 직사각형 구하는 알고리즘 ( O(MN) )
  6. 2016.04.13 printf로 디버깅 하기
  7. 2016.03.30 C++ 컴파일러
  8. 2016.03.17 Lambda function (1)
  9. 2016.03.16 Lambda function
  10. 2016.03.03 짝수만 출력하기
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 삽질기' 카테고리의 다른 글

Stack과 Heap  (0) 2021.02.25
[C] Binary search  (0) 2020.12.06
Quick sort  (0) 2017.07.13
Bit 연산 정리  (0) 2016.08.20
Posted by chobocho
TAG Heap, Stack

댓글을 달아 주세요

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
[C] Binary search  (0) 2020.12.06
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
Quick sort  (0) 2017.07.13
Bit 연산 정리  (0) 2016.08.20
가장 넓은 직사각형 구하는 알고리즘 ( O(MN) )  (0) 2016.04.13
Posted by chobocho

댓글을 달아 주세요

Coding/CPP 삽질기2016. 8. 20. 12:49

arr[k >> 5] |= (1 << (k & 31));

arr[k >> 3] |= (1 << (k & 7));

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

Quick sort  (0) 2017.07.13
Bit 연산 정리  (0) 2016.08.20
가장 넓은 직사각형 구하는 알고리즘 ( O(MN) )  (0) 2016.04.13
printf로 디버깅 하기  (0) 2016.04.13
Posted by chobocho

댓글을 달아 주세요

Coding/CPP 삽질기2016. 4. 13. 18:00

가장 넓은 직사각형 구하는 알고리즘 ( O(MN) )


/*
From :
http://stackoverflow.com/questions/7245/puzzle-find-largest-rectangle-maximal-rectangle-problem
*/

int findMaxRect (int rect[XSIZE][YSIZE]) {
	int ret = 0;
	unsigned int x = 0, y = 0, k = 0;
	int sum[YSIZE+1] = { 0, };
	int stack[YSIZE][2] = { 0, };
	int stIdx = -1;
	int width = 0;
	int y0 = 0, w0 = 0, tempArea = 0;
	
	for ( x = 0; x < XSIZE; ++x ) { 
		for ( y = 0; y <= YSIZE; ++y ) {
			sum[y] = rect[y][x] ? ++sum[y] : 0;
		}
		sum[YSIZE] = 0;
		width = 0;
		stIdx = -1;
		for ( y = 0; y <= YSIZE; ++y) {
			if ( sum[y] > width ) {
				stack[++stIdx][0] = y;
				stack[  stIdx][1] = width;
				width = sum[y];				
			} 
			else if ( sum[y] < width ) {

				while(1) {
					y0 = stack[stIdx  ][0];
					w0 = stack[stIdx--][1];
					tempArea =  width * (y - y0);
				  
					ret = tempArea > ret ? tempArea : ret;

					width = w0;
					if( sum[y] >= width) break;
				} 
				width = sum[y];
				if ( width != 0 ) {
					stack[++stIdx][0] = y0;
					stack[  stIdx][1] = w0;	
				}
			}
		}
	}	
	
	return ret;
}


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

Bit 연산 정리  (0) 2016.08.20
가장 넓은 직사각형 구하는 알고리즘 ( O(MN) )  (0) 2016.04.13
printf로 디버깅 하기  (0) 2016.04.13
C++ 컴파일러  (0) 2016.03.30
Posted by chobocho

댓글을 달아 주세요

Coding/CPP 삽질기2016. 4. 13. 17:25

#define DEBUG


#ifdef DEBUG

    #define cprintf(...) printf(__VA_ARGS__)

#else

    #define cprintf(...) 

#endif



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

가장 넓은 직사각형 구하는 알고리즘 ( O(MN) )  (0) 2016.04.13
printf로 디버깅 하기  (0) 2016.04.13
C++ 컴파일러  (0) 2016.03.30
Lambda function  (1) 2016.03.17
Posted by chobocho
TAG CPP, Debug, printf

댓글을 달아 주세요

Coding/CPP 삽질기2016. 3. 30. 00:09

무료 C++ 컴파일러



1. 구름 IDE ( https://ide.goorm.io/ )

웹기반 IDE 이며, 기본 사용은 무료 이다.

웹 브라우져만 있으면 손쉽게 다양한 언어로 개발이 가능 하다.




2. C++ shell ( http://cpp.sh )

무료이며, 웹브라우져만 띄우면 짧은 코드를 쉽게 실행 할 수 있다.



3. Cygwin ( http://cygwin.com/install.html )

자세한 설명은 Cygwin 홈페이지를 참고하시면 됩니다.



4. Visual studio Express ( https://www.visualstudio.com/ko-kr/products/visual-studio-community-vs.aspx )

너무 유명하므로 설명은 생략 합니다.


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

printf로 디버깅 하기  (0) 2016.04.13
C++ 컴파일러  (0) 2016.03.30
Lambda function  (1) 2016.03.17
Lambda function  (0) 2016.03.16
Posted by chobocho

댓글을 달아 주세요

Coding/CPP 삽질기2016. 3. 17. 00:56

[ C++ Lambda 함수 설명 ]

https://msdn.microsoft.com/ko-kr/library/dd293608.aspx

https://msdn.microsoft.com/ko-kr/library/dd293599.aspx

http://en.cppreference.com/w/cpp/language/lambda


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

C++ 컴파일러  (0) 2016.03.30
Lambda function  (1) 2016.03.17
Lambda function  (0) 2016.03.16
짝수만 출력하기  (0) 2016.03.03
Posted by chobocho
TAG C++, CPP, Lambda

댓글을 달아 주세요

  1. https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life

    2016.03.17 01:07 신고 [ ADDR : EDIT/ DEL : REPLY ]

Coding/CPP 삽질기2016. 3. 16. 01:02

#include <iostream>

using namespace std;


int main()

{

   int num = 2;

  

   auto sum = [](int n) -> int{ return n*n; }(num);

   

   cout << num << " " << sum << endl;

   

   return 0;

}



2 4


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

Lambda function  (1) 2016.03.17
Lambda function  (0) 2016.03.16
짝수만 출력하기  (0) 2016.03.03
Couple  (0) 2015.12.23
Posted by chobocho
TAG CPP, Lambda

댓글을 달아 주세요

Coding/CPP 삽질기2016. 3. 3. 00:04

#include <iostream>

using namespace std;


int main()

{

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

       i % 2 ||  cout << i << endl;   

    }

    return 0;

}




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

Lambda function  (0) 2016.03.16
짝수만 출력하기  (0) 2016.03.03
Couple  (0) 2015.12.23
사각형 개수 구하기  (0) 2014.11.12
Posted by chobocho
TAG CPP

댓글을 달아 주세요