[원격 강의] 쉽게 배우는 알고리즘(3), CS특강

• CS(Computer Science) 특강

• 컴퓨터 구조

  CPU ↔ MEM ↔ DISK

  

  폰노이만 구조

  • CPU : 메모리에 있는 명령들이 올라와서 ALU + Register을 통해 연산을 하게 됨

    

      n 개의 register로 구성되어있음 → 상태(state)
      
      레지스터 세트 = 코어,
      
      코어가 늘어날 수록 상태도 늘어남  ⇒ 발열 발생
      
      - 싱글코어 → 멀티코어?
          
          코어의 성능 향상엔 본질적인 한계 존재함.
          
          → multiple하게 해결하자! ⇒ 멀티코어
          
      - 멀티코어 : 멀티하게 state(Registers)를 가짐
      - 예) 프로그램 A → 클릭 → 내부적으로 CPU에게 이런 연산을 해주세요 라고 함 → CU가 그 명령을 fetch를 함. 그 후 해석해서 ALU에게 줌 →ALU 가 디코딩된 명령어로 산술논리연산을 함 → 프로그램에 전달해서 프로그램 메모리에 상태가 바뀐다

    • ALU(Arithmetic Logic Unit) : 산술 논리 장치
    • CU(Control Unit) : 제어 장치
    • Register
      • 특강 설명
        • Register ⇒ 업무 별로 나뉨
          • General-purpose : 범용
            • EAX, ECX, esp, eab
          • special-purpose : 특수용
            • PC레지스터(프로그램카운터) = 어떤 명령을 실행하고 나서 레지스터의 상태를 하나씩 증가시키는 것
      • 주소 레지스터(AR) : 읽거나 쓸 메모리 주소 저장
      • 프로그램 카운터(PC) : 다음 명령어의 메모리 주소 저장
      • 데이터 레지스터(DR) : 메모리에서 읽어온 데이터 저장
      • 명령어 레지스터(IR) : 메모리에서 읽어온 명령어 저장
      • 어큐뮬레이터(AC) : 연산에 사용되는 데이터 저장
    • Cache Memory CPU와 Disk의 거리를 좁히기 위해, 빈번하게 쓰이거나 가장 최근 사용한 것들은 캐시에 모아놔 최대한 가깝게 캐싱해서 쓰겠다. (cache coherence)
      

  • Memory : 임시 저장 공간

  • Disk : 저장소

• CPU의 언어

  • 고수준 프로그래밍 언어
    • A = 3 B = 4 C = A + B
      
  • 어셈블리 언어(Assembly language)
    • 니모닉
      • LOAD ADD STORE
    • [10][11] [12]
  • 기계어(Machine code)
    • 이진수로 되어있는 언어 (100110,0000001010…)
      
    • 컴퓨터가 이해할 수 있는 언어

• CPU와 프로그래머의 통신 방법

  • CPU는 기계어(binary)만 앎
  • 프로그래머가 직접 어셈블리어를 짤 수 있음(CPU Architecture에 따라 다름) → 여전히 개발자에게 허들이 있음
  • 그래서 나온 것이 프로그래밍 언어 : C, C++, Java … → 컴파일러(번역기)를 통해 컴파일 함수와 기계어를 연동 시킴
    • ISA(Instruction Set Architecture)
      • CISC(Complex instruction set computer)
      • RISC(Reduced Instruction Set Computer) : 효율적

• 명령어 수행

  • opcode
  • operand
    • imm
    • register
    • memory

⇒ 실행(ALU를 사용함)

• 알고리즘

• 정렬

  • 버블 정렬
  • 선택 정렬
  • 삽입 정렬
  • 병합 정렬
    • merge
    • mergeSort

• 스택(ex. 빨래통)

  • Last In First Out(LIFO) 자료구조
  • 기능
    • push(data) : 맨 위에 데이터 넣기
    • pop() : 맨 위에 데이터 뽑기
    • peek() : 맨 앞의 데이터 보기
    • isEmpty() : 스택이 비었는지 안 비었는지 여부 반환해주기

• 큐

  • 한 쪽 끝으로 자료를 넣고 반대 쪽에서는 자료를 뺄 수 있는 선형구조.
  • 기능
    • enqueue(data) : 맨 뒤에 데이터 추가하기
    • daqueue() : 맨 앞의 데이터 뽑기
    • peek() : 맨 앞의 데이터 보기
    • isEmpty : 큐가 비었는지 안 비었는지 여부 반환해주기

• 해쉬

  • 해쉬 테이블(Hash Table)(= 파이썬의 딕셔너리)
    • 데이터의 검색과 저장이 아주 빠르게 진행됨
    • 연관 배열 추가에 사용되는 자료 구조
    • 해시 함수를 사용해 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산함
  • 해쉬 함수(Hash Function)
    • 임의의 길이를 갖는 메시지를 입력해 고정된 길이의 해쉬값을 출력하는 함수
  • 충돌 해결하는 방식
    • chaining
    • 배열의 다음 남는 공간에 넣는 것
      python 콘솔창!!으로 왔다리갔다리 이용함

• 느낀점

  • 우선 용어에 익숙해지고자 빨리 듣고 있는데 그러다보니 메모를 따로 못해서 내용 적을 게 없다... 그렇다고 배운 걸 적자니 이해도 못해서 뭐가 뭔지....... 빨리 5주차까지 훑어보고 주말엔 파이썬 강의와 알고리즘 강의 전체를 주말에 다시 보는 게 목표,,, 목표가 너무 큰가? 그치만,, 이렇게 잡고 우선 해보고,,,,ㅠ 해내야함..
  • 연희튜터님께서 알고리즘 하는게 어렵다면 의사코드(pseudocode)를 하라고 말씀해주셨다!
    알고리즘을 수행할 때 한글로 먼저 내용을 써 놓고 코드를 짜면 훨씬 접근하기 쉽다고!! 다음에 해봐야겠다~~