내배캠 TIL 20220.11.11 (CS 특강, 알고리즘 2주차)

개발자 되는 중/TIL&WIL

내배캠 TIL 20220.11.11 (CS 특강, 알고리즘 2주차)

SeonChoco 2022. 11. 11. 20:51

강창민 튜터님 CS (computer science) 특강

cpu memory disk

컴퓨터를 이루는 3대장

cpu는 cpu를 제외한 모든 유닛을 관장한다.

컴퓨터는 특성

cpu는 n개의 resgister로 이루어져있다.

코어 X N

무어의 법칙

왜 코어를 여러개 만들었을까?

하나로는 발열이 너무 심해서

회로가 타들어 갈 정도

코어 - 협의

코어의 성능 향상엔 본질적인 한계가 있다.

차라리 multi 만들자

state = register 이다.

멀티하게 상태를 가진다.

cpu는

ALU 산술논리연산

CU controll unit = 리얼 뇌

프로그램A를 클릭하면 cpu에게 연산을 하라고 시킨다.

명령 접수는 cu가 받아준다.

그 다음 fetch 한다.

어딘가 쌓인다 그다음에 해석한다.

ALI에게 토스 일거리받음 산술논리연산한다

연산한 결과를 프로그램에 보내고 프로그램의 메모리의 상태가 달라진다.

업무별로 나눈다.

General purpose - 범용 - EAX, ECX (ESP, EAB 같은것)

special puroise - 특수용 (PC 레지스터 - 프로그램 카운터,

프로그램

명령어 1 명령어 2 명령어 3

한라인 한라인 한라인

cpu가 명령을 처리했는지 알아야 다음 일을 할 거 아닌가

얼마나 명령처리했는지 알려주는 것이 PC 레지스터이다.

레지스터의 종류는 너무 많아서 검색해보시길

CPU의 구성

ALU

Registers

Cache

disk 랑 cpu랑 서로 통신할 때 거리가 좀 있다.

매번 왔다 갔다하면 비효율적 사람들이 불편하다.

빈번하게 쓰인 것

가장 최근에 쓰이는 것

등등 그런거를 캐시라는 장소에 저장해놓는다.

음료수 사러 집에서 10km 떨어진 마트 가기 보다는 앞에 있는 자판기에서 음료수 뽑아 먹는거

cache coherence가 뭐라고?

cpu랑 프로그래밍이랑 어떻게 통신하는지

cpu는 binary onetool

cpu는 기계어만 알아듣는다 비트로 된 101100001111000

어셈블리어가 뭐지 loud jmp stop operand (개발자들의 허들이다)

010101010 못쓰니까 어샘블리어 만들데 이것도 힘들어서 C언어같은 HIGH LEVEL 언어를 만들었다

컴파일러가 C 언어, 자바스크립트, 파이썬 같은거다 아하… 말그대로 조립(연결)을 도와주는 언어들인거구나

ISA 가 뭐라고? 명령어 집합 instruction set architecture

원래 RISC CISC라는게 있었다.

CISC complexed라는게 있었는데 너무 복잡해서

RISC reduced로 간단한걸 쓰기로 했다.- 조금더 효율적으로 우리가 쓸수가 있다.

명령어 수행

의미가 뭐야?

이거를 하면 뭐가 되는데?

코드 하나하나 실행이 되는 것 라인 1, 라인2을 보내면서

컴퓨터 메모리의 레지스터들이 자꾸자꾸 변한다.

그렇게 하나하나 변하게 하다보면 결국 내가 원하는 기능이 실행된다

디테일 명령어 수행

결론은 모니터나, 디스크 등등에 영향을 미친다

명령어를 fetch 하면 CU가 일한다

사실 Opcode가 있다.

risc는 한 싸이클에 컴퓨터 명령을 실행

cisc는 시간이 많이 걸린다

opcode- 명령어

operand

imm

resgister

memory

fetch해라

execute

WB: Write back

결론 명령어 수행이 그냥 되는 것이 아니다

프리패치

prefetch

최적화 테크

컴퓨터 구조론

os, db, 네트워크 - 필수

컴파일러, 프로그래밍 언어

summary

1. 왜 싱글에서 멀티 코어 됐는지

2. cpu 생김새

3. cpu와 프로그래머는 어떻게 통신하는가

4. 명령어 수행방법

죽이되던 밥이 되던

알고리즘 강의를 휘뚜루 마뚜루 듣기

02. 어레이와 링크드 리스트

array

캡슐호텔

배열

-크기가 정해진 테이터의 공간

-원소에 즉시 접근할 수 있다. room[0]처럼, 원소 순서는 0부터 시작

상수번 내에 접근 가능 O(1)내에 접근 할 수 있다고 표현.

원소를 중간에 삽입 삭제하려면 한칸씩 한칸씩 해서 모든 원소를 다 옮겨야한다

최악의 경우 길이 N만큼 옮겨야한다 = O(N)의 시간 복잡도를 가진다

원소를 추가 삭제를 해야한다면 배열은 매우 비효율적인 구조

linked list, 리스트

화물열차

-리스트는 크기가 정해지지 않은 데이터의 공간, 연결고리로 이어주기만 하면 자쥬자재로 늘어날 수 있다.

-특정 원소에 접근하려면 연결고리를 따라서 탐색해야한다.

최악의 경우 모든 화물칸 길이만큼 탐색해야한다. = O(N)

연결고리 = 포인터, 화물칸 = 노드

-리스트는 원소를 중간에 삽입 삭제하기 위해서 앞뒤의 포인터만 연결하면 된다. = O(1)

파이썬의 list는 array이다.

하지만 새로운 값을 넣을 때 O(1)의 시간 복잡도가 걸린다. 간단하다

파이썬의 배열은 array로도 쓸 수 있고, array로도 쓸 수 있는 효율적인 자료구조이다. - 동적배열(dynamic array)

03. 클래스

속성을 가진 객체를 총칭하는 개념

객체는 유일무일한 사물

ex) 클래스가 사람이면 객체는 유재석, 박명수 가능

클래스가 동물이라면 객체는 고양이 강아지 가능, 완두 자두 호두 가능

클래스를 이용하면 같은 속성, 기능을 가진 객체들을 묶어서 정의할 수 있다.

Class 클래스명:

pass # pass는 안에 아무런 내용이 없다는 의미

person1 = 클래스명()

#클래스를 통해 새로운 객체를 만들겠다는 의미

#소괄호는 생성자가 들어간다.

print( person1) 객체에 주소를 붙여서 분류해놓은 것이 나온다.

<__main__.Person object at 0x000001F642EC8100>

person이라는 클랙스의 object를 at 이후라는 공간주소에 있다.

이 공간주소로 서로 다른 객체를 확인할 수 있다.

pass처럼 텅빈게 아니라 기능이 있는 class를 만들자

class Person:
    def __init__(self):
        print('i am created', self)

person1 = Person()
print(person1) 
person2 = Person()
print(person2)

파이썬에서 생성자 함수 이름은 _init_으로 고정되어 있다.'

파이썬에서는 클래스안에 생성자나, 내부 함수를 만들 때 (self) 이렇게 써서 인자로 자기 자신을 넘겨준다.

#인자와 매개 변수 차이가 뭐람? 구글링

매개변수 parameter: 함수가 정의될 때 사용되는 변수

인자 argument: 실제로 함수가 호출될때 넘기는 변수

class Person:
    def __init__(self, param_name):
        print('i am created', self)
        self.name = param_name

person1 = Person('김선형')
print(person1.name)
print(person1)
person2 = Person('김선린')
print(person2.name)
print(person2)

클래스에서 객체에 내용을 더 추가 하기 위해서 이용하는 법(클래스에서 객체에 속성을 넣어주는 법)

받아올 내용의 매개변수를 더해준다.

self.name =param_name ?

나 자신에다가 name이라는 변수를 만들어서 매개변수로 가져온 param_name 값을 저장해준다.

Person()안에 이름을 인자로 넣어봤다

class Person:
    def __init__(self, param_name):
        print('i am created', self)
        self.name = param_name

    def talk(self):
        print(f'안녕하세요 ,제 이름은 {self.name} 입니다.')


person1 = Person('김선형')
print(person1)
print(person1.name)
person1.talk()

person2 = Person('김선린')
print(person2)
print(person2.name)
person2.talk()

클래스 내부함수를 만들어보자 메소드라고 부른다.(자바스크립트랑 파이썬 강의에서 둘 다 배웠다. 근데 왜 벌써 기억이 안나지...그리고 둘 다 같이 배우니까 헷갈려 미침 둘 다 못쓰겠다)

함수명 짓고 () 치면 자동으로 self가 들어간다.

print(f'안녕하세요 ,제 이름은 {self.name} 입니다.')
print('안녕하세요, 제 이름은',self.name, '입니다')

문자열 변수와 연결하는 두 가지 방법

저번에 파이썬 강의에서는 +로 연결하는 방식도 이용했다.

04. 링크드 리스트 구현 -1

링크드 리스트 모든 원소 출력

링크드 리스트 원소 찾기/추가

링크드 리스트의 노드에는 들어간 값과 다음 연결된 노드가 무엇인지 (포인터)에 대해 속성을 넣어준다.

직접

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


box_1 = Node(3)
box_2 = Node(4)
box_1.next = box_2
print(box_1)
print(box_1.data)
print(box_1.next)
print(box_1.next.data)

클래스를 만들면 노드에 정보를 넣는일을 일일이 반복하지 않아도 된다.

단순 반복을 줄여주는 링크드 리스트 클래스를 만들어보자

꼭 가지고 있어야할 정보는 맨 앞칸 정보이다. head node 만 가지고 있다.

그 외에는 옆으로 옆으로 넘어가면서 확인할 수 있기 때문이다.

1) linkedlist는 self.head에 시작하는 노드를 저장한다

2) 다음 노드를 보기위해서는 각 노드의 next를 조회해서 찾아간다.

줄 옮기기 단축기 ctrl + shif + 방향

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class linckedList:
    def __init__(self, data):
        self.head = Node(data)

linked_list = linckedList(3)
print(linked_list)
print(linked_list.head)
print(linked_list.head.data)

1. 위에 생성된 클래스 Node로 객체 속성을 data 와 next를 만들어준다.

2. 그 노드를 다시 클래스 linkedlist로 head라는 객체속성을 만든다.

프린트 해보면 linked 클랙스 객체속성 안에 Node 객체 속성이 들어있고 그것 안에 데이터가 있다는 것을 확인해볼 수있다.

프로그래머스 문제 풀기

(강의에서는 파이썬으로 가르치는데, 나는 헷갈린다... 일단 자바스크립트로 연습을 해서 자바스크립트 안 까먹도록 하자)

Math.ceil() 소수점 올림

baekjun hub?라는 크롬 프로그램을 다운 받아서 github와 프로그래머스를 연동했다.

내가 푼 답들을 아래의 레파지토리에 저장할 수 있다.

https://github.com/hobak12/algorithm-practice