[04.17/week06]TIL

오늘 하루 요약

새로 배우게 된 것

• C 언어 방향성
• RB Tree 개념 및 노드 삽입

C언어 강의

📌 C 언어의 사용 목적과 특징

✅ C 언어는 어떻게, 왜 사용하는가?

• 하드웨어와 가까운 언어: 시스템 프로그래밍에 적합
• 세밀한 메모리 제어 가능
  • 다양한 타입(short, int, long, signed, unsigned 등) 지원
  • 상황에 맞는 타입 선택으로 메모리 절약 가능
  • 심지어 bit 단위 제어도 가능

✅ 파이썬과 비교했을 때

항목	C	Python
실행 방식	컴파일러	인터프리터
정수형 크기	아키텍처 의존	기본적으로 22B 이상 (큰 오버헤드)
메모리 효율	높음	낮음
타입 수	다양	상대적으로 단순

예시: 카메라 같이 메모리 제약이 있는 디바이스에서는 C가 훨씬 적합!

---

📏 데이터 타입과 메모리 크기

🔹 C 언어의 데이터 타입 크기

• C는 타입 크기가 고정되어 있지 않다 → 아키텍처에 따라 다름
• 예시:
  • int: 4B (일반적으로)
  • short: 2B
  • char: 1B
  • pointer: 아키텍처에 따라 4B 또는 8B (32bit vs 64bit)

🔹 크기 확인은 필수!

• 특히 포인터 연산 시 매우 중요
• 크기가 고정이 아니기 때문에 이식성이 떨어질 수 있음
• 크기 확인 방법:

  #include <stdio.h>
  printf("%zu", sizeof(int));

---

📘 C Trap and Pitfalls (주의할 점)

⚠️ 흔한 실수들

if(x = y) // 의도는 비교지만, 대입임!

y = x/*p  // => 뒤가 주석 처리됨 (의도치 않은 결과)

if(flags & FLAG != 0) // 우선순위 실수

• 해결: 괄호로 의도 명확히

  if((flags & FLAG) != 0)

while(c = getc(in) != EOF)
    putc(c, out);

• 해결: 괄호로 분리

  while((c = getc(in)) != EOF)
      putc(c, out);

🧠 논리 연산자와 우선순위

• 연산자 우선순위가 우리가 생각하는 것과 다를 수 있음
• 괄호로 우선순위를 명확하게 표현

⛔ 매크로 주의

#define SQUARE(x) x * x

SQUARE(1 + 2) // 1 + 2 * 1 + 2 = 5 ??

• 해결:

  #define SQUARE(x) ((x) * (x))

---

🧭 Pointer (포인터)

기본 문법

int n = 10;
int *p = &n;

malloc과 포인터 타입

int *p = (int*)malloc(sizeof(int) * 5);

• malloc(20)은 20바이트 요청이지만,
  • int의 크기가 4B라고 가정하면 5개
  • 하지만 아키텍처 따라 다르기 때문에 sizeof 사용 필수
• malloc은 void* 반환 → 적절한 타입으로 캐스팅 필요

포인터 타입이 중요한 이유

• p + 1은 p가 가리키는 타입 크기만큼 이동
• 즉, 타입이 있어야 "얼마만큼" 가져올지 해석 가능

---

📦 Struct와 메모리

Struct란?

• 여러 타입을 하나로 묶은 사용자 정의 자료형

struct Example {
    int a;
    char b;
    double c;
};

• 내부 메모리 정렬(Padding)에 따라 실제 크기는 예상과 다를 수 있음

Pointer vs 주소 크기

• 포인터는 "주소를 담는 타입" → 주소 크기는 아키텍처에 따라 다름
  • 32bit → 4B
  • 64bit → 8B

서로 다른 타입으로 같은 주소를 참조한다면?

• 접근 방식에 따라 전혀 다른 값처럼 해석될 수 있음

---

🧨 Segmentation Fault?

• 접근하면 안 되는 메모리에 접근했을 때 발생
• 주로 발생하는 원인:
  • 초기화되지 않은 포인터
  • 잘못된 메모리 연산
  • 해제된 메모리에 접근

---

💡 기타 팁

• 중괄호(Brace) 사용 습관 들이기 → 코드 가독성 및 버그 예방
• switch 문에서는 break 필수
• else는 가장 가까운 if에만 붙는다
• short-circuit 평가 이해:

  if (a && b) {...}

  • a가 false면 b는 아예 평가하지 않음

결국, clarity가 중요하다는 핵심...

RB TREE

• BST(이진 탐색 트리)중 하나

이건 왜 쓸까?

균형을 잡는데는 이유가 다 있다.
한쪽으로 치우친 트리인 경우 O(N)의 탐색 시간, 이를 RB TREE로 균형 잡으면 O(log N)으로 단축 시키니까 쓰는 것.

RB TREE의 다섯가지 속성

1. 모든 노드는 RED or BLACK

2. Root 는 BLACK

NIL?

• 존재하지 않음
• 자녀가 없다면, 자녀를 NIL로 표시
• 값이 없는 노드
• RB 트리에서 LEAF 노드는 NIL

3. 모든 NIL 노드는 Black

4. RED의 자녀들은 Black = RED는 연속적으로 존재 불가

5. 임의의 노드에서 자손 NIL 노드들까지 가는 경로들의 BLACK 수는 동일

Black Height

• 노드 X에서 임의의 NIL 노드까지 내려가는 경로에서의 BLACK노드 개수
  • 자기자신은 카운트 제외
  • 5번 속성을 만족해야 성립 ⇒ 이걸 만족하지 못하면 Black Height 개념 자체가 존재못함

삽입

결국 삽입에서 회전을 하고 색을 바꾸는 그 과정은 저 Black Height가 성립하지 않기 때문.

1. RED 삽입 후 2번 속성(루트 = Black) 위반시 ⇒ 루트를 블랙으로 변경

왜 삽입하는 노드는 RED일까? ⇒ 5번 속성 만족 위함.

블랙을 삽입시, 임의의 NIL 노드까지ㅏ 가는 경로에 블랙이 추가, 5번 속성이 자연스럽게 위반, 따라서 레드 넣어서 이를 방지

2. RED 삽입 후 4번 속성(RED의 자녀는 BLACK) 위반시(CASE3)

• 삽입된 RED
  • 부모의 왼쪽 자녀
  • 부모도 RED
  • 부모의 형제는 BLACK

부모와 할아버지의 색 교환 + 할아버지 기준 오른쪽 회전

3. RED 삽입 후 4번 속성(RED의 자녀는 BLACK) 위반시(CASE2)

• 삽입된 RED

  • 부모의 오른쪽 자녀
  • 부모도 RED
  • 부모의 형제는 BLACK

  부모 기준 왼쪽 회전 + 부모와 할아버지의 색 교환 + 할아버지 기준 오른쪽 회전(CASE3)

3. RED 삽입 후 4번 속성(RED의 자녀는 BLACK) 위반시(CASE1)

• 삽입된 RED
  • 부모가 RED
  • 부모의 형제도 RED

부모와 부모 형제 노드 색 변경 + 할아버지 색 변경 + **할아버지 노드**에서 다시 확인 시작

• 할아버지 색이 바껴서 RED가 되었을때
  • 4번 속성을 만족하는지 다시 체크

공부하다가 아쉬운 점

이걸 내가 코드로 구현할 수 있을까...?