[잊지 말 것]

[비고] 상시 추가중

---

 

---

0. 기타

[실수 표현 유의점]

 컴퓨터는 정확한 십진수의 실수 값을 이진수로 표현 할 수 없어 근사적으로 표현한다. (오차에 주의 할 것)
 - 실수 자료형의 유효자릿수(10진수 기준) : 32비트 - 6, 64비트 -15

 

---

1. 복잡도

[시간 복잡도]

• O(Big-Oh) 표기
   복잡도의 점근적 상한
   최대 시간
   O(logⁿ), O(n) 좋다
   O(nlogⁿ) 이게 최선이었니
   O(n²) 아 이건 좀;
   O(n³), O(2ⁿ), O(n!) 뭐하는 새끼야 이거
• Ω (Big-Omega) 표기
   복잡도의 점근적 하한
   최소 시간
• θ(Theta) 표기
   O와 Omega 표기가 같은 경우

 

[공간 복잡도]

메모리 공간

 

---

2. 비트연산

연산속도 향상, 메모리 절약 가능

[1<<n의 의미]

• 1부터 시작해 n만큼 왼쪽으로 비트 이동
  ex) 1<<0 ? 0001 = 1
       1<<1 ? 0010 = 2
       1<<2 ? 0100 = 4 
       1<<3 ? 1000 = 8
• 2 의 n 제곱 값
• 원소가 n개일 경우의 모든 부분집합(power set)의 수

 

[비트연산 활용]

• i & ( 1<<j )
   수 i의 j번째 위치의 비트가 1인지 0인지 판별 
   (0이 아닌) i와 j번째 비트를 AND연산 함으로 j가 0일 경우 0, 0이 아닐 경우 1이 나온다
• i<<n
  수 i에 2의 n제곱을 곱한 값
• ~i+1
  수 i의 2의 보수 즉 부호 반전 값

 

[byte alignment]

structure byte padding 
 구조체 멤버들 사이에 임의의 공간이 생기는 현상

 

다음과 같이 구조체가 선언되면 멤버틀의 크기 총 합은 8바이트 이지만 패딩 바이트가 추가되어 12 바이트가 할당되며

Data1		Data2
Data3
Data4

다음과 같이 선언할 경우 8바이트만 사용하게 된다.

Data1	Data4	Data2
Data3

 

 

따라서 변수 선언 순서에 따라 구조체 메모리 크기를 줄일 수 있다

 

---