0. 메모리 구조를 알아야 하는 이유.

 

- c++는 개발자가 메모리를 관리를 할 줄 알아야하고, memory 누출이 발생할 경우 (만약 지속적으로)

 

프로그램이 오류가 날 수도, 다운이 될 수도 있습니다.

 

- 컴퓨터 구조론인가.....배울 때 많이 학습했던 부분인 것 같은데 시간이 꽤 경과되어서... 다시 중요한 부분 위주로 다시 정리해보겠습

   니다.

 

1.  메모리 구성

 

2. Stack

 

- 이번 글에서는 c++의 스택구조에 대해서 상세히 정리를 해볼까 합니다.

 

- 변수의 코드를 짜서 포인터를 이용해서 주소를 출력해보시면 아시겠지만, 변수의 주소가 스택으로써 아래에서 위 저장

 

- 컴퓨터는 변수의 이름을 저장해서 바로 접근하는 것이 아닌, stack의 top의 위치에서 얼마나 떨어져있는지를 기억하여 

  접근합니다.

 

 

3. 스택프레임

 

- 사실 Stack 메모리에 쌓이는 단위는 변수 단위가 아닌 스택프레임 단위인데 이는 function단위 입니다.

 

- 변수가 하나씩 쌓이는게 아니라 function에서 차지하는 메모리 만큼이 한번에 stack에 쌓이는 것입니다.

 

- 또한, stack에는 function이나 main 함수의 변수들 뿐만 아니라 스택에 쌓인 function이 종료되면 다시 그 이전의

 

- 함수 (메인이 될수도, 또다른 function이 될수도)로 돌아 가야 하기 때문에 function call을 한 function 의 return     

   address , 그리고 그 function의 arguments 등이 같이 스택메모리 공간에 쌓입니다.

 

- 그 function이 끝나면 스택메모리에서 해당부분이 사라집니다.

 

- 프로그램 실행시 어느정도의 메모리 공간을 확보하는데 간단한 예로 너무 깊이 재귀함수를 실행할 경우, 이 스택메모

  리 공간에 계속 쌓이게 되고, 이는 스택오버플로우를 발생시키는 경우를 종종 확인하실 수 있습니다.

 

- c++에서는 this라는 키워드를 제공하는데 , 이를 통해서 함수를 실행하면서 객체의 멤버 변수에 쉽게 접근할 수 있습니

  다. this 역시 스택프레임에 객체의 주소를 가지고 올라감으로써 쉽게 객체의 멤버변수에 접근할 수 있도록 해주고 있

  습니다.

1. 배열

 

 

- 연속된 메모리 상에 위치 (배정) 된다.

 

- "시작주소 + (자료형의 크기) * INDEX " 를 통해서 접근이 가능하므로 배열의 이름과 INDEX만으로 쉽게 접근

    이 가능하다. (매우 큰 장점)

 

- 크기와 자료형을 지정해주어야 한다.

 

- 동적배열로 어느정도 해결이 가능하지만, 배열이 최대크기를 넘어설 때는 Array Doubling이 발생하는데 

 

- 두배 크기의 배열이 선언되고, 기존의 데이터들을 새로운 두배크기의 배열로 모두 옮겨야 하므로 O(n) 시간이 소요. 

 

-(여담으로 수업을 들을 당시에 그럼 n크기의 배열에서 계속 삽입,삭제,삽입,삭제가 일어나면 계속 새로운배열이 생기고

  시간이 오래걸리는 것 인가? 라는 질문이 있었는데, 데이터의 개수가 n+1이 되어서 2n짜리 배열을 선언해서 옮겼을 

  때, 삭제연산이 일어나서 다시 n이 되었을 때 바로 다시 크기가 n인 배열로 옮기진 않는다고 한다. 보통은 n/2 정도가 

  되었을 때 옮긴다고 한다.)

 

- 탐색, 삽입, 삭제

 

   (1) 탐색

     -> 원하는 위치가 존재할 경우 index로 바로 접근이 가능하다 (O(n))

     -> 특정한 value를 찾고 싶을 때는 앞쪽부터 탐색하므로 O(n)

 

    (2) 삽입

      -> 특정위치에 삽입한다면 그 위치부터 끝쪽 까지 위치하던 데이터 들을 모두 한칸씩 미뤄야 하므로 (O(n))

      -> 맨 뒤에 삽입일 경우 옮길 것이 없으므로 빠르지만, 최악의 경우는 맨 앞쪽에 삽입할 경우 이므로 n-1개를

          옮겨야 할 수도 있다.

 

    (3) 삭제

       -> 삭제된 위치로 부터 뒤에 있는 데이터들을 모두 앞쪽으로 한칸씩 당겨주어야한다. (삽입과 같은 맥락)

 

 

- 배열은 메모리상에 연속되게 위치하기 때문에 크기가 큰 배열을 선언하려고 할 경우 남은 공간의 합은 충분하더라도

 

- 연속된 공간이 확보되지 않을 경우 메모리 할당을 못 받을수도 있다.

 

 

2. 연결리스트( 링크드 리스트)

 

- 단순 연결 리스트 (simple linked list)와 이중 링크드 리스트(doubly linked list)가 존재

 

- (단순 연결 리스트)  - HEAD Pointer를 통해서 접근

 

- (이중 연결 리스트)  - HEAD,TAIL을 통해서 접근

 

- 위의 그림과 같이 연결리스트는 연속된 메모리 공간에서 존재하지 않고 다음 테이터를 가리키는 포인터를

   

- 통해서 다음 원소에 접근한다.

 

- 연속된 공간이 필요하지 않고, 크기를 미리 지정해줄 필요도 없다.

 

- 반면, 다음원소를 가리키는 포인터에 대한 공간낭비 (오버헤드)가 발생한다.

 

- 심한경우를 예로 들자면 char형을 저장하려고 하는 경우 실제 데이터는 1byte인데

 

- 이중 연결리스트로 구현할 경우 prev와 next에 해당하는 포인터들이 각각 4byte씩 이므로 총 9 byte를 차지 하게 된다.

   (하나의 노드 당) -- 이는 배보다 배꼽이 더 큰 격이다.

 

- 탐색, 삽입, 삭제

 

  (1) 탐색

    - 포인터를 따라서 찾아가야 하므로 탐색시간이 오래 걸린다. (O(N)

 

  (2) 삽입

     - 간단하다. 탐색이 끝난 상태(탐색은 오래걸림)라면 넣고자 하는 위치의 이전 노드의 next 포인터가 해당데이터를            가리키도록 수정하 고, 해당 데이터의 next 포인터가 원래 이전노드가 가리키던 다음 노드를 가리키도록 설정만             해주면 된다.

        (싱글 링크드 리스트일 경우. 이중을 경우 prev,와 next에 해당되는 포인터 모두를 수정)

     - 단순 연결리스트의 경우 head를 통해서만 접근하므로 앞 쪽에 데이터(노드)를 추가하는 것은 빠르다.

     - 이중 연결리스트의 경우 tail을 통해서도 접근이 가능하므로 앞,뒤쪽에 데이터(노드)를 추가하는 것은 빠르다.

 

  (3) 삭제

     - 삭제 역시 삽입과 마찬가지로 간단하다.

     - 이전 의 노드의 next 포인터를 다음 노드를 가리키도록 수정해 주면 된다.

        (싱글 링크드 리스트일 경우. 이중을 경우 prev,와 next에 해당되는 포인터 모두를 수정)

 

 

 

3. 배열과 연결리스트의 간단정리.

 

- 배열을 사용할 경우 index를 통한 접근이 간편하며, 이는 큰 장점이다

   저장할 데이터 수가 어느정도 정해져있고, 데이터들을 중간에 삽입,삭제가 많지 않을 떄 좋다.

  연속된 메모리 공간을 요구한다.

 

- 연결리스트를 사용할 경우, 데이터의 개수에 제한이 없고 , 연속된 공간의 메모리를 필요로 하지 않는다.

  데이터의 삽입, 삭제가 빈번하고 상대적으로 어떤 위치의 데이터에 대한 탐색이 적을경우 좋다.

  포인터에 대한 오버헤드가 발생한다.

'학부생 공부 > 자료구조' 카테고리의 다른 글

트리 (Tree)  (0) 2020.10.14
그래프 (Graph)  (0) 2020.05.03
벡터(Vector)  (0) 2020.02.15
큐(queue)  (0) 2020.02.14
스택 (Stack)  (0) 2020.02.13

1. 트리[Tree] 란?

- computer science에서 계층구조(hierarchical structure)를 가진 추상자료형

- 트리는 노드로 구성되어 있는데, 노드들은 부모-자식 (parent-child)관계를 가진다.

- 직장에서 부장-과장(1,2,3)-(대리1,2,3,4,5,6) 이 업무연관성에 따라 그려진 조직도를 떠올려보면 좋다.

- File System, Programming enviroment 등에서 사용된다.

 

 

2. 용어(Terminology)

- Root (node) : parent가 없는 노드

- Internal node : 적어도(at least) 자식을 하나이상 가지는 노드

- External node : 자식이 없는 노드

- Ancestors of a node(a) : node(a)의 parent,grand parent, grand-grandparent........etc

- Depth of a node(a) : number of ancestors (조상노드의 수)

- Height of a tree(a) : maximum depth of any node (가장 큰 깊이를 가진 노드의 깊이가 트리의 높이)

- Descendant of a node : child, grandchild, ..... etc

 

 

3. Method

-기본적인 methods 

-(1) Generic methods

     - int size()

     - bool empty()

-(2) Accessor methods

     - position root()

     - listh<position> positions()

-(3) Position-based methods

     - position parent()

     - list<position> children

-(4) Query methods

     - bool isRoot()

     - bool isExternal()

 

 

4. 탐색(순회)

- 트리 자료구조를 탐색하는 방법은 많지만 여기서는 기본적인 2개만 다루겠다.

-(1) 전위순회

     - descendants들을 방문하기 전에 자신의 노드부터 방문처리 하는 것이다.

-(2) 후위순회

     - descendants를 먼저 방문하고 자신을 마지막에 방문처리하는 것이다.

 

'학부생 공부 > 자료구조' 카테고리의 다른 글

배열(Array) 와 연결리스트(Linked List) 비교  (0) 2020.12.15
그래프 (Graph)  (0) 2020.05.03
벡터(Vector)  (0) 2020.02.15
큐(queue)  (0) 2020.02.14
스택 (Stack)  (0) 2020.02.13

vector는 오름차순 정렬 되어있어야합니다(이진탐색 기반이기 때문에)

'학부생 공부 > C++' 카테고리의 다른 글

(21.05.20) next_permutation  (0) 2021.05.20
C++ memory [heap]  (0) 2020.12.24
C++ memory [stack]  (0) 2020.12.22
c++의 포인터, 참조 타입 변수(레퍼런스)의 차이  (0) 2019.11.10
call by reference, call by value  (0) 2019.11.10

 

 ** 그래프

 - 정점들간의 관계를 표현하는 자료구조 ( G=(V,E) )

 - V는 Vertex(정점) 과 E는 Edge(간선) 을 의미하며 간선은 정점들 간의 연결관계를 표시합니다.

 - 간선 edge는 두 개의 정점이 있어야 정의가 됩니다 (cycle을 가지지 않을 경우)

 - directred graph(유향그래프) 와 undirected graph(무향 그래프) 가 있으며

 - 유향그래프에서는 vw와 wv는 다른 방향을 가지므로 다른 간선이다.

 - 가중치 그래프(weighted graph) 의 경우 (V,E,W)로 구성

 

 

 ** 그래프의 용어

 - 정점(Vertex) : 연결된 객체 (node)

 - 간선(Edge) : 정점들 간의 연결관계를 나타내는 선

 - incident : 정점과 간선의 관계에서 쓰는 용어 (정점에  간선이 연결된 경우)

 - adjacent : 정점과 정점간의 관계에서 쓰는 용어 (정점과 정점이 간선에의해 직접적으로 연결되어있는 경우)

 - 사이클(cycle) : 경로의 시작 정점과 끝 정점이 같을 경우

 - 차수(degree) : 정점에 연결되어 있는 간선의 수를 그 정점의 차수 라고 한다.

 

 

 ** 그래프의 구현

 - 보통 인접리스트로 구현을 하여, 인접 행렬으로도 구현 가능하다.

 - 인접행렬로 구현을 할 경우 두 정점이 직접 연결되어있는지 (adjacent) 를 O(1) 에 바로 알아낼 수 있다.

 - 그러나 어떤 특정 정점에 인접한 모든 정점들을 탐색하거나, 그래프의 간선의 수 등을 알아내려면

    O(n*n)이 걸린다 matrix를 모두 조사해야하므로....

 - 인접리스트로 구현할 경우 어떤 정점에 인접한 노드들은 바로 찾을 수 있다는 장점이 있다.

 

 

 ** 그래프의 탐색

 1. 깊이우선탐색(DFS, Depth-First-Search)

     - 정점을 탐색을 하는데 다음 연결된 정점을 탐색하기 전에 첫 정점과 연결된 정점을 우선 탐색

     - 모든 노드를 다 탐색하고자 할 경우 자주 사용한다.

     - 특정 정점에서 시작하여 원하는 다른 정점까지 경로가 있는지를 탐색할 때 사용하기도 한다.

 

 2. 너비우선탐색(BFS, Breadth-First-Search)

     - 탐색 시작 정점으로 부터 연결된 모든 정점을 먼저 탐색을 한 후 그 탐색한 정점과 연결된 다른 정점들을 탐색

     - 보통 최단경로를 찾는 문제에 BFS를 많이 사용한다.

     - 큐를 이용하여 구현을 많이 하는데 탐색정점과 연결된 정점들을 큐에 넣어서 탐색을 해가면서

     - 탐색한 정점은 큐에서 POP하고 그 정점에 연결된 새로운정점들을 큐에 PUSH해 준다.

     - 탐색을 시작할 때의 큐의 SIZE만큼 탐색을 하면 탐색 후에는 직접적으로 연결된 정점들은 모두 POP되었을 것이고

       탐색을 했던 정점들과 연결된 새로운 정점들이 큐에 들어와 있다.

'학부생 공부 > 자료구조' 카테고리의 다른 글

배열(Array) 와 연결리스트(Linked List) 비교  (0) 2020.12.15
트리 (Tree)  (0) 2020.10.14
벡터(Vector)  (0) 2020.02.15
큐(queue)  (0) 2020.02.14
스택 (Stack)  (0) 2020.02.13

1. DNS란?

 - 사람들은 각각을 구분해주는 예를들면 주민등록번호 같은 것 들이 있다 

 - IP address와 name을 binding

 - IP address를 직접 다루는 건 어렵기 때문에 다루기 쉽게 name으로 변환

 

2. Domain Name System

 - distributed database

 - application-layer protocol 이다.

 (core internet function 이지만 5계층 application-layer에 구현되어 있다.)

 

3. DNS services

 - 1. hostname to IP address translation

 - 2. host aliasing

 - 3. mail server aliasing

 - 4. load distribution (traffic을 분산시킨다.)

 

4. why not centralize DNS?

 (centralized DNS라면 )

 - single point of failure (그 서버하나가 죽으면 끝이다 이럴경우)

 - traffic volume (traffic이 몰림)

 - distant centralized database (먼 곳에서는 속도가 저하)

 - maintenance (유지보수가 어려움)

 - doesn't scale ! (확장성이 낮다)

 

5. a distributed, hierarchical database (관리가 편하다나는 장점)

6. DNS : root name servers

 - local name server에 접근해보고 없을 경우 root name server로 올라간다.

 - 전 세계적으로 13개의 root name servers가 있다.

 - 우리랑 가까운 지역의 root name server는 도쿄에 있다.

 

7. Local DNS name server

 - doesn't not strictly belong to hierarchy

 - " default name server"라고도 불리운다

 - 일단 여기서 찾아보고 없을경우 top level로 간다.

 - proxy server가 하는 역할과 비슷하다.

 

8. local DNS - root DNS

 - iterated query 방식 (local DNS에 로드가 많이 걸린다.)

 - recursive query 방식 ( like stack )

'학부생 공부 > 네트워크' 카테고리의 다른 글

OSI 7계층  (0) 2021.05.29
TCP(전송 제어 프로토콜) / IP(인터넷 프로토콜)  (0) 2021.05.28
SMTP (E-mail)  (0) 2020.04.12
FTP  (0) 2020.04.12
Web and HTTP  (0) 2020.04.06

1. SMTP??

 - application layer protocol (5계층)

 - TCP(4계층) 사용

 - 서버끼리 하는 direct transfer ( sending server to receiving server )

 - commands : ASCII text

 - response : status code and phrase

 - messages must be in 7-bit ASCII(text-based)

 - RFC 822

 

2. Three phases of transfer

 - 1. handshaking (greeting)

 - 2. transfer of messages

 - 3. closure

 

3. SMTP : final words

 - SMTP 는 persistent connections를 사용

 - uses CRLF (to determine end of message)

 

4. HTTP vs SMTP

 - HTTP : pull, 기본적으로 non-persistent 방식 (default)

    (URL을 치면 내가 거기가서 데이터를 당겨오는 방식)

 - SMTP : push, persistent 방식

    (server 가 push하는 방식)

 

5. 그외

 - POP : Post Office Protocol[RFC 1939] -authorization, download

 - IMAP : Internet Mail Access Protocol[RFC 1730] -manipulation of stored msgs on server.....

 - HTTP :  user agent를 사용하지 않고 web에서 바로 주고받는 경우 -gmail, hotmail.....

             ( 가운데 server를 하나 더 놓는 느낌 )

'학부생 공부 > 네트워크' 카테고리의 다른 글

TCP(전송 제어 프로토콜) / IP(인터넷 프로토콜)  (0) 2021.05.28
DNS (domain name system)  (0) 2020.04.13
FTP  (0) 2020.04.12
Web and HTTP  (0) 2020.04.06
TCP, UDP  (0) 2020.04.06

1. FTP 란?

 - the file transfer protocol

 - 원격의 호스트들끼리 파일을 주고 받을 때 사용하는 protocol

 - client / server 모델

 - RFC 959로 정의된다.

 - 주로 port 21번 사용

 

 

2. 특징

 - FTP client는 port 21번을 통해 FTP server와 contact

 - (using TCP)

 - server가 file transfer command 를 받으면, server는 2nd data connection 을 한다 (client 에게) 

 - 즉 2channel 통신이다.

 - "out of band"

 - ---> 데이터를 주고받는 band 외의 다른 band에서 control 정보를 주고 받는다.

 - "state" - (current directory, earlier authentication)

 

'학부생 공부 > 네트워크' 카테고리의 다른 글

DNS (domain name system)  (0) 2020.04.13
SMTP (E-mail)  (0) 2020.04.12
Web and HTTP  (0) 2020.04.06
TCP, UDP  (0) 2020.04.06
Application Layer  (0) 2020.04.04

+ Recent posts