[크래프톤 정글 3기] 12/19(화) TIL

ClassBinu·2023년 12월 19일

크래프톤 정글 3기 TIL

목록 보기

64/120

08:40 입실

알고리즘 복습

재귀 합

#include <stdio.h>

int sum(int n)
{
  if (n == 0)
  {
    return 0;
  }
  return sum(n-1) + n;
}

int main()
{
  int x = 10;
  int result = sum(x);
  printf("%d\n", result);
  return 0;
}

재귀 팩토리얼

#include <stdio.h>

int fact(int n)
{
  if (n == 0)
  {
    return 1;
  }
  return fact(n-1) * n;
}

int main()
{
  int x = 10;
  int result = fact(x);
  printf("%d\n", result);
  return 0;
}

재귀 m^n

#include <stdio.h>

int power(int m, int n)
{
  if (n == 0)
  {
    return 1;
  }
  return power(m, n-1) * m;
}

int main()
{
  int result = power(2, 10);
  printf("%d\n", result);
  return 0;
}

// 개선 버전
int power(int m, int n)
{
  if (n == 0)
  {
    return 1;
  }

  if (n % 2 == 0)
  {
    return power(m * m, n / 2);
  }
  else
  {
    return m * power(m * m, (n-1) / 2);
  }
}

int main()
{
  int result = power(2, 10);
  printf("%d\n", result);
  return 0;
}

재귀 피보나치

#include <stdio.h>

int fib(int n)
{
  if (n <= 1)
  {
    return n;
  }

  return fib(n-2) + fib(n-1);
}

int main()
{
  int result = fib(11);
  printf("%d\n", result);
  return 0;
}

// 메모이제이션(-> 동적 프로그래밍)
int f[10];

int fib(int n)
{
  if (n <= 1)
  {
    f[n] = n;
    return n;
  }
  else
  {
    if (f[n - 2] == -1)
    {
      f[n - 2] = fib(n - 2);
    }
    if (f[n - 1] == -1)
    {
      f[n - 1] = fib(n - 1);
    }
    return f[n - 2] + f[n - 1];
  }
}

int main()
{
  for (int i = 0; i < 10; i++)
  {
    f[i] = -1;
  }
  int result = fib(10);
  printf("%d\n", result);
  return 0;
}

메모이제이션은 테이블 값을 기준으로 계산함.
만약 테이블 값이 없으면 함수를 호출해서 테이블을 업테이트!

배열

C에서 배열의 일부에만 값을 할당하면 나머지는 0으로 초기화됨.

arr[5] = {1}; // 나머지는 0으로 초기화
// {1, 0, 0, 0, 0}

배열 크기 늘리기

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

int main()
{
  int p[5] = {2, 4, 6, 8, 10};
  int *q = (int *)malloc(10 * sizeof(int));

  for (int i = 0; i < 5; i++)
  {
    q[i] = p[i];
  }

  for (int i = 0; i < 10; i++)
  {
    printf("%d ", q[i]);
  }

  return 0;
}

Pintos

해시 테이블 초기화

void
supplemental_page_table_init (struct supplemental_page_table *spt) {
		hash_init(&spt->pages, page_hash, page_less, NULL);
}

unsigned
page_hash (const struct hash_elem *p_, void *aux UNUSED) {
  const struct page *p = hash_entry (p_, struct page, hash_elem);
  return hash_bytes (&p->va, sizeof p->va);
}

bool
page_less (const struct hash_elem *a_,
           const struct hash_elem *b_, void *aux UNUSED) {
  const struct page *a = hash_entry (a_, struct page, hash_elem);
  const struct page *b = hash_entry (b_, struct page, hash_elem);

  return a->va < b->va;
}