본문 바로가기

분류 전체보기55

재귀 함수 이론 정리와 피보나치 수열 재귀함수 : 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 기법이다. 따라서 순환적으로 정의된 문제나 알고리즘을 풀기 적합하다. 예를들어 팩토리얼, 피보나치수열, 이항계수, 이진트리, 이진탐색, 하노이탑 문제를 풀기 적절하다. 재귀함수는 호출부분과 멈추는 부분으로 나뉘어진다. 멈추는 부분이 없으면 무한히 호출하게 된다. 장점: 알고리즘을 명확하고 간결하게 쓸 수 있다. 단점: 함수호출을 여러번 하므로 메모리와 속도면에서 성능이 떨어진다. 반복문보다 재귀가 더 빠른 경우가 있다. 재귀함수는 재귀호출을 할 때마다 더 작은 문제로 쪼개지는데, 선형적으로 작아진다면 시간복잡도는 O(n)으로 반복문과 동일하다. 문제를 반으로 쪼개서 해결하는 경우 시간복잡도는 O(logn)으로 효율적이다. Head Re.. 2020. 9. 6.
네트워크 마지막 강의 - Wireless and Mobile 네트워크 강의를 들으면서 정리한 노트를 완강하고 시간날 때마다 조금씩 블로그에 옮겨적었다. 사실상 네트워크 개론 강의였지만 큰 그림을 그리기 좋았다. Wireless와 Mobile에 대해서 알아보자. Wireless와 Mobility의 차이 Wireless : Link 가 Wireless 인 것을 의미한다. 집에서 노트북을 Wifi에 연결해 쓰는 경우 Wireless이지만 Mobility는 아니다. Mobility : 사용자가 움직여다니면서 네트워크 Access Point가 바뀌는 것을 의미한다. 노트북을 들고 다니면서 LAN선을 이용해 인터넷에 접속하는 것은 Mobility이지만 Wirelss가 아니다. Wireless의 특징 Path Loss : 시그널의 크기가 점진적으로 감소한다. 다른 Source.. 2020. 8. 16.
네트워크 20강 - 링크 계층 지난번 포스팅을 마지막으로 네트워크 레이어에 대해 공부했다. 이번 글에선 2번째 Layer인 Link Layer에 대해서 간단하게 공부해보자. MAC Address와 ARP MAC Address란? Mediam Access Control의 약자이다. 48비트의 주소를 가진다. 링크 계층(LAN 상에서)에서 NIC를 식별하기 위한 주소이다. NIC 생산 시에 하드웨어적으로 설정되어 있다. ARP란? Address Resolution Protocol의 약자이다. ARP는 네트워크 계층 프로토콜이다. ARP는 IP주소를 가지고 맥주소를 알아오는 역할을 한다. 맥주소를 알아야 링크 계층에서 통신이 가능하기 때문이다. ARP 테이블 로 구성된다. ARP를 이용해서 ARP 테이블을 만든다. TTL을 보통 20분 정.. 2020. 8. 16.
네트워크 19강 - 라우팅과 브로드캐스팅 지난 포스팅 BGP 복습 라우터는 새로운 Prefix Reachability를 알게 된다. eBGP나 iBGP advertisement를 통해서 알게 된다. 해당 Prefix에 대해 어떤 Output Port로 나갈 건지 결정한다. BGP Route Selection을 사용한다. Next Hop 라우터로 가기 위해서 OSPF를 사용한다. 해당 Prefix에 대해 어느 Output Port로 나가는지 포워딩 테이블에 기록한다. BGP Routing Policy Advertisement란? 포워딩을 해주겠다는 약속이다. AS 간 라우팅 Policy는 경제적 이득이 있을 때만 다른 AS에게 Advertisementm를 한다. Intra vs Inter AS 프로토콜 비교 Policy의 차이 Intra : 같은.. 2020. 8. 16.
네트워크 18강 - Routing In Internet 앞선 포스팅에서 라우터 내부 구조와 IP, 라우팅 알고리즘을 배웠다. 이것들은 미시적 관점에서의 라우팅이고 거시적 관점, 인터넷에서 어떻게 라우팅이 이루어지는지 살펴보자. Hierarchical Routing 계층적인 라우팅의 필요성 앞서 프로토콜은 복잡한 시스템이므로 기능별로 계층을 나누어서 구현했다. 인터넷도 복잡하고 거대한 시스템이므로 계층을 나누어서 라우팅하는 것이 적합할 것이다. 네트워크가 커지다보면 실제 데이터를 교환하는 것보다 라우팅 데이터를 더 많이 교환하는 상황이 올 수도 있다. 두 가지 문제 Scale Problem Administrative Autonomy 인터넷은 Network of Networks이다. 인터넷을 이루는 각 네트워크마다 관리자가 있다. 현실의 네트워크는 여러 어른들의.. 2020. 8. 16.
네트워크 17강 - 라우팅 알고리즘 지금까지 라우터의 Data Plane에 대해서 알아봤다. 이번 포스팅부터는 라우터의 두뇌 부분에 해당하는 Control Plane에 대해서 라우팅 알고리즘과 라우팅 프로토콜을 중심으로 알아보자. 라우팅 알고리즘 네트워크 상에는 여러 네트워크 장비들이 있다. 목적지까지 무작위 경로로 갈 순 없으니 경로를 설정해야 하는데 어떤 알고리즘을 사용할까? 라우팅 알고리즘의 분류 : Information Global 모든 라우터가 완전한 링크 정보를 알고 있다 Global한 라우팅 알고리즘을 Link State 알고리즘이라고 한다. 다익스트라 알고리즘이 해당된다. Decentralized 한 라우터는 이웃한 라우더들로 가는 Link 정보와 이웃한 라우터와 목적지까지의 거리를 알고 있다. Distance Vector .. 2020. 8. 16.
네트워크 16강 - ICMP 와 IPv6 이전에 IP 얘기를 하면서 TTL에서 ICMP 얘기가 잠깐 나왔던 것 같다. IP는 데이터 전송이 목적이고 ICMP는 데이터 전송에 대한 메타 데이터를 담당 한다. 즉 전송이 아닌 메타 데이터만 담당하므로 ICMP와 IP는 깊은 연관이 있다. 그리고 IP 주소 고갈 문제를 해결하는 IPv6를 살펴보자. ICMP Internet Contorl Message Protocol의 약자이다. IP 제어를 위해 사용되는 프로토콜이다. 오류 보고, echo reply/ request 를 담당한다. ICMP는 IP 데이터그램에 캡슐화된다. IP 패킷 페이로드 부분에 실린다. ICMP는 직접 전송을 담당하는 프로토콜이 아니기 때문이다. Type과 Code, 오류를 일으킨 IP 데이터그램의 첫번째 8바이트로 구성된다. T.. 2020. 8. 12.

티스토리툴바