'2015-2학기'에 해당되는 글 13건

  1. 2015.09.09 2장 스택
  2. 2015.09.08 1장 개요
  3. 2015.09.08 1장. 리스트

1. 스택이란?

- 스택은 나중에 들어간 요소가 가장 먼저 나오는 (Last-In, First-Out:LIFO) 자료구조


2. 스택의 주요 기능 : 삽입과 제거

- 삽입(Push)



- 삭제(Pop)


3. 배열로 구현하는 스택

- 스택 구조체의 선언

typedef struct tagArrayStack{

int Capacity; /* 용량 */

int Top; /* 최상위 노드의 위치 */

Node* Nodes; /* 노드 배열 */

} ArrayStack;


- 스택의 생성

void AS_CreateStack(ArrayStack** Stack, int Capacity)

{

/* 스택을 자유저장소에 생성 */

(*Stack) = (ArrayStack*)malloc(sizeof(ArrayStack));

/* 입력된 Capacity만큼의 노드를 자유저장소에 생성 */

(*Stack)->Nodes = (Node*)malloc(sizeof(Node)*Capacity);

/* Capacity 및 Top 초기화 */

(*Stack)->Capacity = Capacity;

(*Stack)->Top = 0;

}


- 스택의 소멸

void AS_DestroyStack(ArrayStack* Stack)

{

/* 노드를 자유 저장소에서 해제 */

free(Stack->Nodes);

/* 스택을 자유 저장소에서 해제 */

free(Stack);

}


- 삽입(Push) 연산

void AS_Push(ArrayStack* Stack, ElementType data)

{

int Position = Stack->Top;


Stack->Nodes(Position)Data = Data;

Stack->Top++;

}


- 제거(Pop) 연산

ElementType AS_Pop(ArrayStack* Stack)

{

int Position = --(Stack->Top);


return Stack->Nodes(Position)Data;

}


4. 링크드 리스트로 구현하는 스택

- 노드 구조체

typedef struct tagNode

{

char* data;

struct tagNode* NextNode;

} Node; 


- 스택 구조체

typedef struct tagLinkedListStack

{

Node* List;

Node* Top;

} LinkedListStack; 


- 삽입(Push) 연산

void LLS_Push(LinkedListSTack* Stack, Node* NewNode)

{

if(Stack->List == NULL)

{

Stack->List = NewNode;

}

else

{

/* 최상위 노드를 찾아 NewNode를 연결한다.(쌓는다.) */

Node* OldTop = Stack->List;

while(OldTop->NextNode != NULL)

{

OldTop = OldTop ->NextNode;

}

OldTop->NextNode = NewNode;

}


/* 스택의 Top 필드에 새 노드의 주소를 등록한다. */

Stack->Top = NewNode;

}


- 삭제(Pop) 연산

Node* LLS_Pop(LinkedListStack* Stack){

/* 현재 최상위 노드의 주소를 다른 포인터에 복사해 둔다. */

Node* TopNode = Stack->Top;


if(Stack->List == Stack->Top)

{

Stack->List = NULL;

Stack->Top = NULL;

}

else

{

/* 새로운 최상위 노드를 스택의 Top 필드에 등록한다. */

Node* CurrentTop = Stack->List;

while(CurrentTop != NULL && CurrentTop->NextNode != Stack->Top)

{

CurrentTop = CurrentTop -> NextNode;

}

Stack->Top = CurrentTop;

CurrentTop->NextNode = NULL;

}


return TopNode;

}


5. 스택의 응용: 사칙 연산 계산기

- 중위 표기법 : 연산자가 피연산자의 가운데 위치

- 후위 표기법 : 연산자가 피연산자의 뒤에 위치


 중위 표기법

후위 표기법 

1 + 3 

1 3 + 

23 / 7 + 12 

23 7 / 12 + 

(117.32 + 83) * 49

117.32 83 + 49 * 

1 - 3 * 2 

1 3 2 * - 


- 후위 표기식 계산 알고리즘


- 중위 표기법에서 후위 표기법으로의 변환 알고리즘

+ 입력받은 중위 표기식에서 토큰을 읽는다.

+ 토큰이 피연산자이면 토큰을 결과에 출력한다.

+ 토큰이 연산자(괄호포함)일 때, 이 토큰이 스택의 최상위 노드에 저장되어 있는 연산자보다 우선순위가 높으면(왼쪽 괄호는 우선 순위가 가장 낮다.) 스택에 삽입하고, 그렇지 않다면 결과에 출력한다.

+ 토큰이 오른쪽 괄호 ')' 이면 최상위 노드에 왼쪽 괄호'('가 올때까지 스택에 제거 연산을 수행하고 제거한 노드에 담긴 연산자를 출력한다. 왼쪽 괄호를 만나면 제거만 하고 출력하지는 않는다.

+ 중위 표기식에 더 읽을 것이 없다면 빠져나가고, 더 읽을 것이 있다면 1부터 다시 반복한다.


 토큰

작업 

출력 

스택 

(117.32 + 83) * 49 

스택에 '(' 삽입 

 

(117.32 + 83) * 49 

117.32 출력 

117.32 

(117.32 + 83) * 49 

스택에 '+' 삽입 

117.32 

+ ( 

(117.32 + 83) * 49 

83 출력 

117.32 83 

+ ( 

(117.32 + 83) * 49 

스택의 모든 연산자 제거 후 출력 ('('는 출력 안함) 

117.32 83 + 

 

(117.32 + 83) * 49 

스택에 '*' 삽입 

117.32 83 + 

(117.32 + 83) * 49 

49 출력 

117.32 83 + 49 

(117.32 + 83) * 49 

식 모두 읽었음. 스택의 모든 연산자 제거 후 출력 

117.32 83 + 49 * 

 


'2015-2학기 > 알고리즘' 카테고리의 다른 글

3장 큐  (0) 2015.09.14
1장. 리스트  (0) 2015.09.08
Posted by OnewayK
,

1. 데이터 통신

- 전기 통신(telecommunication, 원격통신)은 먼 거리에서 행해지는 통신을 의미

- 데이터(data)는 데이터를 만들어 사용하는 사용자간에 합의된 형태로 표현된 정보

- 데이터 통신(data communication)은 전선과 같은 통신 매체를 통하여 두 장치간에 데이터를 교환하는 것.

* 데이터 통신의 목적 : 시공간을 초월한 정보 공유(전선과 같은 통신 매체를 활용)


- 데이터 통신 시스템의 기본 특성

+ 전달(delivery) : 정확한 목적지에 전달, 원하는 장치나 사용자에게 전달.

+ 정확성(accuracy) : 데이터를 정확하게 전달.

+ 적시성(timeliness) : 데이터를 적정 시간 내에 전달.

+ 파형 난조(jitter) : 패킷 도착 시간이 달라서 조금씩 음성이나 동영상 품질(quality)이 일정치 못함.


1-1. 데이터 통신 구성 요소



- 메시지(Message)

+ 통신의 대상이 되는 정보(데이터)

+ 문자, 숫자, 그림, 소리, 영상 또는 이들의 조합


- 송신자(Sender)

+ 데이터 메시지를 보내는 장치

+ 컴퓨터, 전화기, 비디오 카메라 등


- 수신자(Receiver)

+ 메시지를 받는 장치

+ 컴퓨터, 전화기, TV


- 전송매체(Medium)

+ 송신자에서 수신자까지 이동하는 물리적인 경로

+ 꼬임쌍선(twisted pair wire), 동축석(coaxial cable), 광케이블(fiberoptic cable), 레이저 또는 무선파


- 프로토콜(Protocol)

+ 데이터 통신을 통제하는 규칙들의 집합(상호 합의) - 반드시 해야함


1-2. 데이터 표현

- 문자(text) : 비트 패턴, 즉 0과 1로 된 비트들의 순차열로 표현.

+ 코드(code) : 부호를 표현하기 위한 비트 패턴들의 집합

+ 코딩(coding) : 부호를 표현하는 과정

+ ASCII : ANSI 표준 코드(7bit)

+ 확장 ASCII : 8bit

+ 유니코드(unicode) : 32bit 사용, 전 세계 모든 문자 표현


- 숫자(number) : 비트 패턴을 사용하여 표현

- 화상(image) : 픽셀(pixel), 해상도(resolution)

+ 흑백(1 또는 2 비트)

+ 칼라(RGB, 또는 Y(yellow), C(cyan), M(magenta))


- 음성(audio) : 연속 신호(소리나 음악)

- 동영상(video) : 연속적인 개체 또는 여러 화상의 조합(정지화상의 연속)


1-3. 데이터 흐름 방향

- 단방향 방식(simplex mode)

+ 한쪽 방향으로만 통신이 가능

+ 한 지국은 송신만, 다른 한 지국은 수신만 가능

+ 예 : 자판, 모니터



- 반이중 방식(half-duplex mode)

+ 각 지국들은 송,수신이 가능

+ 각 지국간 동시에 송신 불가

+ 예 : 워키토키, 민간방송용 라디오(CB radio)


- 전이중 방식(full-duplex mode)

+ 양쪽 지국간 동시에 송/수신이 가능

+ 양방향으로 통행이 가능한 2차선 도로와 같음

+ 신호는 링크의 용량을 공유(송수신 공간을 따로 설정해서 충돌이 안됨)해서 양방향으로 전달

+ 예 : 전화


2. 네트워크(Network)

- 통신 링크에 서로 연결된 장치(노드: node, 컴퓨터나 프린터)의 모임

- 작업을 여러 컴퓨터에 나누어 처리하는 분산처리(distributed processing)에 사용

- 네트워크 평가 기준

+ 성능(performance) : 전달시간(transit time), 응답시간(response time), 처리율(throughput)과 지연(delay)

+ 신뢰성(reliability) : 고장의 빈도 수, 고장 난 후 링크를 복구하는데 소요되는 시간

+ 보안(security) : 불법적인 접속이나 바이러스로부터 보호


2-1. 물리적 구조 : 연결 유형

- 점-대-점 회선 구성(point-to-point line configuration)

+ 채널의 전체 용량은 두 기기간 전송을 위해서 사용

+ 케이블이나 전선, 또는 극초단파나 인공위성 연결과 같은 방식도 가능

+ 텔레비전 채널을 바꿀 때 사용하는 적외선 리모컨


- 다중점(multipoint, 멀티드롭(multidrop))

+ 3개 이상의 특정 기기가 하나의 링크를 공유하는 방식

+ 채널의 용량을 공간적으로 또는 시간적으로 공유



2-2. 물리적 구조 : 접속형태(topology)

- 물리적 혹은 논리적인 네트워크 배치 방식



2-2-1. 그물형(Mesh) 접속 형태



- 모든 장치는 다른 장치와 점-대-점 링크

- n개의 장치를 서로 연결하기 위해 n(n-1)/2개의 채널이 요구

- n-1개의 입출력(I/O) 포트


- 장점

+ 원활한 자료 전송 보장 : 점-대-점 전용 링크 제공

+ 높은 안정성

+ 비밀 유지와 보안

+ 결함 식별과 분리가 비교적 용이


- 단점

+ 케이블의 양과 요구되는 I/O 포트 수

+ 설치와 재구성의 어려움


2-2-2. 스타형(Star) 접속형태



- 허브(hub)라는 중앙제어장치(central controller)와 전용 점-대-점 링크 구성

- 각 장치간 직접적인 통신 불가(허브를 통해야함)

- 모든 전송은 제어 장치를 통해 전송

- 1개의 채널

- 1개의 I/O 포트가 요구


- 장점

+ 그물형 접속형태보다 적은 비용

+ 설치와 재구성이 용이


- 단점

+ 허브가 고장나면 전체 시스템 고장


2-2-3. 버스형(bus) 접속형태



- 다중점 형태

- 탭(tap)과 유도선(drop line)에 의해 버스에 연결


- 장점

+ 설치가 쉽다.

+ 가장 적은 양의 케이블 사용


- 단점

+ 재구성이나 결함 분리의 어려움

+ 중추 케이블의 결함시 다수의 장치에 영향을 줌


2-2-4. 링형(ring) 접속형태



- 자신의 양쪽에 위치한 장치와 전용 점-대-점 회선을 구성

- 각 장치는 중계기(repeater) 포함


- 장점

+ 설치와 재구성이 쉽다.

+ 신호는 항산 순환.

+ 경보(일정 시간 내 신호가 수신되지 않을 시 위치를 경보) 사용


- 단점

+ 단방향의 경우 링의 결함 시 전체 네트워크 마비


- 해결책

+ 이중 링 또는 결함 지점의 단절 스위치 사용을 통해 해결


3. 네트워크 유형


- LAN(local-area network), MAN(metropolitan-area network): 국내에서 사용하지 않음, WAN(wide-area network)


3-1. 근거리 통신망(LAN)

- 개인소유 또는 단일 사무실, 건물 혹은 학교 등에 있는 장치들을 서로 연결하여 자원 공유를 목적으로 설계

- 버스형, 링형, 스타형 사용




3-2. 광역통신망(WAN)

- 국가, 대륙 또는 전세계를 포괄하는 광대역 영역에 데이터, 음성, 영상 및 비디오 정보의 장거리 전송 제공

- 거리 제한이 없음

- 통신회사가 임대를 목적으로 만들어 사용


a. 점-대-점(Point-to-Point) WAN



b. 교환형(switced) WAN



3-2-1. 네트워크간 연결(internetwork)

- 두개 이상의 네트워크가 서로 연결되어 있으면 "Internetwork" 또는 "internet"


- 두 개의 LAN과 하나의 WAN으로 구성된 네트워크간 연결



- 4개의 WAN과 3개의 LAN으로 구성된 네트워크


4. 교환(switch)

- 회선교환망(circuit-switched network)

- 종단 시스템 간에 회선이라는 전용선 이용



- 패킷 교환망(packet-switched network)

- 종단 간 통신은 패킷이라는 데이터 블록에 의해 이루어짐



5. 인터넷(Internet)

- 수 천개의 상호 연결되어 있는 네트워크로 이루어짐



+ 백본, 제공자 네트워크, 소비자 네트워크로 구성

+ 백본은 KT, LG U+, SKT 같은 통신사 소유

+ 백본망은 대등점(peering point)이라는 교환시스템에 의해 연결

+ 제공자 네트워크는 요금을 지불하고 백본 이용

+ 소비자 네트워크는 인터넷 말단으로 인터넷에서 제공되는 서비스 이용

+ 백본과 제공자 네트워크는 인터넷 서비스 제공자(Internet Service Provider, ISP) 라고 함

+ 제공자 네트워크는 국가 또는 지구 인터넷 서비스 제공자(national 또는 regional ISP) 라고 함


5-1. 초기 역사

- 1960년 이전 전선과 전화망

- 패킷 교환망 탄생 : 1961년 MIT의 클라언락에 의해 발표


-ARPANET

+ 미 국방성이 정보 공유를 위한 컴퓨터 연결 관심

+ 1967년 ARPA(Advanced Research Project Agency)는 ACM(Association for Computing Machinery)모임에서 각 호스트를 IMP(Interface Message Processor) 라는 특정 컴퓨터에 연결하고, IMP들을 서로 연결하는 ARPANET이란 아이디어 제안.

+ 1969년 4개 노드(UCLA, UCSB, SRI, UU)를 네트워크로 구성, NCP(Network Computer Protocol)라는 소프트웨어가 호스트간 통신 제공


5-2. 인터넷의 탄생

- 1972년 Vint Cerf와 Bob Kahn은 네트워크를 통하여 패킷을 전송하는 중계 하드웨어 역할을 하는 게이트웨이(Gateway) 개발


- TCP/IP

+ 1973년 종단-대-종단 패킷 전달을 위한 포로토콜 제안

+ 1977년 인터넷 시연(ARPANET, 패킷 라디오, 패킷 위성)

+ 네트워크간 연결 프로토콜을 TCP/IP로 부르기 시작

+ 1981년 UNIX 운영체제에 TCP/IP 포함 배포

+ TCP/IP가 ARPANET의 공식적인 프로토콜이 됨


- MILNET

+ 1983년 군사용 MILNET과 군사용이 아닌 ARPANET 분리


- CSNET

+ 1981년 NSF(미국과학재단)의 자원에 의해 ARPANET에 접속할 수 없는 대학들에 의해 고안

+ 전산학과가 있는 미국 대학들을 중심으로 구성


- NSFNET

+ 미국내에 산재된 5대의 슈퍼컴퓨터를 T1 라인(1.544Mbps) 으로 연결하는 백본(backbone)으로 미 전역에 대한 연결 제공


- ANSNET

+ IBM, Merit, MCI가 ANS(Advanced Networked Service)라는 비영리 기관을 통하여 구축한 고속 인터넷 백본 네트워크


5-3. 오늘날의 인터넷

- 월드 와이드 웹(WWW) : CERN 에 있는 팀 바너스리에 의해 개발

- 멀티미디어 : voice over IP(telephony), video over IP(skype), view sharing(YouTube), television over IP 등과 같은 멀티미디어 응용

- 대등-대-대등 응용 : peer-to-peer 네트워크


6. 표준과 관리 조직

6-1. 인터넷 표준

- 인터넷을 통하여 완전한 시험을 거쳐 사용되는 규격

- 반드시 지켜야 하는 협약된 규약

- 인터넷 드래프트(Internet draft)로 시작하여 상태에 따라 완성된 처리 절차를 가짐

- 인터넷 드래프트는 6개월의 유효기간을 갖는 작업 문서

- 드래프트 RFC(Request for Comment)로 발간(문서번호 지정)

- 완성 단계를 거친 후에 요구수준에 따라 분류



- 완성 단계

+ 제안 표준(proposed standard)

 = 인터넷 공동체를 통하여 많은 노력과 충분한 논의를 거친 안정된 규격

+ 드래프트 표준(draft standard)

 = 적어도 2번의 독자적인 성공과 상호 운용성이 이루어진 규격

 = 문제점은 계속적으로 수정이 이루어짐

+ 인터넷 표준(Internet standard)

 = 구현이 완전히 이루어진 규격

+ 기록 단계(historic)

 = 인터넷 표준이 되기 위한 단계를 통과하지 못한 규격

 = 역사적인 면에서 중요한 의미를 가짐

+ 실험 단계(experimental)

 = 인터넷 운영에 영향을 주지 않고 실험적인 작업 규격

 = 인터넷 서비스 기능으로 구현되지 않을 수도 있음

+ 정보 제공(informational)

 = 인터넷과 관련된 일반적이고 역사적인 튜토리얼 정보


- 요구 단계

+ 요구(required)

 = 모든 인터넷 시스템에서 최소한의 적합성 구현

 = 예 : IP, ICMP

+ 권고(recommended)

 = 최소한의 적합성이 요구되지 않음

 = 유용성이 있기 때문에 권고

 = 예 : FTP, TELNET 완성 단계

+ 기록 단계(historic)

 = 인터넷 표준이 되기 위한 단계를 통과하지 못한 규격

 = 역사적인 면에서 중요한 의미를 가짐

+ 선택(elective)

 = 요구도 권고 되지도 않은 등급으로 시스템에 유익할 경우 사용

+ 사용 제한(limited use)

 = 제한된 상황에서만 사용(실험 단계 RFC)

+ 미권고(not recommended)

 = 일반적인 용도에 적합하지 않은 것(기록 단계 RFC)


6-2. 인터넷 관리

- 인터넷 관리를 담당하는 조직



- ISOC(Internet Society)

+ 1992년 설립

+ 국제적인 비영리단체

+ 인터넷 표준 제정 지원

+ IAB, IETF, IRTF, IANA 등의 인터넷 단체 관리 및 지원

+ 인터넷과 관련된 학술 활동 및 연구 담당


- IAB(Internet Architecture Board)

+ ISOC를 위한 기술 자문 위원회

+ TCP/IP 프로토콜 그룹의 지속적인 개발 감독

+ 인터넷 공동체 연구원들에게 기술적인 조언 제공

+ IETF와 IRTF를 통하여 수행

+ RFC 문서 편집 관리

+ 다른 관련 기관과의 대외적인 창구 담당


- IETF(Internet Engineering Task Force)

+ IESG(Internet Engineering Steering Group)에 의해 관리되는 작업 그룹

+ 운영상의 문제점 파악, 해결책 제공

+ 인터넷 표준 규격 개발, 검토

+ 현재 9개의 작업반(working group)활동 : applications, internet protocols, routing, operations, user services, network management, transport, IPng, security)


- IRTF(Internet Research Task Force)

+ IRSG(Internet Research Steering Group)에 의해 관리 되는 작업 그룹

+ 인터넷 프로토콜과 응용, 구조, 기술과 관련된 장기간 연구 주제를 중점적으로 다룸

Posted by OnewayK
,

1. 링크드 리스트

1-1. 특징

- 배열과는 달리 유연하게 크기를 바꿀 수 있는 자료구조

- 각 노드는 다음 노드를 가리키는 포인터를 가짐.

- 각 노드를 다음 노드를 가리키는 포인터로 연결하여 만든 리스트. Single Linked List라고도 함.

- 링크드 리스트의 첫 번째 노드를 헤드(Head), 마지막 노드를 테일(Tail)이라고 한다.

- 헤드(Head) : 첫번째 노드의 주소값을 가지고 있음(Pointer Type)

- 테일(Tail) : 마지막 노드의 주소값을 가지고 있음(Pointer Type)


1-2. 단점

- 앞에 있는 노드를 찾아갈 방법이 없다.


1-3. 배열과의 차이점

- 리스트는 주소를 통해 다른 노드로 접근하나 배열은 index 값을 통해 접근한다.


1-4. C언어로 표현하는 링크드 리스트의 노드

 typedef struct tagNode{

int Data; // 데이터 필드

struct tagNode* NextNode; // 다음 노드를 가리키는 포인터

}


1-5. 노드의 추가





1-6. 노드의 삭제

1-7. 노드의 삽입


2. 더블 링크드 리스트

2-1. 특징

- 각 노드가 앞 노드/뒷 노드 양쪽에 대한 포인터를 모두 갖고 있어 각 노드들을 이중으로 연결하는 리스트.


2-2. 노드의 추가



2-3. 노드의 삭제



2-4. 노드의 삽입




3. 환형 링크드 리스트

- 우로보로스처럼 머리(헤드)가 꼬리(테일)를 물고 있는 형태의 링크드 리스트


3-1. 노드 추가

- 최초의 노드를 추가하는 경우(즉, 노드가 한 개 뿐)


- 리스트에 노드가 이미 한 개 이상 존재하는 경우에는 테일과 헤드 사이에 새 노드를 삽입한다.

- 코드

void CDLL_AppendNode(Node** Head, Node* HeadNode)

{

/* 헤드 노드가 NULL이라면 새로운 노드가 Head */

if((*Head) == NULL)

{

*Head = HeadNode;

(*Head)->NextNode = *Head;

(*Head)->PrevNode = *Head;

}

else

{

/* 테일과 헤드 사이에 HeadNode를 삽입한다. */

Node* Tail = (*Head)->PrevNode;


Tail->NextNode->PrevNode = HeadNode;

Tail->NextNode = HeadNode;

HeadNode->NextNode = (*Head);

HeadNode->PrevNode = Tail /* 기존의 테일을 새로운 */

 /* 테일의 PrevNode가 가리킨다. */

}

}


3-2. 노드의 삭제

-코드

void CDLL_RemoveNode(Node** Head, Node* Remove){

if(*Head == Remove)

{

(*Head)->PrevNode->NextNode = Remove->NextNode;

(*Head)->NextNode->PrevNode = Remove->PrevNode;


*Head = Remove->NextNode;


Remove->PrevNode = NULL;

Remove->NextNode = NULL;

}

else

{

Node* Temp = Remove;


Remove->PrevNode->NextNode = Temp->NextNode;

Remove->NextNode->PrevNode = Temp->PrevNode;


Remove->PrevNode = NULL;

Remove->NextNode = NULL;

}

'2015-2학기 > 알고리즘' 카테고리의 다른 글

3장 큐  (0) 2015.09.14
2장 스택  (0) 2015.09.09
Posted by OnewayK
,