기록하는 습관 "기습"

원시적인 naive 매칭 문자열 하나하나에 패턴문자열을 대조해보는 방법으로, O(mn)의 수행시간을 갖는다. 다만 이전에 비교했던 불일치 건에 대한 사실을 전혀 활용하지 못하기에 비효율적이다. Rabin-Karp 알고리즘 문자열 패턴을 수치화하여 문자열 비교를 수치비교로 대신한다. 수치화 방법은 다음과 같다. 가능한 문자 집합의 크기에 따라 진수가 결정된다. 만약 A = {a,b,c,d,e}이면, |A| = 5이다. 여기서 문자열 ad를 수치화한다고 했을 때 수치는 다음과 같다. 0*5^1 + 3*5^0 = 4 (4가 문자열 ad의 수치화, 맨앞의 숫자는 알파벳의 순서) 문자열 수치화로 문자열 매칭을 수행하려면 다음과 같은 문제점을 해결해야 한다. 수치화 작업의 부담 보통 하나의 문자열들을 일일이 계산하..

그리디 알고리즘 눈앞의 이익만 우선 추구하는 알고리즘을 총칭한다. 최적해를 찾을 수 있으면 찾지만, 없다면 그런대로 괜찮은 해를 찾아내는 것이 목표다. 이 때문에 대부분 최적해를 보장하지 못하지만 드물게 최적해를 보장하는 경우도 있다. 그리디 알고리즘으로 최적해가 보장되는 않는 예는 다음과 같다. 이진트리 최적합 경로 찾기 동전 바꾸기 배낭 문제 최적해가 보장되는 예는 다음과 같다. 최소 신장 트리 : prim, kruskal 최단 경로 : 다익스트라 회의실 배정 문제 여기서 몇가지를 뽑아서 설명하겠다. 동전 바꾸기 동전을 모아서 특정 액수를 만들되 동전의 개수를 최소로 하는 문제다. 다만 이 문제는 모든 동전의 액면이 일반적인 화폐의 유통과 같았을 때, 즉 500원, 100원, 50원, 10원일 때 그..

그래프는 정점 vertex와 간선 edge로 사물과 현상을 표현한 것이다. 이전에 다뤘기에 세세한 것은 넘어가겠다. 그래프의 표현 그래프를 표현하는 방법 중에는 인접 행렬, 인접 리스트, 인접 배열, 인접 해시테이블이 있다. 인접행렬은 간선 수 이상의 공간을 차지하고, 인접리스트는 특정 간선 존재 여부를 검사하는 데에 오래 걸린다. 이 두 단점을 커버할 수 있는 표현은 인접 배열이다. 인접배열은 정점 N개일 때 N개의 인접배열로 표현하는 것이다. 즉, 인접한 정점의 갯수만큼 배열을 또 생성한다. 인접리스트를 배열로 표현한다면 이해가 쉬울 것이다. 이때 간선 존재 여부의 수행시간은 O(log k)이다. 인접 해시테이블은 각 정점마다 인접배열을 두는 대신 하나의 해시 테이블을 사용하는 것이다. 인접한 정점이..

동적 프로그래밍 큰 문제에는 닮은 꼴의 작은 문제가 깃들기도 한다. 이를 해결한 것이 재귀적 알고리즘인데, 이 알고리즘은 잘 쓰면 효율적인 보약이지만 잘못 쓰면 치명적인 맹독이다. 재귀적 알고리즘 자체가 심한 중복 호출을 불러올 수 있기 때문이다. 이를 해결하기 위한 방법이 동적 프로그래밍이다. 심한 중복 호출이 일어나는 경우는 피보나치 수열과 행렬곱셈 최적순서 구하기가 있다. 이에 대해 알아보자. 피보나치 수 구하기 피보나치 수열의 정의는 다음과 같다. 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)])] 추론을 거쳣더 결론을 내려면 단일화가 필요하다. 이는 두 개의 술어논리문장을 합성할 때 필요한 절차다. 두 개를 합성할 때 ..