programming

위키피디아에서는 아래와 같이 정의하고 있다.수학에서 조화수열는 등차수열의 역수를 취하여 형성되는 수열이다.조화수열의 일반항은 $\frac{1}{a+kd}$와 같다. 프로그래밍 문제에서 이 수열 내림의 합을 구하는 문제가 나오기도 한다. 이때 그 합은 아래와 같이 표현가능하다.$$\sum_{i=1}^{n}{\lfloor \frac{n}{i} \rfloor}$$여기서 이 수열을 그냥 1부터 n까지 구하게 된다면 시간복잡도가 n이다. 이때 10000/1001의 내림과 10000/1111의 내림이 9로 동일한 것을 알 수 있다. 이 성질을 이용하면 시간 복잡도가 sqrt(n)이 된다.그렇다면 n/i의 내림과 n/j의 내림이 같으면서 가장 큰 j를 찾고 n/i의 내림과 그 범위 (j-i+1)를 곱하면 되고 이 것..

tcache bin tcache_entry *e = (tcache_entry *) chunk2mem (p); if (__glibc_unlikely (e->key == tcache_key)) { tcache_entry *tmp; size_t cnt = 0; LIBC_PROBE (memory_tcache_double_free, 2, e, tc_idx); for (tmp = tcache->entries[tc_idx]; tmp; tmp = REVEAL_PTR (tmp->next), ++cnt) { if (cnt >= mp_.tcache_count) malloc_printerr ("free(): too many chunks detected in tcach..

size = chunksize (p); /* Little security check which won't hurt performance: the allocator never wrapps around at the end of the address space. Therefore we can exclude some size values which might appear here by accident or by "design" from some intruder. */ if (__builtin_expect ((uintptr_t) p > (uintptr_t) -size, 0) || __builtin_expect (misaligned_chunk (p), 0)) malloc_printerr..

(숫자)는 현재 중괄호가 몇 개나 쒸워져있는지를 나타낸다. 중괄호가 열리는 부분과 닫히는 부분에 각각 하나씩 있다. if (!checked_request2size (bytes, &nb)) { __set_errno (ENOMEM); return NULL; }먼저 요청 크기가 최소, 최대 크기 사이인지 확인한다.if (__glibc_unlikely (av == NULL)) { void *p = sysmalloc (nb, av); if (p != NULL) alloc_perturb (p, bytes); return p; }할당된 힙이 없을 시 새로운 힙을 할당한다. (1)if ((unsigned long) (nb) 요청 크기가 fastbin의 크기보다 작다면..

먼저 chunk, bin, arena에 대해서 정리하고 시작하겠다. glibc 2.35 버전을 분석했다. _int_malloc, _int_free 소스코드: https://elixir.bootlin.com/glibc/glibc-2.35/source/malloc/malloc.c#L3769해당 링크의 아래쪽으로 계속가면 _int_free도 있다.chunkmalloc() 함수가 호출됨으로서 할당받는 영역 struct malloc_chunk { INTERNAL_SIZE_T mchunk_prev_size; /* Size of previous chunk (if free). */ INTERNAL_SIZE_T mchunk_size; /* Size in bytes, including overh..

1 베이즈 정리 베이즈 정리는 두 확률 변수의 사전 확률과 사후 확률 사이의 관계를 나타내는 정리로 사전 확률에서 추가로 얻은 정보로 사후 확률을 구할 수 있다.$$ P(A|B) = \frac{P(B|A)P(A)}{P(B)} $$ 수식은 위와 같고, P(A|B)가 사후 확률, P(A)가 사전 확률이고, 나머지 확률이 추가로 얻은 정보라고 보면 된다.  참고로 베이즈 정리는 워낙 부피가 커져서 베이지안 통계학으로 하나의 통계 분야가 되었다.2 예시 실제 예시는 아니고, 이해를 돕기위해 하나 만들겠다. A를 시험 평균 성적이 80점 이상인 학생으로 두고, B를 학원을 다니는 학생으로 두겠다.  총 100명의 학생중 A인 학생은 40명, B인 학생은 60명, A이면서 B인 학생은 30이라 할 때, P(A)는 ..

고3 때 했던 논문리뷰용어사전 attention: 문맥에 따라 집중할 단어를 결정하는 방식, 행렬곱을 이용해 구현한다.  self-attention: 한 문장이 있을 때 문장에서 각 단어들의 관계를 찾는 방법  transformer: attention 기법만을 적극적으로 활용하여 만든 모델   softmax: 입력받은 값을 모두 0~1사이의 값으로 정규화하면서 값들의 총합이 1이 되도록 만드는 함수, 확률을 구하는 함수이기도 하다.  mask: 참조하고 싶지 않은 단어는 미리 지워두는 함수, 지금 해석되지 않은 단어를 미리 참조할 필요는 없기에 사용된다. 해석할 필요없는 단어에 -에 해당하는 값을 넣어 구현한다.  embedding: 특정 단어나 문장을 벡터로 만든 것, 컴퓨터의 경우는 자연어를 이해할 ..

1 객체지향 객체지향은 여러 독립적인 부품들의 조합, 즉 객체들의 유기적인 협력과 결합으로 파악하고자 하는 컴퓨터 프로그래밍이다. 객체지향의 4가지 특징은 추상화, 상속, 다형성, 캡슐화이다.2 추상화 추상화란 본질만을 추출하는 것이라고 보면 된다.  예를 들어 사람 4명이 있다면 서로 이름, 나이 , 키와 몸무게 등이 다르겠지만 추상화하면 모두 인간이라는 점이 같을 것이다. 그러니 인간 클래스를 만들어 객체의 공통적인 속성과 기능을 정의한다.  3 상속 상속이란 기존의 클래스를 재활용하여 새로운 클래스를 작성하는 방법이다. 이 때 기존 클래스를 부모 클래스라 하고, 새로운 클래스를 자식 클래스라고 한다.  메서드 오바라이딩으로 예를 들면 게임 캐릭터가 적과 플레이어가 있을 때 둘 다 이동을 하니까 인간..

1 컴파일러 컴파일러는 파일 전체를 기계어로 번역시키는 프로그램이다. 컴파일 과정은 총 4단계이다.  처음으로 전처리 단계이다. 전처리 단계에는 전처리기 매크로나 주석을 처리한다. 다음으로 컴파일 단계이다. 컴파일 단계에는 각종 소스 코드를 어셈블리 명령어로 번역한다. 다음으로 어셈블 단계이다. 어셈블 단계에는 어셈블리 코드를 기계어로 번역한다. 마지막으로 링킹 단계이다. 링킹 단계에는 번역한 기계어 코드를 한 곳에 모아 실행 파일로 만든다.   대표적인 예로 c언어가 컴파일러를 사용한다.2 인터프리터 인터프리터는 한 줄씩 기계어로 번역시켜 바로 실행하는 프로그램이다. 그래서 인터프리터의 경우에는 따로 exe파일을 만들지 않고, 바로 실행이 된다.  인터프리터의 경우에는 실행 시 컴파일러보다 느리다. 왜..

1 라이브러리 라이브러리는 주로 소프트웨어를 개발할 때 컴퓨터 프로그램이 사용하는 비휘발성 자원의 모임이다. 위키백과에서 들고 왔는데 너무 어렵게 설명해서 쉽게 말하자면 자주 사용되는 코드들을 작성해서 모아놓은 것이 라이브러리라고 알면 되겠다.  예를 들자면 python에서는 import로 들고 오는 것과 c에서는 include로 들고 오는 것이 라이브러리이다.2 프레임워크 프레임워크는 소프트웨어나 시스템 등을 쉽게 개발하고 구축할 수 있도록 마련되어 있는 구조이다.  예를 들자면 django나 java spring 등이 있다. 3 차이점 라이브러리와의 차이점은 프레임워크는 정해진 틀에서 만들게 하고, 라이브러리는 몇 가지 기능만 필요한 것을 가져와 사용할 수 있도록 제공한다. 그리고 프레임워크는 라이브..