Radix Sort
MSD(Most-Significant Digit)
가 아닌 LSD(Least-Significant Digit)
부터 비교해야함
최소 공통 조상 (LCA : Lowest Common Ancestor)
찾는 방법
- 두 정점에 대해 루트 노드 부터 본인의 부모까지 정점을 각각 리스트로 저장한다.
- 리스트에서 정점을 하나씩 꺼내서 같은 지 확인한다.(리스트 길이가 다르면 긴 리스트의 정점을 이동한다.)
시스템 버스
- 제어버스(Control Bus)
- 주소버스(Adress Bus)
- 데이터버스(Data Bus)
※ 제어버스, 데이터버스는 양방향 버스, 주소버스는 단방향 버스
중앙처리장치(CPU) 구성
- 산술논리연산장치(ALU)
- 제어장치 → 명령어 해석
- 레지스터
캐시메모리
- 속도가 빠른 장치와 느린 장치에서 속도 차이에 따른 병목현상을 줄이기 위한 메모리
- L1, L2, L3 (각각 CPU, CPU-메모리 사이, 메인보드에 위치)
- CPU가 요청한 데이터가 캐시에 있으면
Cache Hit
, 없어서 DRAM에서 가져오면 Cache Miss
캐시 미스
Cold miss : 해당 메모리를 처음 불러서 나는 미스
Conflict miss : A와 B 데이터가 같은 캐시메모리에 할당돼있어서 나는 미스
Capacity miss : 메모리 공간이 부족해서 나는 미스
지역성
시간 지역성
: 한번 참조된 변수는 다음에 다시 참조될 확률이 높다.
공간 지역성
: 참조된 데이터 근처의 데이터는 잠시후 또 사용될 가능성이 높다.