CS 기초2

Memory

• 이전에 16진수?

16진수 사용 이유는 2진수보다 간단하게 16진수을 이용해서 나타낼수 있기 때문이 다.
1byte에 해당되는 내용을 2진수는 2개의 16진수로 나타낼 수 있기 때문에 정보표현에 매우 유용함.

표기법은 0x11.
0~9 다음 A, B, C, D, E, F

• 메모리 교환, 스택, 힙
  
  메모리 안에 데이터 저장되는 구역이 나눠져 있음.
  Machine code에는 프로그램 실행될 때 프로그램 컴파일된 바이너리 저장.
  Global에는 프로그램내 전역변수 저장.
  Heap에는 메모리데이터 저장.
  Stack에는 프로그램내 함수 저장.
  (출처 cs50)

  Data structures

컴퓨터 메모리를 더 효율적으로 관리하기 위해 정의한 새로운 구조체

• Linked list
  배열과 달리 메모리 상 여러곳에 나눠져 저장되어 있는 형태.
  자신의 값과 다음 주솟값을 가지고 있다.
  장점은 새로운 값 추가시 메모리 재설정 안해도 되지만
  단점으로는 임의의 값 접근 불가 (순차대로 가서 접근)
  그래서 접근시간 O(n)이다. (배열은 정렬시 O(log n))

• Tree
  연결리스트에서 각 노드들이 1차원이 아닌 2차원으로 구성되어 있는 경우
  가운데 시작하는 루트노드가 있고 그 밑으로 자식노드들이 있고 포인터를 가지고 있는 형태
  
  Binary search에 효율적이다.
  포인터가 늘어나 메모리 사용을 더하게 되고, 새로운 요소를 추가하다 균형이 무너지게 되면 효율이 떨어짐. (선형검색이랑 비슷해진다.)

• Hash table
  연결리스트의 배열로, 해시함수를 통해 요소들이 어디로 이동될 지(바구니, 배열) 정해진다.
  이동된 곳에서 요소들은 새롭게 정의된 연결리스트로 이어진다.
  이렇게 연결리스트가 담긴 여러 바구니가 있는 구조를 Hash table.
  해시함수를 잘 만들어 바구니에 요소가 하나씩 담긴다면O(1) 이지만
  여러 요소가 담기게 된다면 O(n)이 된다.
  

• Trie
  각 노드가 배열로 이루어진 트리형태 구조.
  (해시테이블에서 바구니에 요소가 무조건 한개만 담긴 상태, 해시테이블 확장버전 이라고 생각했다.)
  O(1)인 장점이 있지만, 많은 메모리를 사용한다는 단점이 있다.
  

• Stack, Queue, Dictionary
  큐는 LIFO방식 push와 pop으로 요소를 넣고 뺄 수 있다.
  스택은 FIFO방식으로 enqueue(get in line)과 dequeue(get out of line)
  딕셔너리는 키와 값 요소로 이루어져 있고, 키에 해당하는 값을 저장하고 읽어온다.
  해시테이블과 동일한 개념

사진출처 cs50