[CS 공부] 22.10.05

minyoon·2022년 10월 5일
0

CS공부

목록 보기
1/12

Radix Sort


MSD(Most-Significant Digit) 가 아닌 LSD(Least-Significant Digit) 부터 비교해야함

최소 공통 조상 (LCA : Lowest Common Ancestor)


찾는 방법

  1. 두 정점에 대해 루트 노드 부터 본인의 부모까지 정점을 각각 리스트로 저장한다.
  2. 리스트에서 정점을 하나씩 꺼내서 같은 지 확인한다.(리스트 길이가 다르면 긴 리스트의 정점을 이동한다.)

시스템 버스


  • 제어버스(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 : 메모리 공간이 부족해서 나는 미스

지역성


시간 지역성 : 한번 참조된 변수는 다음에 다시 참조될 확률이 높다.

공간 지역성 : 참조된 데이터 근처의 데이터는 잠시후 또 사용될 가능성이 높다.

profile
궁금한게 많은 사람🧐

0개의 댓글