기록하는 습관 "기습"

회선구성 둘 이상의 통신장치가 하나의 링크에 연결되는 방식이다. 링크는 하나의 장치로부터 다른 장치로 데이터를 보내는 물리적 통신로다. 종류는 3가지로 나뉘는데 다음과 같다. 점대점 point-to-point : 두 장치만 사용하는 단일 전용 링크를 제공한다. 다중점 multipoint : 두 개 이상의 장치가 단일링크로 공유하는 방식이다. 교환방식 switching : 교환기들로 구성된 네트워크를 통하여 여러 기기들 간에 데이터를 송수신하는 방식이다. 접속형태 물리 또는 논리적인 네트워크 구성 방법인데, 네트워크 링크의 물리적 또는 논리적 링크의 배열이다. 접속형태를 선택할 때 고려사항이 있다. 대등 대 대등 peer-to-peer : 장치들이 동등하게 링크를 공유하는 방식이다. (링형과 그물형이 있다..

지식표현 실제 문제를 지능적으로 해결하려면 많은 양의 지식을 필요로 한다. 그런데 이런 지식을 어떻게 효율적으로 표현하고 활용할 것인가는 인공지능에서 다루는 중요한 연구 분야 중 하나다. 컴퓨터로 지식을 이용하기 위해서는 컴퓨터가 효율적으로 이해할 수 있는 형식언어(Formal Language)로 기술되어야 한다. 다시 말해, 형식적으로 지식표현을 할 필요성이 있다. 지식을 컴퓨터에 표현하는데 사용되는 형식언어를 지식표현언어(knowledge representation language)라고도 한다. 지식을 표현할 때 고려해야 할 사항이 있는데 이는 다음과 같다. 어떤 객체와 관계를 어떻게 정확히 표현할 것인가? 술어 논리 표현에서 has-size(bear, big)일 때 bear2가 더 크다는 것은 어떻..

인공지능 인공지능은 인간의 지능을 모방하거나 대체하는 컴퓨터 시스템이나 소프트웨어를 말한다. 인공지능은 다양한 분야에서 적용되고 있으며, 인간의 일상생활과 사회에 많은 영향을 미치고 있다. 이번엔 인공지능에 대해 간단히 알아보겠다. 인공지능의 정의는 다양하다. Charniak & McDermott: AI is the study of mental faculties through the use of computational models. Winston: AI is the study of ideas that enable computers to be intelligent. Minsky: AI is getting a machine to do something which, if done by a human, is ..

B-Tree 검색트리가 방대하면 모두 메모리에 올려놓고 사용할 수 없다. 따라서 디스크에 넣어둔 상태로 작업해야 한다. 이는, 외부 검색트리에 해당한다. 외부검색트리일 땐 CPU보다는 디스크 접근 횟수가 효율을 좌우한다. 그리고 트리의 높이를 최소화하는 것이 유리하다. 이는 분기수를 늘리면 다진 검색트리가 되고 높이도 줄어든다. 10억 개의 키값을 가진 이진검색트리는 높이가 30이다. 256개의 분기를 가진 트리는 5의 높이를 갖는다. 이러한 분기는 블럭의 크기를 고려하여 결정한다. B-Tree는 결국 트리 균형을 유지하여 최악의 경우 디스크 접근 횟수를 줄인다. 또한, 다진검색트리로써 다음과 같은 특성을 갖는다. 루트노드를 제외한 모든 노드에서 [k/2]~k개의 키를 갖는다. 모든 리프 노드는 똑같은 ..

사회복지제도의 분석 소비자 이론을 응용해서 사회복지제도와 관련된 세 가지 지원방식의 차이를 비교해볼 수 있다. 여기서 어느 보조 방식을 쓰든 예산은 한정돼있다고 가정한다. 이렇게 하면 각 보조방식의 차이를 분명히 나타낼 수 있다. 그리고 비교의 편의를 위해서 두 개씩 각각 비교를 한다. 현금보조와 현물보조 현금보조는 말그대로 현금을 지원하는 것이고, 현물보조는 쌀이나 물, 라면과 같이 생활에 필요한 물품을 직접 주는 것이다. 보조를 받기 전인 기존 예산선은 선분 AB다. 여기서 만약 현금보조를 받는다면 예산선은 선분 CD로 이동한다. 그러나, 현물보조를 받는다고 가정하면 꺾인 선 AF'D이다. 이는 선분 BD만큼의 쌀을 공급받는다는 것을 알 수 있다. 이 두 경우의 차이는 꺾인 선 CF'A가 포함되어 있..

레드블랙트리 Red-Black Tree 이전 이진검색트리에서, 평균 수행시간이 O(log n)이라 했다. 그러나 트리의 균형이 나쁘다면 최악의 경우 n에 비례한 시간이 걸린다. 이를 보완하기 위한 '균형 잡힌 이진트리'가 바로 레드블랙트리다. 이진검색트리에 몇 가지 조건을 추가해서 균형 잡힌 트리가 되도록 한다. 트리의 높이, 검색/삽입/삭제 연산이 모두 O(log n)의 시간이 걸린다. 레드블랙트리는 모든 노드에 빨강 혹은 검정을 칠하되 다음과 같은 특성을 만족해야 한다. 루트는 블랙이다. 모든 리프(NIL, Null값과 같다)는 블랙이다. 노드가 레드면 그 노드의 자식은 반드시 블랙이다. 루트 노드에서 임의의 리프노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다. 참고로 레드블랙트리의 리프노..

검색트리 데이터의 저장과 검색은 자료구조와 알고리즘 분야에서 매우 중요하다. 수행시간에서 커다란 차이를 보이기 때문이다. 데이터의 저장과 검색을 효율적으로 하기 위해서는 적절한 자료구조 및 알고리즘의 사용을 필요로 한다는 사실은 자명하다. 만약 데이터가 들어오는 순서대로 배열에 저장한다고 가정해보자. 자료수가 n개일 때 수행시간은 다음과 같다. 새로운 자료 하나를 저장하는 시간은 Θ(1) 자료를 검색하는 시간은 Θ(n) 보다시피 검색에는 비효율적이다. 허나, 트리 모양 구조의 검색 트리에 저장한다면 어떨까? 저장과 검색, 둘 모두 Θ(log n)의 시간이 걸린다. 검색트리는 자식노드 갯수에 따라, 저장장소에 따라, 검색키에 포함된 필드수에 따라 분류된다. 다만 여기서는 언급하지 않겠다. 이진 검색트리 이..

지수의 문제 지수 index란 상품의 수량이나 가격에 생긴 평균적인 변화를 하나의 수치로 표현한 것이다. 여기서 수량지수와 가격지수로 나눌 수 있다. 수량지수 quantity index : 상품묶음의 양이 평균적으로 증가한 것인지 여부를 판별한다. 가격지수 price index : 상품가격의 평균적인 변화에 대해 알 수 있는 지수다. 수량지수 이질적인 상품들을 하나로 묶어 평균적인 수치로 나타내기 위해 고안된 개념이다. 각 상품의 양에 가격을 곱하고 이를 모든 상품에 대해 더해서 상품묶음의 전체 가액을 구한다. 선분 A0B0는 2004년의 예산선이고, A1B1은 2014년의 예산선이다. i를 보면 소비자는 2004년의 예산으로 Q0를 구매할 수 있었지만 2014년에 들어선 Q1를 구매할 수 있으므로 명백..

선택 알고리즘 Selection algorithm 눈 앞에서 각각 숫자가 놓여 있다. 1, 3, 5, 6, 7 ... 여기서 만약 3번째로 큰 원소를 찾아야 한다. 여기서 보통 O(n log n) 시간이 걸리는 정렬 알고리즘을 사용하여 정렬해놓고 위치를 찾을 수 있다. 하지만, 더 빠르게 찾을 수도 있다. 더욱 n에 비례하는 시간에 근접할 수 있는 알고리즘이 선택 알고리즘 selection algorithm이다. 선택 알고리즘에는 두 가지 유형이 있다. 평균적으로 선형시간(n에 비례한 시간)이 소요되는 선택 알고리즘을 말한다. (select라 보통 표현한다.) '최악'의 경우에도 선형시간이 보장되는 선택 알고리즘이다. (linearselect라 보통 표현한다.) 여기서는 일반적인 선택 알고리즘을 먼저 설..

예산제약 budget constraint 상품을 구입하는 목적으로 지출할 수 있는 소득의 일정한 크기를 의미한다. 자신의 소득을 m이라 가정하고 한 달의 쌀과 옷을 소득에 맞게 각각 구매 한다고 해보자. 그렇다면 나의 예산제약은 다음과 같다. Px X * PyY = M 상품묶음에 대해 분명히 파악하고자 한다면 위의 식을 y에 대해 풀어서 다음처럼 표현해야 한다. -(Px/Py)는 아래에서 보이듯 예산선의 기울기이며, M/Py는 y축 상의 절편이다. 아래와 같은 그래프가 완성되며 이는 예산선 budget line이라 한다. 소득을 전부 사용하였을 때 얻을 수 있는 상품묶음 집합을 그래프로 나타낸 것이다. 예산선의 기울기는 기회비용과도 관련이 있다. 기회비용이란, 어떠한 재화나 서비스를 구매하기 위해 포기하..