공부 정리

트리의 개념 비선형 구조 원소들 간에 1:n 관계를 가지는 자료구조 원소들 간에 계층관계를 가지는 계층형 자료구조 상위 원소에서 하위 원소로 내려가면서 확장되는 트리(나무)모양의 구조 노트(node) - 트리의 원소 ex) 트리 T의 노드 - 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14 간선(edge) - 노드를 연결하는 선으로 부모 노드와 자식 노드를 연결 루트 노드(root node) - 트리의 시작 노드 ex) 트리 T의 루트 노드 - 1 형제 노드 (sibling node) - 같은 부모 노드의 자식 노드들 ex) 2, 3은 형제 노드 조상 노드 - 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들 ex) 8의 조상 노드: 4, 2, 1 서브 트리(subtr..

* Emoji? 1997년 일본 휴대폰에서 시작된 이모지는 여러 모바일 운영체제에 추가된 후 2010년대에 전세계적으로 인기를 얻기 시작해, 요즘에도 선풍적인 인기를 끌고 있다. 이모지와 이모티콘은 다른 것이며 이모티콘은 텍스트의 형태이고 이모지는 픽토그램, 인코딩된 문자로 표현될 수 있는 그림이라는 차이점도 있다. * Character Set 바꿔주기 어쨌든 그냥 이모지가 포함된 글을 저장하려고 하면 error가 뜨거나, 이모지 부분이 ?를 뜨는 등 에러가 발생하게 된다. 이 에러가 발생하는 이유는 mysql 세팅이 utf-8로 되어있는 경우에 발생하는데, utf-8은 한 문자를 나타내기 위해서 1바이트에서 4바이트까지 사용한다. 그런데 MySQL의 경우 utf-8을 3바이트 가변 인자로 구현하고 있다..

* PRIM 정의 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어 가는 방식. 그리디 알고리즘이다. 임의의 정점을 하나 선택해서 시작한다. 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택한다. 모든 정점이 선택될 때 까지 1번과 2번의 과정을 반복한다. 서로소인 2개의 집합(2 disjoint-sets) 정보를 유지한다. 트리 정점들(tree vertices) - MST를 만들기 위해 선택된 정점들 비트리 정점들(non-tree vertices) - 선택되지 않은 정점들 프림 알고리즘은 싸이클링 여부를 체크할 필요가 없다. 왜냐면 연결되지 않은 정점들만 찾으므로 * PRIM 적용 예 * PRIM Algorithm Code for Java import ja..

먼저 알아야 하는 것 : MST, Union-Find Union-Find Algorithm 이걸 카테고리를 알고리즘으로 해야하는지... 자료구조로 해야하는지... * Union-Find (= disjoint-set / merge-find) 알고리즘 Union-Find 알고리즘은 2개의 기능을 가지고 있는 알고리즘이다. 1. Find : 어느 부.. superbono-2020.tistory.com * Kruskal 정의 간선을 하나씩 선택해서 MST를 찾는 알고리즘. 그리디 알고리즘의 한 종류이다. 간선 리스트를 작성한다. 최초, 모든 간선을 가중치에 따라 오름차순으로 정렬한다. 가중치가 가장 낮은 간선부터 선택(두 정점을 해당 가중치의 비용으로 연결한다)하면서 트리를 증가시킨다. -> 사이클이 존재하면 ..

* 그래프에서 최소 비용 문제 1. 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리 -> 최소 신장 트리 2. 두 정점 사이의 최소 비용의 경로 찾기 * 신장 트리 - n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리 * 최소 신장 트리(Minimum Spanning Tree) - 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리 * MST의 특징 사이클이 포함되어서는 안된다. 간선의 가중치의 합이 최소여야 한다. -> MST의 정의 * 현실에서의 MST 현실에서의 예를 들자면 케이블 회사가 클라이언트를 모두 연결하면서 케이블을 연결하는 비용을 최소로 하고 싶을 때 등이 있다. MST의 알고리즘에는 KRUSKAL과 P..

* Sliding Window Protocol? www.youtube.com/watch?v=zY3Sxvj8kZA&ab_channel=KhurramTanvir Slinding window(슬라이딩 윈도우)는 패킷 기반의 데이터 전송 프로토콜이다. 이 프로토콜은 데이터 링크 계층, TCP와 같은 패킷의 신뢰성 있는 전달이 필요할 경우 사용된다. 보통 신뢰성 있는 데이터 전송에 대해서는 모든 패킷에 대해서 정상적으로 정상적으로 전달되었음을 알리는 확인 신호(acknowledgement, 이하 ACK)를 받아야한다. 만약 패킷이 중도에 잘못되었거나 분실되어 확인받지 못하는 경우, 해당 패킷을 재전송해야한다. 이 과정은 시간이 오래 걸리기 때문에 효율성이 떨어진다. 슬라이딩 윈도우 프로토콜은 일정한 윈도우 크기 ..

* Load Balancing? Load Balancing(로드 밸런싱, 부하 분산)은 컴퓨터 네트워크 기술의 일종으로 여러 개의 컴퓨터 자원들에게 작업을 나누는 것을 의미한다. 이 때 컴퓨터 자원은 CPU, Storage, Server 등이 될 수 있다. 로드 밸런싱을 통해 가용성 및 응답 시간을 최적화할 수 있다. 또한 인터넷 서비스에 로드밸런싱을 적용하면 내부 네트워크 구조를 숨길 수 있으므로 크래킹을 막을 수 있는 보안적 이점을 얻을 수 있다. * Load Balancer? 서버에 가해지는 부하(Load)를 분산(Balancing)해주는 장치 또는 기술을 통칭한다. 한 대의 서버로 부하가 집중되지 않도록 트래픽을 분산 관리해주어 각각의 서버가 최적의 퍼포먼스를 보일 수 있도록 해준다. * 트래픽 ..

* URI? 특정한 리소스의 식별자이다. * URL? HTTPs, FTP 등 어떻게 접근하지는지도 알 수 있게 해주는 특별한 타입의 식별자 특정 서버 안에서 해당 리소스에 접근할 수 있는 상대적인 위치(Location)를 나타낸다. (ex. http://www.google.com/doodles) url은 해당 리소스에 접근하는 절대적인 위치가 아닌 상대적인 위치를 말하기 때문에, 리소스가 옮겨지면 이전 url은 유효하지 않게 된다. * URN? URN은 리소스의 Name을 알려준다. 따라서 위치에 영향을 받지 않는 unique함을 나타내는 키 역할이 수행 가능하다. 앞서 URL은 리소스가 옮겨지면 이전 URL이 유효하지 않게 된다고 했지만 URN은 그렇지 않다. 출처 - goodgid.github.io/..

사실 TCP/UDP의 차이를 명료하게 정리하고자 글을 다시 쓴다. * TCP(Transmission Control Protocol)? 이름에서도 알 수 있듯 전송 제어 프로토콜이다. 인터넷을 사용하는 모든 통신의 기본적인 프로토콜이며 신뢰성 있는 데이터 전송을 보장한다. 연결 지향형(connection-oriented) 서비스를 제공한다. 전송 계층(transport layer)에서 동작한다. 다른 타입의 컴퓨터 간에 연결을 설정하는데 도움이 된다. 운영 체제와는 상관 없이 독립적으로 작동하며 많은 라우팅 프로토콜을 지원한다. - 동작 3 way handshake 방식을 통해 established 되며 연결이 설정된 뒤 데이터 전송이 시작된다. - 특징 - 전송(수신)확인 - 재전송 - 네트워크가 혼잡할..

* TCP 3 way handshake? TCP/IP 네트워크에서 서버와 클라이언트를 연결하는데 사용되는 프로세스이다. 실제 데이터 통신 프로세스가 시작되기 전에 클라이언트와 서버가 동기화 및 승인 패킷을 교환해야하는 3단계 프로세스이다. TCP는 UDP와 달리 정확한 전송을 보장하는데 이를 위해 상대방 컴퓨터와 사전에 세션을 수립해야 함. * TCP 메세지 유형 & 포트 상태 유형 -TCP 메세지 유형 메세지 사용 SYN 연결을 시작하고 설정하는데 사용된다. 장치간에 시퀀스 번호를 동기화하는데 쓰인다. ACK 상대방이 SYN을 수신했는지 확인할 때 SYN-ACK 로컬 장치의 SYN 메세지 및 이전 패킷의 ACK FIN 연결을 종료 - 포트 상태 유형 Closed 포트가 닫힘 Listen 포트가 열린 상..