AtraFelis's Develop Diary

어떤 테이블에서 특정한 값을 검색할 때, '이진 탐색'을 적용하기 위해서 만들어놓는 하나의 속성을 기준으로 정렬된 테이블의 사본을 index라고 한다.예를 들어, 어떤 커뮤니티의 게시글 정보를 저장하는 테이블에 천만 개의 정렬되지 않은 데이터가 들어가 있다고 가정하자. 여기서 *"작성자가 'AtraFelis'인 게시글만 찾아주세요*"라고 쿼리문을 날렸다고 했을 때 어떻게 되겠는가?ID작성자제목내용1AtraFelis  2홍길동  ...이춘향  1,000홍길동  ...AtraFelis  대충 이런 테이블이 있다고 생각해보자. 정렬되어 있지 않으므로 일단 이진탐색을 사용할 수 없을 것이다. 그렇다면 처음부터 일일히 비교를 하던가, 아니면 테이블 전체를 불러와서 정렬한 후에 이진탐색을 하던가... 뭐 여러가지 ..

IPv4는 32비트 주소를 사용한다. 개수로 따지면, $2^{32}$개 즉, 4,294,967,296개의 주소가 있는 셈이지만, 인터넷의 발달에 따라 대략 이 43억 개에 달하는 주소도 부족하게 되었다.이 때문에 여러가지 방안이 고안 되었는데, 장기적인 방안이자 해결책으로서 IPv6 주소 체계가 만들어졌다. IPv6는 128비트 주소를 사용한다. 즉, $2^{128}$개라는 어마어마한 수의 주소를 커버할 수 있게 된 셈이다.하지만 기존의 장비들을 한 번에 IPv4에서 IPv6로 바꿀 수는 없는 노릇이기에 IPv4를 부족한 데로 사용할 단기적인 방안이 필요했다. 그것이 이번 포스트의 주제이다.Classless AddressDHCPNATIPv4의 주소 고갈을 해결할 단기적인 방안은 이렇게 세 가지다. 이 글..

Silver I문제케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.오늘은 Baekjoon Online Judge의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 찾으려고 한다. 케빈 베이컨 수는 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합이다.예를 들어, BOJ의 유저가 5명이고, 1과 3, 1과 4, 2와 3, 3과 4, 4와 5가 친구인 경우를 생각해보자.1은 2까지 3을 통해 2단계 만에, 3까지 1단계, 4까지 1단계, 5까지 4를 통해서 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+1+2 = 6..

SIVLER I문제RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.1번 집의 색은 2번 집의 색과 같지 않아야 한다.N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.입력첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다..

TCP/IP 프로토콜은 기존에는 OSI 7계층으로 사용하였으나, 인터넷의 발달과 여러가지 이유로 5계층을 주로 사용한다. 최근에는 물리계층과 데이터링크 계층을 한 번 더 묶어 4계층으로 사용하는 듯하지만, 이 글에서는 TCP/IP 5계층에 대해 정리하고자 한다.Physical Layer(물리 계층) : bitsDatalink Layer(데이터 링크 계층) : framesNetwork Layer(네트워크 계층) : datagramsTransport Layer(전송 계층) : segments or user datagramsApplication Layer(응용 계층) : messagesTCP/IP 5계층은 이렇게 구성되어 있으며, 각 계층마다 다루는 데이터를 부르는 호칭이 다르다. 깊게 따질 것 없이, 이 계..

문제서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다.이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다. 매 게임시작 시 건물을 짓는 순서가 주어진다. 또한 모든 건물은 각각 건설을 시작하여 완성이 될 때까지 Delay가 존재한다.위의 예시를 보자.이번 게임에서는 다음과 같이 건설 순서 규칙이 주어졌다. 1번 건물의 건설이 완료된다면 2번과 3번의 건설을 시작할수 있다. (동시에 진행이 가능하다) 그리고 4번 건물을 짓기 위해서는 2..