기록하는 습관 "기습"

동적 프로그래밍 큰 문제에는 닮은 꼴의 작은 문제가 깃들기도 한다. 이를 해결한 것이 재귀적 알고리즘인데, 이 알고리즘은 잘 쓰면 효율적인 보약이지만 잘못 쓰면 치명적인 맹독이다. 재귀적 알고리즘 자체가 심한 중복 호출을 불러올 수 있기 때문이다. 이를 해결하기 위한 방법이 동적 프로그래밍이다. 심한 중복 호출이 일어나는 경우는 피보나치 수열과 행렬곱셈 최적순서 구하기가 있다. 이에 대해 알아보자. 피보나치 수 구하기 피보나치 수열의 정의는 다음과 같다. f(n) = f(n-1) + f(n-2) f(1) = f(2) = 1 이를 프로그램으로 구현하면 fib(n) { if (n = 1 or n = 2) then return 1; else return (fib(n-1) +fib(n-2)); } 여기서 수가 ..

집합의 처리 여기서 다루는 집합은 상호배타적 집합 disjoint set뿐이므로 교집합 연산은 다루지 않는다. 상호배타적 집합을 다루기 위해 필요한 연산은 다음과 같다. makeSet(x) : 원소 x로만 이뤄진 집합을 생성한다. findSet(x) : 원소 x가 속한 집합을 알아낸다. union(x, y) : x와 y가 속한 집합의 합집합을 구한다. 집합의 연산은 위와 같다. 다음은 위 집합의 처리를 할 때 가장 근본적으로 고려해야 할 집합의 구현방법이다. 연결리스트로 구현 : makeSet, findSet은 O(1), union은 O(log n)이 소요된다. tree로 구현 : makeSet, findSet, union에서 O(m)의 시간이 소요된다. 가장 효율적이다. 연결리스트로 집합 처리 각 원소..

인공신경망 인공신경망은 인간의 두뇌와 신경 시스템을 닮은 정보처리소자이다. 연결주의 기법으로써 뉴런들을 연결하여 문제해결 모델을 만든다. 인공 뉴런의 구조는 위와 같다. 위의 변형함수는 여러 가지가 있는데 하드리미터, 임계값, 시그모이드가 그것이다. 임계값은 어느 값을 기준으로 0과 1을 나누고, 시그모이드는 0과 1의 사이값을 취한다고 보면 된다. 하드리미터는 특정값보다 크면 1, 작으면 -1로 한다. 인공 신경망에서의 학습과정은 다음과 같다. 입력 값을 이용하여 인공 뉴런의 출력 값을 계산 인공 뉴런이 계산한 출력 값과 사용자가 기대하는 출력 값을 비교 기대하는 출력 값을 생성할 수 있도록 가중치 조절 이러한 인공신경망을 보여주는 대표적인 예가 단층인공뉴론 퍼셉트론이다. 퍼셉트론의 학습과정은 다음과 ..

학습이란? 비슷한 작업을 반복할 때 처음보다 나중에 하는 작업효율이 높아지도록 시스템을 변화시키는 것이다. 학습의 종류 귀납적 학습 - 일반화 연역적 학습 - 연역적 추론 방식 지도학습 : 학습된 데이터를 어떻게 마련하느냐가 중요 비지도 학습 : 자기학습 강화학습 기계학습에 필요한 요소는 데이터와 지식표현(논리, 프레임, 규칙, 의미망), 연산, 개념공간, 휴리스틱 탐색이다. ID3 알고리즘 Iteractive Dichotomiser (반복 양분) 3 알고리즘으로 학습결과를 의사결정(하향식) 트리 형태로 표현하는 것이다. ID3 알고리즘에서는 정보이론을 다루는데 이는 정보의 양을 측정할 수 있는 수학적 근거이다. 예를 들어, 특성 P의 정보는 양은 Information gain(P)이며, 이는 전체정보의..

1. IPv4 주소의 길이는 _비트이다. a. 16 b. 128 c. 32 d. 64 2. IPv4 주소는 일반적으로 _진 표기법 또는 점 10진 표기법으로 표기된다. a. 16 b. 265 c. 10 d. 64 3. 클래스기반 주소지정에서 IPv4 주소는 _개의 클래스로 나누어진다. a. 3 b. 4 c. 5 d. 6 4. 클래스 A에서 netid는 _이다. a. 0에서 127 b. 128에서 191 c. 192에서 223 d. 224에서 255 5. 클래스 B에서 netid는 _이다. a. 0에서 127 b. 128에서 191 c. 192에서 223 d. 224에서 255 6. 클래스 C에서 netid는 _이다. a. 0에서 127 b. 128에서 191 c. 192에서 223 d. 224에서 255..

확률이란 특정사건이 일어나거나 일어나지 않을 기회의 정도를 나타낸다. P(x) = 특정사건 x가 일어난 횟수 / 전체사건이 일어난 횟수 여러 사건들로 구성된 공간에서 복수개의 사건에 대해 어떤 사건 A 또는 B가 일어날 확률은 다음과 같다. 예를 들어 카드놀이에서 사용되는 52장 중에서 한 장을 뽑았을 때 그 카드가 ace이거나 heart일 확률은? 동시에 일어나는 사건이 서로 독립적일 경우의 식은 다음과 같다. P(A ∩ B)=P(A)P(B) 여기서 조건확률도 아는 것이 좋다. 한 사건 b가 일어난 상태에서 a가 일어날 확률은 다음과 같이 표현하고 계산할 수 있다. P(A|B) B가 일어난 상태에서 A가 일어날 확률 bayes 정리는 사후확률을 구할 수 있으며, 사건 A가 일어났을 때의 확률 을 계산함..

명제 참 또는 거짓만을 값으로 가질 수 있는 문장이다. 무조건 서술문이고 참 거짓 판별이 가능해야 한다. 예를 들어, "울릉도는 섬입니까?"와 "치킨 먹는 것은 참이다."는 명제가 될 수 없다. 전자는 서술문이 아니고, 후자는 참과 거짓을 판별할 수 없다. 아래는 명제기호이다. P -> 자동차엔진이 고장이다. Q -> 운전할 수 없다. P -> Q 자동차엔진이 고장이면 운전할 수 없다. 논리 논리는 명제논리와 술어논리로 나눌 수 있다. 명제를 이용한 논리는 명제논리, 이는 개별 요소를 표현할 수 없다. 이를 다음과 같이 표현한다. P (∃y[woman(y)∧loves(x,y)])] 추론을 거쳣더 결론을 내려면 단일화가 필요하다. 이는 두 개의 술어논리문장을 합성할 때 필요한 절차다. 두 개를 합성할 때 ..

또 나만 보려고 만든 요약본 단기금융시장 통상 만기가 1년 이내인 금융상품이 거래되는 시장이다. 단기금융시장은 여러 종류가 있다. 다음은 이에 대한 설명이다. 환매조건부매매시장 : 일정시간 경과 후 일정가격으로 동일 채권을 다시 매수하거나 매도할 것을 조건으로 채권거래가 이뤄지는 시장이다. 자본시장 장기자금 조달 수단인 주식이나 만기 1년 이상의 채권이 거래되는 시장이다. 통화안정증권시장 : 통화량의 구조적 조절을 위해 발행하는 통화안정증권을 발행 유통하는 시장이다.] 자산유동화증권시장 : 저유동성 자산을 유동화하기 위해 발행되는 증권을 유통하는 시장이다. 파생금융상품시장 상품의 가치가 채권, 주식, 통화의 가치 변동에 따라 결정되는 금융상품이 유통되는 시장이다. 옵션 : 자산을 미리 정한 미래의 가격으..

IP 주소 네트워크층에서는 모든 장치와 서로 통신할 수 있도록 연결된 장치를 유일하게 구분할 수 있는 방법이 필요하다. 인터넷에 연결된 각 장치를 구별하기 위해 IP계층에서 사용하는 식별자를 인터넷 주소 또는 IP주소라고 한다. 한 장치가 두 개의 네트워크와 연결되어 두 개의 IP주소를 가질 수 있지만 똑같은 IP주소를 두 장치가 가질 수는 없다. 허나 여기서 알아둬야 할 것은 IP주소는 유일하긴 하지만 바뀔 수 있다는 것이다. IPv4 주소는 32비트 길이의 주소이며, IPv4 같은 프로토콜에서 사용되는 주소의 총 개수를 주소공간이라 한다.IPv4 주소의 주소공간은 2^32개, 40억 개 이상이다. IP주소를 나타내는 데에 3가지 표기법이 있는데, 각각 이진 표기법, 16진 표기법, 점 10진 표기 법..

교환 switching 메시지를 발신지에서 목적지로 전달하는 과정에서 많은 결정이 이뤄진다. 메시지가 연결장치에 도착할 때 패킷을 송신할 출력포트를 결정하는 것도 그렇다. 패킷이 라우터(교환기)의 한 포트에 도착하면 이 패킷은 다른 포트를 통해 다음 교환기로 전달된다. 이 과정을 교환(switching)이라고 하며 이 과정은 연결장치(라우터)에서 수행된다. 교환의 종류는 다음과 같은 두 가지다. 회선 교환 패킷 교환 회선 교환 circuit switching 대부분 네트워크층에서 구현되지 않고 물리층에서 구현된다. 메시지를 전달하기 전에 발신지와 목적지 사이에 물리회선(링크)를 생성한 후 메시지를 전달한다. 발신지는 메시지를 전달하면 네트워크에 통보하고 네트워크는 다른 연결을 위해 연결을 해제한다. 여기..