개발자의 기록장 블로그

logN의 시간복잡도를 가지려면 문제의 크기가 절반씩 줄어들어야 한다. 그렇다면 문제의 크기를 절반 씩 줄이는 것에 목표를 두자. power(3,5)라면, power(3,2) * power(3,2) * power(3,1) -> power(3,1)*power(3,1)*power(3,1)*power(3,1)*power(3,1)원래라면 5의 시간복잡도가 3이 됐다. 즉 y값에 따라서 문제의 크기를 절반씩 줄여주면 된다.  def power(x, y): if y == 0: return 1 if y % 2 == 0: return power(x, y//2)*power(x,y//2) else: return power(x,y//2)*power(x,y//2)*..

1. Brute Force기본 값으로 가장 첫 날의 수익을 지정 수익은 지금까지의 구한 수익 + 당일 수익 으로 구할 수 있다. def sublist_max(profits): profit = [profits[0]] for i in range(1, len(profits)): profit.append(profit[i-1] + profits[i]) return max(profit) 2. Divide and Conquer basecase는 start == end 수익율이 최대인 구간은 리스트 중앙을 기준으로 왼쪽에 있거나 오른쪽에 있거나 중앙을 관통할 수 있다.리스트를 좌 우 로 나누는 것은 재귀로 해결 중앙을 관통하는 구간의 최대값을 알기 위해서는 따로 함수의 분리 필요 -..

LAN계층은 좁은 지역에서 구성되는 네트워크로 전송효율을 중요시하는 연결방식이다. 효율은 상황마다 다르기 때문에 그 연결 형식이 다양하게 존재한다. 따라서 전송 선로의 특성과 매체간 연결 방식에 따른 처리 계층이 필요한데 이를  MAC계층에서 담당한다. 사실 LAN에서의 데이터링크계층은 두가지로 나뉜다. LLCMACLLC 계층은 일반적인 데이터 링크 계층의 기능을 수행한다. 뭐 오류제어라던지 흐름제어라던지...사실 WAN에서는 MAC계층이 존재하지 않는다. LAN의 다양한 연결형식 때문에 LAN의 데이터 링크 계층에 MAC 계층이 추가된 것이라고 생각하면 된다. MAC계층은 전송선로의 물리적 특성을 반영한다. 이는 LAN의 구조에 따라 다양하다. LLC계층은 큰 영향을 받지는 않지만 부분적으로 영향을 받..

데이터를 전송한다라는 것은 기본적으로 '누가' '누구에게' '무엇을' 보내는 것을 말한다. 누가와 누구에게는 당연히 송신호스트와 수신호스트이고 무엇은 데이터일 것이다.  데이터는 과연 네트워크망에서 어떻게 움직일까? 송신호스트가 수신호스트에게 받아라! 하면 받는 것은 아님이 분명하다.  데이터데이터는 데이터 링크 계층에서 프레임이라고 불린다. 프레임에는 문자프레임과 비트 프레임이 존재한다. 문자 프레임은 프레임 내용이 문자로 구성된 8bit의 고정된 길이를 가지며 비트 프레임은 프레임 내용이 비트로 구성된다. 문자프레임은 데이터 내용의 시작과 끝에 DLE'STX와 DLE'ETX ASCII 문자를 추가해 플레그와 데이터를 구분한다.만약 DLE문자가 데이터 내용에 포함된다면 문제가 발생할 수 있는데 이를 해..

오늘 날의 인터넷은 전화 교환기가 중개하는 음성통신서비스에서 컴퓨터 통신 환경으로 전환되면서 매우 활발히 쓰이고 있다. 인터넷은 라우터라는 네트워크 교환기가 패킷을 선로의 혼잡도에 따라, 다른 교환기의 고장 여부에 따라 경로를 전환해가며 전송한다. 이때 교환이라는 개념이 아주 중요히 사용되므로 이에 대해서 알아보자. 회선 교환 방식교환이란 송신 호스트에서 수신 호스트까지 올바른 경로로 중개해주는 것을 말한다. 교환 시스템은 연결형 서비스와 비연결형 서비스로 제공되는데, 회선교환방식과 패킷교환방식이 각각에 해당된다. 회선 교환 방식은 전화연결과 같다. 미리 경로가 정해지며 고정 대역폭을 할당받아 안정적인 데이터 전송이 가능하다. 경로가 일정하기에 데이터들이 모두 같은 경로로 움직이며 순서가 뒤바뀌지 않는다..

우리가 사용하는 인터넷, 즉 네트워크는 매우매우 크고 복잡한 시스템들의 집합이다. 하지만 이렇게 큰 시스템들도 사실 작은 여러 컴포넌트들로 이루어져있는데, 컴포넌트들을 이해한다면 큰 시스템을 자연스럽게 이해할 수 있다. 이를 다른 말로 모듈화된 시스템 계층이라고 말한다. 독립적으로 동작할 수 있으며 상호유기적으로 통합될 수 있는 모듈들로 시스템을 구성하면 크기를 늘리기도 쉽고 유지보수하기도 쉬우며 전체 구조를 모듈을 파악함으로써 쉽게 이해할 수 있다. 모듈화모듈은 큰 시스템을 구성하는데 있어서 필수적인 방법적 접근방식이다.  모듈끼리 통신하기 위해서는 적절한 인터페이스가 필요하며 이런 모듈은 상-하위 계층이 존재한다.(이전에 서비스를 주고받으면서 OSI7계층이 동작한다고 했었다!) 상위 계층(모듈)이 하..

어떤 학문을 배울 때 용어가 중요하다는 것은 누구나 알고있는 사실이다.  특히나 컴퓨터 네트워크란 학문은 개념적 학문이 아닌 실제로 구현되고 동작하는 컴포넌트들의 집합으로 설명되기 때문에 용어 하나하나의 의미에 민감할 수 밖에 없다.  따라서 공부를 시작하기에 앞서 용어 정리를 좀 하고나서! 진행하면 어떨까 해서... 네트워크는 활용되는 만큼이나 많은 용어들이 생기고 사라지고 하는 것 같다. 새로운 용어를 표현할 때 기존의 단어를 재활용 하거나 문자의 축약형을 사용하는 경우도 많이 보았다.(IP = Internet Protocol 같은 경우라던가...) 있는 그대로의 사전적 의미보다 올바른 용어의 활용처를 아는 것이 중요하겠다. 컴퓨터 네트워크컴퓨터 네트워크란 시스템들이 프로토콜을 이용해 통신하는 집합체..

다이나믹 프로그래밍은 이름처럼 문제 해결과정을 역동적으로 진행해 나가는 알고리즘 풀이 방식이다.예를들어, divide and conquer 방식의 경우 문제의 크기를 줄여나가면서 그 문제를 정복해 나가며 합치는 과정을 진행한다. 하지만! 다이나믹 프로그래밍은 단순히 문제의 크기를 나누어 가는 것이 아니라, 중복된 부분에 대한 효율적인 처리 방법에 대해서 고민한다. 어떤 때에 이 방식을 사용할 수 있을까?최적부분구조가 있을 때중복된 부분이 있을 때. 최적 부분 구조란 부분문제의 '최적의 답'을 이용해 전체 문제의 '최적의 답'을 찾을 수 있는 구조이다.  예를들어 피보나치의 경우 전체 큰 문제를 계속 나눠가며 그 값들을 합쳐 올라가는데, 이 나누어진 값들을 최적부분구조라고 한다. *divide가 된다면, ..