School

Data Structure - Graph ( DFS, BFS )

DFS 이는 깊이 우선 탐색이라고도 하며, 루트 노드 ( 혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 deep하게 탐색하는 방법입니다. 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사합니다. 즉, 넓게(wide)탐색하기 전에 깊게(deep)탐색 하는 것입니다. 사용하는 경우 : 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택합니다. BFS 이는 너비 우선 탐색이라고도 하며, 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법입니다. 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나..

Java Programming - Socket

TCP/IP 소개 두 시스템 간에 데이터가 손상없이 안전하게 전송되도록 하는 통신 프로토콜입니다. TCP에서 동작하는 응용프로그램의 사례로는 email, FTP, 웹(HTTP)등이 있습니다. 이는 연결형 통신이라는 특징이 있습니다. 한 번 연결 후 계속 데이터가 전송가능합니다. 마치 친구와 전화를 걸고 받을 때처럼 말이죠. 그리고 보낸 순서대로 받아 응용프로그램에게 전달합니다. 소켓 (socket) TCP/IP 네트워크를 이용하여 쉽게 통신 프로그램을 작성하도록 지원하는 기술입니다. 소켓ㅇ리란 두 응용프로그램 간의 양방향 통신 링크의 한쪽 끝 단입니다. 소켓끼리 데이터를 주고받을 수 있으며, 소켓은 특정 IP 포트 번호와 결합합니다. 소켓에는 서버 소켓과 클라이언트 소켓이 존재하게 됩니다. 서버 소켓과 ..

Data Structure - Tree ( Forests )

Forests forest란 n>=0인 disjoint tree들을 말합니다. 우리는 이러한 forest를 가지고 활용을 할 겁니다. 먼저 다음과 같이 S1 = {0, 6, 7, 8}, S2 = {1, 4, 9}, S3 = {2, 3, 5}이렇게 있다고 해 봅시다. 이 들은 모두 disjoint한 set들입니다. 만약에 Si와 Sj가 disjoint한 집합들이면, Si union Sj가 존재하게 됩니다. 만약 S1과S2를 합치게 되면 아래와 같은 두 그림이 될 수 있습니다. Representation of Sets 우리는 이러한 집합들을 표현할 수 있는 방법을 정의해야 합니다. 우리는 root pointer가 각각의 set name에 해당하는 포인터를 가리키게 해야 합니다. 다음 과 같은 예시를 봅시다...

Data Structure - Tree ( Selection Tree )

Selection Tree 우리는 k개의 연속된 sequence가 있게 됩니다. 이를 우리는 runs라고 합니다. 이들은 모두 하나의 배열로 정렬되어 나올겁니다. 그리고 각각의 runs들은 오름차순으로 정렬되어 있습니다. 그리고 그 안의 값들을 key라고 합니다. 그리고 n을 우리는 이제부터 records의 개수로 정의할 수 있습니다. 그리고 위 runs sequence를 가지고 정렬을 하려면 merging task을 수행해 주어야 합니다. 반복적으로 가장 작은 키를 도출해 내면서 말이죠, 이 때 k - 1번의 비교가 필요하게 됩니다. 그리고 k > 2인 상황에서, 우리는 reduction작업을 통해 winner and loser tree를 구성해 낼 수 있게 됩니다. Winner Trees 우리는 이를..