マツシタのお勉強

welcome to my engineering blog
Cracking the Coding Interview
AtCoder
Network
LeetCode
iOS
Hacker Rank

TCP/IPの基礎知識

TCP/IP TCP/IPのレイヤー構成 IPアドレス ポート番号 グローバルIP プライベートIP ネットマスク サブネット ブロードキャスト マルチキャスト ルーター ネットワーク

TCP/IP

コンピュータネットワークで広く用いられている通信プロトコル。TCP(Transmission Control Protocol)とIP(Internet Protocol)と呼ばれるプロトコルのセット。

TCP/IPのレイヤー構成

アプリケーション層 ... 具体的な通信サービスを実現する
トランスポート層  ... 高信頼性など目的に応じた通信品質を実現する(TCPが含まれる)
インターネット層 ... 中継などにより任意の機器同士の通信を実現する (IPが含まれる)
ネットワークインタフェース層 ... 直接接続された機器同士の通信を実現する

ある層で実現する機能は上位の層から利用される。


ネットワークインタフェース層の役割

ハードウェアで直接繋がっているコンピュータ同士が、相互に通信できるようにするための機能を実現する。

この層を構成する代表的なプロトコル

プロトコル 説明
イーサネット 有線LANで最も主流なネットワークの規格
Wi-F 無線を使いLANに接続するための規格
PPPoE イーサネットの上で１対１の接続を行うプロトコル
PPP PPPoEの元となったプロトコル
ARP/RARP IPアドレスからMACアドレスを得る/その逆(MACアドレスからIPアドレスを得る)


インターネット層の役割

複数のネットワークを繋いで、相互にパケットをやり取りする機能を実現する。

下位にあるネットワークインタフェース層は直接繋がったコンピュータ同士の通信を提供するが、インターネット層を用いることで、直接繋がっていないコンピュータ同士でも、相互に通信ができるようになる。

ルーティング

このそうで大きな役割を果たすのがパケットの中継機能。パケットを中継し、所定の方向に転送することをルーティングという。ルーティングによって任意の相手にデータを届ける事を可能にしている。

この層を構成する代表的なプロトコル

プロトコル 説明
IP 直接つながっていないネットワーク間で、パケットをルーティングする機能を提供するプロトコル。

IPはIPアドレスというコンピュータを識別するためのアドレスを用いてルーティングする。


トランスポート層の役割

インターネット層が作り出す任意のコンピュータ同士の通信接続をベースにして、ネットワークの使用目的に応じた特性をもつ通信を実現する。 具体的には、より信頼性の高い通信を可能にしたり、信頼性は低くても素早くパケットを送れるようにしたりする。

この層を構成する代表的なプロトコル

プロトコル 説明
TCP コンピュータ同士が行う通信にｍ信頼性の高さを付け加えたるプロトコル。最初に接続を作り、通信を終えたら接続を切る。再送や順序の入れ替えをするので、リアルタイム性には欠ける。
UDP インターネット層の機能をほぼそのまま使い、事前準備が不要で身軽な通信を実現するプロトコル。必要な時にすぐに相手にデータを送れ、到着しデータはすぐにアプリケーションに届く。


アプリケーション層の役割

個別のアプリケーション層が保つ機能を実現する層。 下位にあるトランスポート層が作り出す「目的に応じた通信機能」の中から、アプリケーションに適したものを選びｍそれを使ってアプリケーション同士がデータをやり取りする。

この層を構成する代表的なプロトコル

プロトコル 説明
HTTP Webへアクセスする。サーバーに対して情報取得を指示するリクエストや、その結果をサーバーが返すレスポンスなどの順序や書式が定められている
SMTP メールの送信やサーバー間の転送をする
DNS ドメイン名とIPアドレスを相互に交換する


IPアドレス

IPアドレスとは、IPと呼ばれるプロトコルを使うネットワークにおいて、各コンピュータを識別するために、コンピュータへ付与する番号の列。


ポート番号

ポート番号とは、コンピュータのどの機能を使用するか指定するための番号。トランスポート層にあたるTCPまたはUDPが提供する機能。 １台のコンピュータが複数の機能を持つ場合、IPアドレスを指定するだけでは複数ある機能のうちどれを使うかを示すことができない。IPドレスとポート番号の両方を指定することで、どのコンピュータのどの機能、といった指定が可能となる。

代表的なポート番号

ポート番号 プロトコル 用途
80 HTTP Webへのアクセス
443 HTTPS 暗号化したWebへのアクセス
20 FTP data ファイル転送


グローバルIPとプライベートIP

IPアドレスは以下の２つに分けることができる

グローバルIP

コンピュータを識別するために、世界で唯一となるように割り振られる。

プライベートIP

組織の内でネットワークで使用するもので、組織内で被っていなければ他の組織のプライベートIPと重複しても良い。


IPアドレスのクラスとネットマスク

IPアドレスは、左側のネットワーク部と右側のホスト部の２つによって構成されている。

ネットワーク部

あるネットワークを特定する情報。

ホスト部

そのネットワーク内のコンピュータを特定する情報。


また、IPアドレスにはクラスと言う概念がある。

IPアドレスにおけるクラス

クラスはA〜Eまであり、基本的にはA〜Cを使用する。それぞれの違いは、１つのネットワークアドレスの中で、何台のコンピュータを区別できるか、つまりネットワークの規模の違い。

クラス 用途
クラスA 大規模ネットワーク用。ネットワーク部が８ビットなので、残りのホスト部は24ビット。多くのコンピュータを区別できる。
クラスB 中規模ネットワーク用。ネットワーク部が16ビット
クラスC 小規模ネットワーク用。ネットワーク部が24ビット

ネットワーク部を知るためには、ネットマスクを使用する。 ネットワーク部に当たる部分を１にしたビット列をネットマスクと呼び、これとIPアドレスをAND演算するとネットワークを取り出せる。


サブネット化とサブネットマスク

サブネット化とは、規模の大きなネットワークを構築する際、１つのネットワークを小さなネットワークに分けること。

サブネット化のメリット

  • ブロードキャストが届く範囲を限定する
  • 故障が波及する範囲を最小限に抑える

ブロードキャストとは、ネットワーク内の全コンピュータへ一斉送信すること。個別に送ることによって生じる付加を軽減させることができるが、不必要なコンピュータに無駄な処理をさせ、ネットワークの通信能力を浪費してしまう。このブロードキャストが届く範囲を限定することで、浪費を抑えることができる。

サブネット化する方法

サブネット化する場合、IPアドレスの中のネットワーク部をさらに延ばして、サブネットを特定するための番号を確保する。その分ホスト部は短くなるので、サブネット内で使用できるコンピュータの数はその分少なくなるので注意。

また、サブネット化した時のネットワマスクを特にサブネットマスクと呼ぶ。


ブロードキャストとマルチキャスト

IPプロトコルを使った通信は１対１で行うものや１対多で行うものがある。

通信の種類 説明
ユニキャスト １対１で行う通信
ブロードキャスト 同じイーサネットに接続している全てのコンピュータに対してデータを届ける通信。ネットワーク内で行うため、他のネットワーク内のコンピュータには通信されない。
マルチキャスト あるグループに含まれる特定のコンピュータに足してデータを届ける通信


ルータの役割と機能

ルータは、相互に独立しているイーサネットワークの間に入って、両者の間でパケットを中継するもの。

ネットワークの基礎知識

ネットワーク 通信プロトコル OSI参照モデル LAN WAN パケット交換

ネットワークとは

ネットワークの働きは「アプリ同士が何かを行うためにデータをやり取りできるようにしてやること」。 それを実現するために、データを配送するためのルールや、使用する機器や通信媒体、サービス毎に決められたデータの形式や手順を覚えればOK。


通信プロトコルとは

通信プロトコルとは、「コンピュータが従うべきルール」の事。通信プロトコルは以下の２つから成る。

データ形式

情報をどのような形式で送るかを定めたもの

通信手順

どのような順序で何をやりとりするかを定めたもの

大抵の通信処理は複数の通信プロトコルを組合せて使用する。

通信プロトコルの標準化

通信プロトコルは、世界共通の規格として世界に好評されている。 ソフトウェアやハードウェアを開発する企業は、この公表された共通の規格にもとづいて開発する。

通信プロトコルはIETF(Internet Engineering Task Force)と呼ばれる団体が策定し、**RFC(Request For Comment)と呼ばれる英語文書として後悔されている。


レイヤー

通信プロトコルとは階層的に取り決められている。 「より共通的な機能」を下に置き、「より個別の機能」を上に置いて、上の機能が下の機能を利用する形で階層的に取り決められている。

レイヤー構造のメリット

レイヤー毎に仕事が明確に決まっているので、ある部分のレイヤーを組み替えることで別の操作を用意にすることができる。つまり、組み換えがしやすくなる。


OSI参照モデル

OSI(Open System Interconnection)参照モデルは、コンピュータネットワークに求められる機能を７つの階層に整理したもの。

レイヤー７：アプリケーション層(具体的な通信サービスを実現する。メール、Webなど)
レイヤー６：プレゼンテーション層(データの表現形式を相互変換する)
レイヤー５：セッション層(通信かの開始から終了までの手順を実現する)
レイヤー４：トランスポート層(信頼性の向上など用途に応じた特性を実現する)
レイヤー３：ネットワーク層(中継などにより任意の機器同士の通信を実現する)
レイヤー２：データリンク層(直接接続された機器同士の通信を実現する)
レイヤー１：物理層(コネクタの形状やピン数など物理的な接続を定める)

ネットワークアーキテクチャ

OSI参照モデルのようにどのような考え方や構成でネットワークを作り上げるかを定めた基本的な体系の事を「ネットワークアーキテクチャ」と呼ぶ。TCP／IPモデルもネットワークアーキテクチャの１つ。


LANとWAN

ネットワークは大きくLAN(Local Area Network)とWAN(Wide Area Network)の２つに分類できる。

LAN

LANは、オフィスや家庭などの１つの拠点内のネットワークを差す

WAN

WANは、拠点と拠点を結ぶためのネットワークを差す。


回線交換とパケット交換

あるで０たを目的の相手に向けて送り出すことを「交換」と言う。交換の方法は以下の二つがある。

回線交換

通信回線そのものをつなぎ替える方式。回線そのものを相手に繋ぐため、その相手にデータを送り出している間、その回線を占領できるというメリットがある。しかし、デメリットとして、データを送っていたに時でも回線を張っているので、その時は無駄に回線を占領してしまう。

パケット交換

やり取りしたいデータを、パケットと呼ばれる小さなサイズのデータに小分けして、それを共有の回線に乗せて運ぶ。近年はこの方法がよく用いられている。通信回線は皆と共有しているので、自分と相手は通信していなくても、他の人がそれを使う事ができる。

パケットの形

パケットは、データを一定サイズに小分けし、その前にヘッダを付加した形をとる。ヘッダには、それを届ける宛先や送信元の情報、含まれているデータに関する情報などが指定されている。

3Sum Closest : LeetCode

LeetCode 3Sum いもす法

Problem

leetcode.com

与えられたInt型の配列numsの要素の内、３つ選んだ要素の和がtargetに最も近い値を見つける問題。

Solution

全列挙によるO(N3)の解法

配列の全ての３つの要素の和を算出し、その中から一番targetに近い値を見つける事で問題を解くことができる。 この時、配列の要素数をNとすると計算量はO(N3)となる。

いもす法によるO(N2)の解法

探索を始める前に配列をソートすることで計算量を小さくすることができる。 選択する３つの要素のインデックスをそれぞれleft, mid, rightとすると、leftを固定し、３つの要素の和に対してtargetより大きければrightを−１し、小さければmidを＋１する。これleftを0 ~ N - 2まですることで計算量O(N2)で解くことができる。

Source Code

Maximum Size Subarray Sum Equals k

LeetCode HashMap

Problem

discuss.leetcode.com

Solution

This problem can be solved by using HashMap effectively. First, we store each sum of range from 0 to i (0 <= i < N). While we traverse the array, we check if the (sum - k) is stored in HashMap. If the number is in the map, the size of subarray that its sum equals k is i - hash.get(sum - k). This is the most important point.

Source Code