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

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

Binary Search

• 수업자료 있음
• 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: 이런 식으로 사용하면 안된다.