컴퓨터공학 입문수업 3주차 강의노트

|

강의 중에 자유롭게 메모한 정리되지 않은 내용입니다. 강의 내용은 다른 포스팅에 따로 정리하였습니다.

4/21(금) DAY 18

숙제

  • python socket 활용하여 채팅 클라이언트 서버 만들기
  • 파이썬이면 60줄로 서버 클라이언트 소켓을 만들 수 있다 (다이어그램 참고 )

개발 사이트 정보

  • 구글 디벨롭퍼 그룹 : 구글 플러스 커뮤니티 GDG Korea
  • Django
  • GDG SEOUL
  • women techmakers
  • 파이썬은 챗봇 만들기 좋음

    네트워크

  • 수업자료
  • 용어를 익힌다는 관점에서 수업 듣기
  • 초기의 네트워크 통신(모뎀)은 1:1 만 가능하고 전화비가 많이 나왔다.
  • 다대다 통신의 시작
    • 버스구조 : 각각의 컴퓨터가 메인라인에 각각 연결되어 있는 구조가 버스구조
    • 링형 : 버스를 구부려서 끝과 끝을 연결
    • 스타형 : 가운데 관리하는 컴퓨터(메인서버)를 두고 연결되어 있는 상태
  • USB는 네트워크, 저장장치 둘다 수행이 가능하다.
  • 맥북에는 랜포트가 없다.
  • 에플에서는 USB로 RJ45 포트와 통신이 가능하다
  • LAN(근거리 통신망) < MAN(도시권 통신망) < WAN (광역 통신망)
  • AP : Access point
  • 공유기는 Asus 제품이 좋다. WiFi ac라고 붙은게 최신
  • 테더링 : 1:1 통신을 한다. (USB, 블루투스)
  • 핫스팟 : LTE를 Wifi로 바꿔서 다른 기기가 통신할 수 있도록 한다.
  • 임베디드, IOT 계역

OSI 7 layer (아주중요)

  • Open Systems Interconnection Reference Model
  • 국제 표준화기구에서 개발한 컴퓨터 네트워크 프로토콜 디자인과 통신을 계층으로 나누어 설명한 것
  • packet : 과거 피쳐폰에서는 packet 단위로 요금이 부과
  • 일반적으로 1kbyte
  • 패킷이
  • 헤더 7개를 붙어셔 통과 시키면 ISP(Internet Service Provider)
  • 네트워크 카드에서 발생 (Application layer, presentation layer, session layer)
  • let’s encrypt - 개인홈페이지 암호화 가능 (사용법 참고)
  • ~ Network layer 는 컴퓨터 공학 영역 data link layer ~ 전자공학 영역
  • TCP/IP 프로토콜에서는 4단계를 가진다 (OSI 7 Layer Model 기반)

TCP/IP 프로토콜

  • 프로토콜 : 약속


  • 신입 면접 단골질문
    • lineked list
    • big O (버블소트 O(N^2), 퀵소트, 머지소트 O(N log N), 바이너리서치 O(log N))
    • stack, queue (쉬워서 잘 안나옴), 재귀함수 (피보나치, 하노이의 탑) 퀵소트, 등차수열 활용한 (1~1억 까지 더하기)

4/20(목) DAY 17

앞으로 공부해야 할 내용

  • liked list
    • double lineked list (dummy lineked list오 함께 반드시 공부)
    • deque (알아두기)
  • queue
    • circular queue (배열을 이용한 구현)
  • sorting (선생님 깃헙에 다 올라와 있음)
    • insertion sort (훑어보기)
    • selection sort (훑어보기)
    • heap sort (꼭!)
    • merge sort (꼭!)
  • tree
    • BST (Binary Search Tree) (아주중요)
    • AVL - 균형 맞추는 알고리즘 (BST 와 함께 공부)
  • table, map, (dictinary) - 파이썬에서 3개는 같다(?)
    • open addressing 기법
    • closed addressing 기법
  • graph (반드시 숙지)
    • BFS (broadness first search) 너비우선탐색
    • DFS (depth first search) 깊이우선탐색
    • kruskal algorithm (네비게이션에서 활용 가능)
    • 다이작스트라 (네비게이션에서 활용 가능, BFS기반 구현)
    • 프림
  • 그리디 알고리즘
  • 파이썬 데코레이터 찾아서 공부하기

수업내용

  • stack을 활용한 계산기 elif로 다시 짜기
  • 왜 else, if 깊게 짰는지?
    • 우선순위 (fizzbuzz)
    • if, elif, elif, elif : if 문이 False인 경우 elif로 이동, 첫번째 if 문은 배제
    • if, if, if, if : 첫번째 if False인 경우
  • ADT 는 유저 프로그래머가 사용하는 메소드

heap

  • heap 소트, priority queue 에 사용

퀵소트

  • 수업자료
  • 현업에서 많이 쓰인다.
  • 머지소트 꼭 공부하기
  • soritng, 성능평가
  • 빅오를 구할 때 유일하게 퀵소트만 worst case 가 아닌 평균 값으로 구한다. (다른건 최악의 케이스)
  • 버블소트의 빅오는 O(N**2), 퀵소트의 빅오는 O(N log N) 엔로그엔!! 머지소트도 엔로그엔 하지만 퀵소트가 가장 빠르다
  • 각 알고리즘의 빅오 외우기

퀵소트 bigO 구하기 (수업영상 다시 보기)


4/18(화) DAY15

  • 바이너리 서치 재귀적 구현 다시한번 연습하기

수식의 표기법

  • 수업자료
  • 중위 표기법 : 우리가 아는 수식
  • 후위 표기법 :

후기 표기법 만드는 법

  • 수업자료 참고

stack, 후위표기법을 활용한 계산기 만들기

Tree

  • tree, graph 는 이산수학에 들어가는 범주
  • 2개 뿐만이 아니라 3개 4개로 뻗어나갈 수 있다.
  • 일반적으로 말하는 tree 는 binary tree(이진트리)를 말한다.
class tree_node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
  • full binary tree 포화이진트리 : 많이 보이지는 않는다.
  • complete binary tree 완전이진트리 (힙 구현시 중요)

BST(Binary Search Tree) : 이진탐색트리

  • 아주중요함(구글링), 어려움, 2진 완전트리가 아니다.
  • AVL 알고리즘 공부할 것 - 이진탐색트리의 균형을 맞춰준다. (중요)

heap (숙제)

  • 수업자료
  • stack, queue 처럼 search가 필요 없다.
  • 전통적으로 heap의 이진트리를 만들어야 할때 배열로 만든다 (노드로 구현하는 것도 가능)
  • 1 based index
  • 완전이진트리 사용
  • heap 소트 : heap을 이용한 소트

heap 구현 힌트

  • num_of_data 의 data 는 완전 이진트리의 마지막 index를 의미한다.
  • left_child = parent * 2 > num_of_data 라면 해당 노드는 단말노드
  • left == num_of_data 라면 자식노드가 1개
  • left < num_of_data 자식노드가 둘 다 있다.

heap 구현 인터페이스 ADT

class Heap:
  def get_parent_idx(self, idx):
    return idx // 2

  def get_left_child_idx(self, idx):
    pass

  def get_right_child_idx(self, idx):
    pass

  def __init__(self, s_min_max = 'min'):
    self.dynamic_arr = [None, ]
    self.num_of_data = 0

  def is_empty(self):
    pass # boolean

  def size(self):
    pass

  def insert(self, data):
    pass

  # 단말노드면  None, 우선순위가 높은 자식노드의 인덱스
  def which_is_prior_child(self):
    pass

  def delete(self):
    pass

# 테스트코드
# list 아이템 출력
# delete 시 정렬이 되는지 확인     

4/17(월) DAY14

  • binary search recursive 복습
  • Bubble sort
  • Insertion sort 구글링 해보기
  • Quick sort (목요일에 배울 예정)
  • 참고영상

이번주 수업 내용 (개요)

  • data structure
    • 자료구조와 알고리즘이 뭔지?
  • linked list : node를 이용하여 구현
  • stack, queue : stack으로 계산기 만들어보기
  • heap만 유일하게 배열을 기반으로 구현한다.
  • 자료구조를 만들어봤다 하면 자주 받는 질문
    • 후위표기법 계산기 만들어봤니?
    • linked list 만들어봤니?
    • heap 뭘로 구현해봤니? (one based, zero based )

유용한 정보

  • 자료구조, 알고리즘 : 코더와 엔지니어의 차이, 진입장벽
  • 백지에 linked list 구현
  • 최단경로 graph로 구현
  • 이벤트 드리븐 구글링 해보기
  • 자료구조를 배우면 라이브러리를 보는 시야가 넓어진다.

노드

linked list

  • 자료구조에서 가장 중요한 개념 중 하나

ADT(abstract data type) 추상 자료형

  • 새로 정의한 자료형
  • 메소드의 목록 (인터페이스)

stack

  • stack 과 queue는 search가 없다.
  • Node 기반으로 stack 구현해보기 (숙제) head만 있어도 구현이 된다
  • LIFO (Last Input First Out, 선입후출, 라이포)
  • 접시

stack ADT (인터페이스)

  • is_empty() -> boolean
  • push -> insert : push(data)
  • pop -> delete : pop return 맨위 값을 리턴하고 동시에 삭제
  • peek -> 엿보기 : 맨 위 값 반환만 하고 삭제는 안함

queue

  • Node 기반으로 queue 구현해보기 (숙제) head,tail 만 있어도 구현이 된다
  • FIFO (First Input First Out, 선입선출, 파이포)
  • 화장실 줄서기

queue ADT (인터페이스)

  • enqueue == > insert …

4/14 (금) DAY13

수업내용 (개요)

  • data structure & algorithm
    • binary search
    • big O of binary search
  • recursion
    • fibonacci
    • hanoi tower
  • sorting
    • bubble sort
    • quick sort (하루종일 할겁니다. 피벗 적용으로 성능개선까지, 현업에서 가장 많이 사용)
  • data structure
    • linked list (이것만 잘 넘어오면 다른 자료구조 괜찮을거에요)
    • stack, queue (계산기 만들어 봅니다)
    • heap & priority queue
  • 수업자료 있음
  • linear search (순차검색) : 순서대로 찾는다. 성능평가시 비교대상으로 사용
  • linear search는 정렬 방식이 상관 없다.
  • binary search (이진탐색) :
  • binary search는 반드시 정렬된 상태에서 시작해야한다.
  • 로그실행시간을 보장한다.

성능측정

  • 수업자료 있음

BigO의 대표적인 사례

재귀함수

  • 함수 정의 내에 같은 이름의 함수가 올 때 이를 재귀함수라 부른다.
  • 반드시 탈출조건이 있어야 stack 터지는걸 방지할 수 있다.
  • 같은 행위가 반복될 때 재귀함수를 사용한다.

피보나치 수열

하노이의 탑

버블정렬

파이썬의 제너레이터와 코루틴


4/13 (목) DAY12

질문

  • 컴파일 언어는 변수나 함수 선언 순서가 중요? (자바스크립트, CSS 처럼)

수업내용 (개요)

  • compiler vs interpreter 차이
  • instructions & register (핵심주제)
  • memory segments (아주중요)
  • virtual memory (중요)
  • operand stack –> virtual machine의 작동원리
  • process vs thread
  • mulithread 구현
  • race condition (못하면 검색)
  • mutual exclusion (못하면 검색)

메모

  • 파이썬은 연산된 데이터 저장할 때 stack을 사용한다.
  • 컴퓨터공학 5대 과목
    • 프로그래밍 언어
    • 자료구조 : 링크드리스트, 스택, 큐 (계산기)
    • 알고리즘 : 바이너리서치, 소팅
    • 컴퓨터 구조 : cpu, 레지스터
    • os : 메인메모리 (ram), 하드디스크, 4G씩 부여받아도 왜 여러게 프로그램이 실행 가능한가? vm

4/11 (화) DAY11

수업내용 (개요)

  • 함수의 호출 방법 (아주중요)
    • call by reference (참조에 의한 호출)
    • call by value (값에 의한 호출)
    • call by assignment
  • CPU & memory : segmentation(중요) > 찾아보기
    • register
    • cache
    • main memory (코드, 데이터, 스텍, 힙 segment)
  • paging 기법 (중요) > 찾아보기
  • compiler & interpreter

유용한 정보

  • 왜 메모리에 대해서 알아야 하나?
    • Facebook의 string 최적화 예시 [자료]https://www.youtube.com/watch?v=kPR8h4-qZdk&feature=youtu.be
    • 수업자료
  • 면접단골질문
  • call by reference, call by value 차이 설명
  • 링크드 리스트 만들어봐라

call by reference

  • 두 변수의 값을 바꾸는게 목적인 함수
  • C++ 을 사용한 예시

call by value

  • ‘하지만 메인 함수의 변수 n과 func 함수의 변수 n은 메모리상 다른 위치에 상주해 있으므로 직접적인 연관이 없다.’
  • C++을 사용한 예시

출처: http://luckyyowu.tistory.com/9 [요우의 내맘대로 블로그]

  • call by reference
    • 함수 간에 같은 변수를 사용하는 방법
    • 참조자 & : 포인터

  • 참고글

call by assgignment

  • 파이썬은 call-by-reference도 아니고, call-by-value도 아니다.
  • 파이썬은 모든 요소가 객체이기 때문에 메모리 효율상 call by assgignment 방식을 사용한다.
  • mutable, immutable

  • 파이썬에서 class 는 독자적인 메모리공간인 심볼테이블을 갖고있다.
  • 따라서 메소드 안에서 call by reference와 같이 동작한다.
  • 함수선언시 def (definition) 임시 메모리공간을 정의한다.

  • 파이썬에서 call by assgignment 개념을 모르면 나중에 어려움을 겪게된다.

  • 파이썬의 함수 호출방식 call by assgignment

    • 처음은 call by reference 처럼 동작한다 (매개변수 인자의 주소를 가르킨다)
    • 하지만, 함수 내에서 인자의 값이 재할당 되면 해당 매개변수의 자료형에 따라서 동작이 다르다.
      • 불변객체 (immutable) : 숫자, 스트링는 call by value 처럼 동작
      • 가변객체 (mutable) : dic, list는 call by reference 처럼 동작 (단, 매개변수 일부 내용을 업데이트 할때만)

숙제

  • 함수 호출방식 설명하기

메모리

  • ram은 1byte(8bit) 단위로 주소를 만든다. (우편번호 처럼)
  • 32bit 컴퓨터, 64bit 컴퓨터의 차이는?
    • 와이어의 갯수 (와이어의 전압에 따라 0,1 구분)
    • 한번에 보낼 수 있는 데이터의 양이 32개다, 64개다.
  • 32bit 시스템은 4G까지만 메모리를 표현할 수 있다. (2 ** 32 = 약 4기가) (용산의 사기수법 32bit 컴퓨터에 8기가 메모리를 사용하는건 의미가 없다.)
hex(id(a)) # 메모리 address를 의미한다.
# '0x1012241d0'
  • 파이썬 인터프리터에 의존적
    • python 32bit : 32/4 = 8 , 메모리 주소 8자리
    • python 63bit : 64/4 = 16, 메모리 주소 16자리
  • 컴파일 언어는 모든 data segment(code, data, heap, stack)를 사용하지만, 파이썬은 heap 영역만 사용한다.
  • del을 잘 활용하면 메모리 관리를 더 잘 할 수 있다.

4/10 (월) DAY10

수업내용 (개요)

  • 연산자 오버로딩 (operator overloading)
  • 다형성, 추상클래스 (polymorphism, abstract class)
  • data analysis oop (cache개념 사용)

유용한 정보

  • 프로그램을 만들려면 클래스별로 따로 파일을 만들고 조합 할 때 main.py을 사용하는게 좋다.
  • 2의보수 : 나중에 웹개발 보안쪽 check sum을 할 때 2의 보수를 사용한다.
  • 다형성: 같은 코드 다른결과 (같은 코드인데 어떤 객체에 적용하냐에 따라서 결과가 달라진다)

cache

진수 (노트필기 참고)

10진수

  • 0~9 10개의 숫자

2진수

  • 0,1 2개의 숫자

16진수

  • 0~9, a,b,c,d,e,f

2의 보수

  • 컴퓨터가 음수를 저장하는 양식
  • 1byte
  • 부동소수점의 특징
    • 정확도를 포기한 대신에 표현 범위를 어마어마하게 늘렸다.
    • if a = 12.12132: 이런 식으로 사용하면 안된다.