개발자의 기록장 블로그

네트워크 계층에서 가장 중요한 작업은 패킷의 이동경로를 정하는 작업, 즉 라우팅 기능을 적절하게 진행하는 것이다.경로를 선택함에 있어서 중요한 점은 혼잡제어와 패킷의 분할/병합이 필요하다. 라우팅라우팅은 라우팅 테이블을 가지고 경로를 결정하는 과정이다. 라우팅 테이블은 네트워크 상황에 따라 달라질 수도(동적 라우팅) 고정될 수도(정적 라우팅) 있다. 혼잡제어혼잡제어는 경로에 패킷 수가 과도하게 집중되면 발생하는 혼잡을 제어하는 것이다. 먼저 흐름제어와 혼잡제어를 구분해보자. 혼잡제어는 서브넷을 포함한 전반적인 네트워크의 전송능력을 다룬다. 흐름제어는 두 호스트 사이의 점대점 전송속도를 컨트롤 하는 것이다. 혼잡의 원인으로는 지나치게 많은 패킷의 유입이 있다. 패킷이 오버하게 오면 라우터가 이 내용을 패스..

데이터 링크 계층은 신뢰성있는 데이터 전송을 보장한다. 신뢰성이란 프레임 분실/변형등의 오류를 검출하고 복구하는 것을 말하며 이를 재전송 기법을 통해서 해결한다.  위 방법으로 논리적인 전송선로를 네트워크 계층에게 제공한다. 재전송 기법을 하기 위해서 일단 오류가 발생한 것을 감지해야 가능하다. 이를 위해서 데이터 전송원리 즉, 데이터를 선로를 통해 보내는 방법인 프로토콜에 대해서 알아보아야 한다. 데이터링크계층데이터 링크 계층에서는 호스트 끼리 1:1 연결돼있는 상태를 전제한다. 사실 연결의 의미는 자세히 말하면 전송의 의미와 비슷하다.  두 호스트가 점대점 방식으로 연결되있는 방식이 있고, 멀티드롭 방식으로 하나의 전송매체를 공유해 여러 호스트가 달려있는 경우도 있다. 후자의 경우 전송시에는 하나의 ..

이 문제는 예전에 최대 건물 높이 중에서 최소값이 빗물이 담길 수 있는  최대 값이라고 했었다.하지만 그렇게 하면 O(n^2)의 시간복잡도를 가지는데... 이를 해결하려면 최대 건물 높이를 미리 알아놓으면 좋을 것 같다. def trapping_rain(buildings): container = 0 left = [] right = [] for i in range(len(buildings)): left.append(max(buildings[:i+1])) right.append(max(buildings[i:])) for i in range(len(buildings)): container += (min(left[i], rig..

탐색이란 의미를 잘 살펴보자. 0번 인덱스 1을 취했을 때, 15가 되려면 11을 선택해야 될 가능성이 존재한다.이때 12는 15보다 작으므로 좌측 값을 늘려야한다. 1번 인덱스 2를 취했을 때 15가되려면 11을 선택해야 한다.이때 13이므로 좌측 인덱스를 늘린다.5와 11의 경우 15보다 크므로 우측 인덱스를 줄인다. 이런 방식으로 가다보면 값이 없는 경우는 O(n)이고 값이 있으면 탐색된다. def sum_in_list(search_sum, sorted_list): left = 0 right = len(sorted_list)-1 for i in range(len(sorted_list)): if sorted_list[right] + sorted_list[left] ..

위의 계단의 위치를 생각해보면, 1->2->3->42->3->41->3->42->4 이다. 즉 4번째 계단에 도착하려면 2번째 계단이나 3번째 계단에서 출발해야한다.식을 쓰면 stair(4) = stair(3) + stair(2)이고 이 식은 피보나치 식과 같다. def staircase(n): temp1, temp2 = 1, 1 for i in range(n): temp1, temp2 = temp2, temp1+temp2 return temp1  계단 올라가는 수를 조정한다면?   이 경우에도 마찬가지로 stair[n] 을 올라가려면 stair[n-k] + stair[n-l] + --- 이런 식이다.def staircase(stairs, possible_steps):..

1. BruteForce def max_profit(stock_list): max_profit_so_far = stock_list[1] - stock_list[0] for i in range(len(stock_list)): for j in range(i+1,len(stock_list)): max_profit_so_far = max(max_profit_so_far, stock_list[j] - stock_list[i]) return max_profit_so_far하나하나 보면서 모든 경우를 살펴보면 된다. O(n^2) 2. So_Far def max_profit(stock_list): max_profit_so_far = stock_list[1] ..

1. O(n) 저장소 활용  값이 없으면 딕셔너리에 저장하고, 값이 있으면 그 즉시 원소를 리턴해주면 된다. def find_same_number(some_list): container = {} for ele in some_list: if ele in container: return ele container[ele] = True 2. 저장소 활용하지 않고 풀기  사실 N+1 크기의 리스트에 1~N까지 자연수가 할당되려면 무조건 중복되는 놈이 하나씩 생긴다.그 중복되는 값만 찾으면 되므로 중복되는 녀석이 있는 범위를 좁혀나가면서 구하면 될 듯 하다.줄여 나간다는 것은 divide 한다는 것이고 이는 재귀적으로 문제를 해결해나간다는..

탈수가 나지 않으려면 현재 포인트에서 다음 포인트까지 물 소모량보다 물 용량이 작거나 같을때만 움직일 수 있다.만약 아니라면, 물을 채워주어야한다. 물을 채우면 다음 포인트까지 이동할 양도 빼주어야한다. def select_stops(water_stops, capacity): MaxCapacity = capacity capacity -= water_stops[0] container = [] for i in range(1, len(water_stops)): diff = water_stops[i] - water_stops[i-1] if capacity >= diff: capacity -= diff els..