CS 특강1. CPU

컴퓨터는 CPU, memory, Disk로 이루어져 있음

CPU(Computer Processing Unit)

CPU 혹은 중앙 처리 장치는 컴퓨터에서 기억, 해석, 연산, 제어라는 4대 주요 기능을 관할하는 장치를 말한다.프로그램의 명령어를 해석하여 데이터를 연산/처리를 하고 그렇게 돌아가도록 제어해주는 부분, 혹은 그 기능을 내장한 칩을 의미한다.

• core(연산이 실제로 실행되는 부분) n개로 이루어짐
• 각 core는 n개의 register의 state를 가짐
• 코어 성능 향상은 본질적으로 한계가 있어 싱글코어에서 멀티코어로 바뀜
• 멀티코어는 멀티한 state를 가지고 있다.

구조

프로그램에서 입력 -> CU에 해당 입력된 값을 연산해달라고 접수가 됨 ->Fetch -> Decode -> ALU->출력

• CU(Computer Cuit): 명령제어장치. like 뇌
• ALU(Arithmetic Logic Unit): 산술/논리 연산
• Register: 저장장치. 용도에 따라 종류가 나뉨
  • General-purpose(범용) : EAX, ECX
  • Special-purpose(특수용): PC(Program Counter)
• Cache(캐시): CPU와 Disk 사이 거리가 멀기 때문에 빈번하게 사용하거나 최근에 사용한 데이터나 값을 복사해놓는 공간이다.

명령어 수행 기능

• Fetch(인출) : 메모리상의 프로그램 카운터가 가리키는 명령어를 CPU로 인출하여 적재.
• Decode(해석) : 명령어의 해석. 이 단계에서 명령어의 종류와 타겟 등을 판단한다.
• Execute(실행) : 해석된 명령어에 따라 데이터에 대한 연산을 수행한다.
• Writeback(쓰기) : 명령어대로 처리 완료된 데이터를 메모리에 기록한다.

프로그래머와 CPU의 소통

CPU는 기계어(Binary one tool)이기 떄문에 어셈블리어로 소통한다.
but 어셈블리어도 너무 어렵 쏘 어렵 그래서 프로그래밍 언어를 컴파일해서 사용.
통역을 두 번 거쳐 소통하는 느낌인거지

---

알고리즘

정렬

: 데이터를 순서대로 나열하는 방법

• 정렬을 할 때는 컴퓨터에 명확한 과정을 설명해야함

버블정렬

앞에서부터 두개씩 비교해서 처음 항목이 다음 항목보다 작으면 그대로 두고 크면 둘의 위치를 변경한다. 이렇게 인덱스 0부터 맨 뒤에 항목은 제외(뒤에서 두번째 항목하고 비교하면 정렬되기에)하고 비교
*a , b = b, a: 파이썬에서 변수 값 교체하기

input = [4, 6, 2, 9, 1]
# 버블 1번 -> [4, 2, 6, 1, 9] 4번 검사, 9는 정렬
# 버블 2번 -> [2, 4, 1, 6, 9] 3번 검사, 6까지 정렬
# 버블 3번 -> [2, 1, 4, 6, 9] 2번 검사, 4까지 정렬
# 버블 4번 -> [1, 2, 4, 6, 9] 1번 검사. 모두 정렬

# 반복문은 4번 돌았고
# 한 반복은
# 인덱스가 다음 인덱스랑 비교해서 다음인덱스가 작으면 자리를 옮기고
# 그렇게 인덱스가 길이의 -1이 될 때까지 도는걸


def bubble_sort(array):
    n = len(array)
    for i in range(n-1):
        for j in range(n -i -1):
            if array[j] > array[j+1]:
                array[j], array[j+1] = array[j+1],array[j]
    return array


bubble_sort(input)
print(input)  # [1, 2, 4, 6, 9] 가 되어야 합니다!

• 이 함수의 시간복잡도는 $O(N^2)$만큼 걸림 ( 이중반복을 했으니까)

선택정렬

: 선택해서 정렬한다. 전체를 보고 가장 작은 걸 맨 앞에 정렬하고 그 다음 작은걸 그 다음에 넣고 식으로

input = [4, 6, 1, 9, 2]
#        -  -  -  -  -
# 앞에서부터 크기를 보고 가장 작은걸 기억한 후 가장 앞에 정렬시킨다
# 셀렉트 1번 -> 4부터 9까지 5번 검사 [1, 4, 6, 2, 9]
#                                    -  -  -  -
# 셀렉트 2번 -> 4부터 9까지 4번 검사 [1, 2, 4, 6, 9]
#                                       -  -  -
# 셀렉트 3번 -> 4부터 9까지 3번 검사 [1, 2, 4, 6, 9]
#                                          -  -
# 셀렉트 4번 -> 6부터 9까지 2번 검사 [1, 2, 4, 6, 9]
#맨 마지막 꺼는 검사 안해도 됨
#셀렉트는 앞에서부터 순서대로 비교를 했을 떄 작으면 그 다음거랑 그 작은 값이랑 비교를 하면 됨


def selection_sort(array):
    n = len(array)
    for i in range(n - 1):
        min_index = i
        for j in range(n - i):
            if array[i+j] < array[min_index]:
                min_index = i + j
        array[i], array[min_index] = array[min_index], array[i]


selection_sort(input)
print(input) # [1, 2, 4, 6, 9] 가 되어야 합니다!

• 시간복잡도: 이중반복이니까 $O(N)$

삽입정렬

선택 정렬이 전체에서 최솟값을 "선택" 하는 거 였다면,
삽입 정렬은 전체에서 하나씩 올바른 위치에 "삽입" 하는 방식이다.

선택 정렬은 현재 데이터의 상태와 상관없이 항상 비교하고 위치를 바꾸지만,
삽입 정렬은 필요할 때만 위치를 변경하므로 더 효율적인 방식이다.

input = [4, 6, 2, 9, 1]


def insertion_sort(array):
    n = len(array)
    for i in range(1, n):
        for j in range(i):
            if array[i - j - 1] > array[i - j]:
                array[i - j - 1], array[i - j] = array[i - j], array[i - j - 1]
            else:
                break
    return array

insertion_sort(input)
print(input)

• 이미 정렬된 아이들은 다시 안봐도 되니까 array[i-j-1]가 array[i-j]보다 작으면 다른 애를 안봐도 그냥 뒤에 붙여주면 정렬이 된거임
  

def insertion_sort(array):
    n = len(array)
    for i in range(1, n):
        for j in range(i):
            if array[i] < array[j]:
                array[j], array[i] = array[i], array[j]

    return array

• 이건 내가 생각해 본 코드인데
  삽입정렬이 아니라 탈락
  그리고 새로 정렬할 애가 바로 앞에 애보다 커도 그 앞에 꺼를 다 비교하게 되어있어서 성능이 별로일 것 같다
  그래도 일단 결과값은 잘 나옴

---

마무리

강의는 3주차를 다 보고 다시 정리하면서 처음부터 보고있는데
알고리즘 이해가 잘 안되서 시간이 많이 걸린다.
그려가면서 하니까 괜찮긴한데
그래도 하나가 이해가 안되면 진도를 잘 못나가겠다...ㅎㅎ

주말동안 진도 다 빼야되는데..

나는 알고리즘과 친해질 수 있을까..

참조

https://namu.wiki/w/CPU
[스파르타코딩클럽] 쉽게 배우는 알고리즘 KDT 실무형 스프링 백엔드 엔지니어 양성과정 1회차