TIL : CPU, 이진탐색, 재귀함수

Today, What I learned?

창민 튜터님의 CS특강과 계속되는 알고리즘과의 전쟁.. 🔥

오늘은 CS 특강에서 들은 CPU와 이진 탐색, 재귀함수에 대해서 정리한다!

특강 관련해서만 정리해도 양이 꽤 많긴 하지만.. 정리 시작! 👏

 

CPU

흔히들 컴퓨터 견적을 따질 때 많이 보는 것들 중에 하나로 익숙할 수 있다!..

Central Processing Unit의 약자로 중앙 처리 장치를 말한다. CPU는 컴퓨터의 두뇌라고 할 수 있다.

컴퓨터 시스템 전체를 제어하며 명령어를 수행하고 데이터를 처리한다.

처리장치와 제어장치로 구성되어 있고, CPU에는 캐시 같은 부가 장치도 포함되어 있다.

 

 

왜 CPU는 싱글 코어에서 멀티 코어가 되었는가?

결론적으로 싱글코어만으로 낼 수 있는 퍼포먼스에 한계가 있었기 때문에 멀티코어가 등장했다.

코어의 개수마다 가장 빠른 처리속도를 자랑하는 레지스터 세트가 증가하기 때문에 성능이 더욱 높아진다.

싱글코어의 본질적인 한계를 멀티코어는 열 손실 감소, 빠른 작업 수행으로 극복한다.

 

CPU의 구성

산술논리연산장치(ALU)

• 산술 연산장치, 논리 연산장치 등으로 구성되어 있다.
• 산술 연산 장치는 덧셈, 뺄셈 같은 산술 연산을 한다.
• 논리 연산 장치는 논리합, 논리곱 같은 논리 연산을 한다.

 

제어장치(CU)

• 모든 장치들의 종작을 지시하고 제어한다.
• 명령 레지스터에서 읽어 들인 명령어를 해독해서 신호를 보내 정확한 수행을 하도록 한다.

 

레지스터

범용 레지스터(general purpose register)

• 이 레지스터는 데이터를 일시적으로 저장하는 역할을 한다.
• EAX(산술 연산), EBX(메모리 주소 저장), ECX(반복 명령어(for, while문 같은) 수행) 등 총 8가지 종류로 구성되어 있다.
• 소규모의 일시적인 기억 장치다.
• 프로그램을 진행하며 가까운 시간 내에 사용할 데이터나 연산 결과를 일시적으로 기억할 때 사용한다.

 

특수 레지스터 (special purpose register)

특수 레지스터는 이름처럼 특수한 기능을 수행한다.

크게 세 가지로 나눠볼 수 있다.

 

1) 주소를 기억하는 레지스터

• 프로그램 카운터(PC)
  • 다음에 수행될 명령어의 주소를 가지고 있다.
  • 현재 처리하려는 데이터를 인출한 후에는 자동적으로 1을 증가한다. (카운터인 이유!)
• 이 외에도 기억 장치 주소를 임시 저장하는 MAR, SP(스택 포인터) 등이 있다.

 

2) 명령어 레지스터

가장 최근에 인출된 명령어를 가지고 있는 레지스터다.

 

3) 데이터를 기억하는 레지스터

• 기억장치 버퍼 레지스터(MBR)
  • 기억장치에 쓰일 데이터나 읽힐 데이터를 임시로 저장하는 기억장치
• 누산기(AC)
  • 데이터를 일시적으로 저장하는 레지스터

 

CPU 명령어 사이클

1. 명령어 인출 (fetch cycle) : 명령어 주소를 계산하고 그 주소에서 명령어를 가져오는 단계
2. 명령어 해독 (decode) : CU의 디코딩을 통해 명령어를 어떻게 수행할지 결정한다.
3. 데이터 인출 (data fetch) : Operand가 연산자의 대상의 위치를 계산해서 불러온다.
4. 명령어 실행 (execute) : 명령어를 ALU를 통해 실행한다.
5. 저장 : 수행된 연산 결과가 필요에 따라 레지스터나 기억 장치에 쓰인다.

 

캐시

• CPU와 디스크 사이의 거리를 좁히기 위해 빈번하게 사용되거나, 최근에 사용되었던 데이터들을 모아놓는 저장공간이다.
• 빠른 접근이 가능하다.
• 주기억장치인 디스크의 수행 속도 개선을 위한 방법 중 하나!

 

 

CPU와 프로그래머가 통신하는 과정

CPU는 기계어밖에 알지 못한다. 기계어는 0,1로만 이루어져 있기 때문에 사람이 알아보기 당연히 어렵다!..
이런 명령어를 사람이 좀 더 쉽게 알아보도록 하기 위해 만들어진 것이 어셈블리어.

어셈블리어는 컴퓨터와 일대일로 대응이 되어 빠른 수행 속도를 자랑하지만, 그만큼 배우기가 어렵고 유지보수가 힘들다는 점...

그래서 기계 중심의 언어인 저급 언어(Low-level Language)와 반대되는 사람 중심의 언어, 고급 언어(High-Level Language)가 등장했다.
LISP, BASIC, C, Java 등등!..

이런 고급 언어들은 컴파일러를 통해 번역 과정을 거쳐서 실행된다.

 

 

 

이진 탐색

이진 탐색은 탐색 방법 중 하나! 특정한 값을 찾기 위해 사용하는데, 일정한 규칙으로 정렬된 데이터만 탐색할 수 있다.
O(logN)의 시간 복잡도를 갖는다.

 

이진 탐색은 어떤 방식으로 진행되는가??

중간에 있는 임의의 값을 선택해서 찾고자 하는 값과 비교한다.
만약 이 중간값이 찾는 값보다 작으면 중간값을 기준으로 왼쪽, 더 크다면 오른쪽을 대상으로 다시 탐색하고 이 과정을 반복한다.

 

 

자바스크립트로 구현한 이진탐색

const finding_target = 14;
const finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16];

function solution(target, array) {
  let currentMin = 0;
  let currentMax = array.length - 1;
  let currentGuess = Math.floor((currentMin + currentMax) / 2);

  while (currentMin <= currentMax) {
    if (array[currentGuess] === target) {
      return true;
    } else if (array[currentGuess] < target) {
      currentMin = currentGuess + 1;
    } else {
      currentMax = currentGuess - 1;
    }

    currentGuess = Math.floor((currentMin + currentMax) / 2);
  }

  return false;
}

최솟값과 최댓값, 중간값을 설정한다.
최솟값이 최댓값보다 커지지 않을 때까지 타깃 값을 찾는 과정을 반복!..

만약 중간값이 타깃 값보다 작다면 최솟값을 1 추가하여 중간값을 다시 탐색한다.
반대의 경우는 최댓값을 1 감소.

 

 

 

재귀 함수

자기 자신을 계속 반복해서 부르는 함수다.
간결하고 명확성 있는 코드를 작성하기 위해 사용하는데, 반드시 빠져나가는 지점인 터미널 컨디션을 명시해주어야 한다.
그렇지 않으면 무한 루프에 빠져서 에러 발생!..

반복문으로는 코드가 복잡해진다거나.. 같은 경우에 사용하면 좋다.

 

 

자바스크립트로 구현한 재귀 함수

function palindrome(string) {
  if (string.length <= 1) {
    // 터미널 컨디션
    return true;
  } else if (string[0] !== string[string.length - 1]) {
    return false;
  }

  return palindrome(string.slice(1, string.length - 1));
}

유명한 팰린드롬 문제를 재귀 함수로 구현해보았다.
팰린드롬은 '오디오', '우영우', '소주만병만주소' 와같이 각각 첫 글자, 끝 글자가 일치해야 하기 때문에
slice 메서드로 글자 길이를 조정해서 재귀 함수를 호출했다.

 

재귀 함수엔 반드시 터미널 컨디션이 있어야 하기 때문에!..
가운데 글자만 남는 경우에는 true를 반환하도록 했고, 만약 글자들이 일치하지 않는다면 false를 반환하도록 했다.

 

 

 

 

 

오늘 TIL 유독..길다.. 

알고리즘으로 정신없던 평일 마무리~~ 😇
주말 동안엔 알고리즘 공부도 더 하고, 끝말잇기 에러 처리.. 반드시 끝낸다!! 👏