L.O.K

동적계획법(Dynamic Programing)이란? 복잡하고 어려운 문제를 작은 단위로 '분할'한 후 다시 '결합'하여 최적의 답을 구하는 방법 동적계획법은 분할된 모든 경우의 수를 검토한다. 중복되는 경우의 검토 비용을 줄이기 위해 기존의 결과를 저장한다. 피보나치 수열 F(n) = F(n-1) + F(n-2) F(n)은 F(n-1)과 F(n-2)로 나뉘어진다. F(n-1)은 F(n-2)와 F(n-3)으로 나뉘어진다. . . . 이처럼 가장 큰 단위가 작은 단위로 나뉘어지는 피보나치 수열은 동적계획법으로 풀기 적합하다. Top-Down F(7)은 피보나치 수열 공식에 따라 위 그림과 같이 분할되어 간다. F(1) = 1이고 F(0) = 0이라 주어지면 다시 위로 '결합'하며 올라간다. 이때 결과를 미리..

[인공지능] 전문가시스템 지금껏 포스팅했던 '탐색'으로 구현한 인공지능은 절차적 코드를 사용한다. 그러나 지능은 '탐색'으로만 구현되지 않는다. 전문가 시스템은 코드가 아닌 규칙으로 표현된 지식을 이용하여 좀 더 lordofkangs.tistory.com 지난 포스팅에서 '전문가 시스템'을 다루어 보았다. 전문가 시스템은 전문가가 지식베이스에 전문지식을 넣으면 추론 엔진으로 사용자가 원하는 정보를 추론하는 시스템이다. 그러나 과연 전문가가 넣은 지식이 100% 정확한 정보일까? 현실세계의 대부분의 정보는 '불확실'하다. 그러므로 우리는 불확실한 정보를 가지고도 올바른 결정을 내릴 수 있어야 한다. [인공지능] 조건부 확률 이번 포스팅에서는 '베이지 정리'를 이해하기 위한 기본적인 확률 개념을 다루어 볼 ..

이번 포스팅에서는 '베이지 정리'를 이해하기 위한 기본적인 확률 개념을 다루어 볼 것이다. ( 베이지 정리는 다음 포스팅에서 다룰 것이다. ) 확률이론 ( probability theory ) 인공지능 시스템에서 불확실한 정보를 갖고도 올바른 결정을 내리려면 '확률'이 필요하다. 확률이란, 특정 사건이 발생할 비율이다. 확률적 추론에서는 가장 높은 확률이 결론으로 선택된다. 상호배타성 절대 동시에 일어날 수 없는 두 사건 ( p , q ; p + q = 1 ) 독립사건 사건 p가 일어나도 사건 q의 확률에 영향을 주지 않으면 독립사건이다. 조건부 확률 두 사건 ( A, B )이 상호배타적이지 않을 때 ( A 와 B는 동시에 일어날 수 있음 ) 사건 B가 발생했을 때 (조건부), 사건 A가 발생할 확률 결..

[인공지능] 지식표현방법 ( 명제논리, 술어논리 ) 명제논리 참 또는 거짓을 판별 할 수 있는 문장 P : 마트는 월요일부터 토요일까지 영업한다. ( 지식 ) Q : 오늘은 월요일이다. ( 사실 ) R : 마트는 오늘 영업한다. ( 추론된 사실 ) 새로운 '사실'을 lordofkangs.tistory.com 명제는 참 또는 거짓으로 표현하지만 실제 세계는 그렇지 않다. 인간은 모호한(fuzzy) 표현을 자주 사용한다. 퍼지 논리란, 모호한 표현을 명확하게 표현하는 방법이다. 명제 논리 - 키가 크다. ( 1 ) - 키가 작다. ( 0 ) 퍼지 논리 - 키가 매우 큼 ( 1.0 ) - 키가 큼 ( 0.8 ) - 키가 약간 큼 ( 0.6 ) - 키가 작음 ( 0.0 ) 퍼지 논리는 '참'과 '거짓'이 아닌 ..

명제논리 참 또는 거짓을 판별 할 수 있는 문장 P : 마트는 월요일부터 토요일까지 영업한다. ( 지식 ) Q : 오늘은 월요일이다. ( 사실 ) R : 마트는 오늘 영업한다. ( 추론된 사실 ) 새로운 '사실'을 추론할 수는 있지만 새로운 '지식'을 만들 수는 없다. 논리 연산자 Q : 오늘은 일요일이다. NOT Q : 오늘은 일요일이 아니다. J : 옷은 파랑색이다. K : 옷은 스트라이프 무늬가 있다. J AND K : 옷은 파란색이고 스트라이프 무늬가 있다. 함축 : A → B A문장이 B를 함축한다. A 문장은 B를 함축한 문장이다 고로, A가 참일때 B는 반드시 참이 되어야 한다. A가 참일때 B가 거짓이면 거짓이다. A가 거짓이라면 B도 거짓일 수 있다. ( 참 ) A가 거짓이어도 B는 참일..

지식은 인공지능의 중요한 요소이다. 지식표현방법 1) 절차적모델 : 행동이나 절차를 표현 ( 규칙 ) 3) 선언적모델 : 사실이나 주장을 표현 ( 논리, 의미망, 프레임 ) 의미망 ( Semantic Network ) 방향그래프를 활용하여 개념 간의 관계를 표현 is a : ~의 일종이다. has : ~를 가지고 있다. 의미망은 인과관계를 표현하기에 좋지만 관계가 많아지면 유지보수가 복잡해진다. 표준지침이 없어 보편화된 표현방법이 없다. 프레임 ( Frame ) '객체(Object)'의 인공지능식 표현, 특정 객체에 속하는 속성을 표현하는 방법 슬롯은 속성을 의미한다. 슬롯의 값은 디폴트값 외에도 다른 프레임을 가리키는 프레임포인터나 슬롯에 이벤트( 요구, 변경, 제거 등)가 발생했을 때 동작하는 프로시..

예제) 원을 따라 주유소가 다섯 곳이 있다. 주유소마다 주유할 수 있는 기름양은 다르다. 자동차는 한 곳의 주유소를 선택하여 주유를 한 뒤 이동한다. 주유소를 거칠 때 마다 주유소에서 제공하는 기름양만큼 주유가 가능할 때, 자동차가 원 한 바퀴를 돌 수 있으려면 어떤 주유소에서 출발해야 하는가? 주유소A에서 시작해보자. A B C D E 5 4 3 도착X ( 자동차가 각 주유소를 출발할 때 기름의 양) 주유소B에서 시작해보자. B C D E A 1 도착X ( 자동차가 각 주유소를 출발할 때 기름의 양 ) 이렇게 하나씩 접근하면 오래 걸린다. Greedy한 접근법을 사용하면 쉽게 처리할 수 있다. ( 현재를 기준으로 최적의 선택을 하는 방법 ) 주유소A 부터 다시 해보자. 현재 기준 : 주유소 A A B ..

예제 ) 주어진 문자열을 파티션으로 나누려 한다. 파티션에 포함된 문자는 다른 파티션에서 발견되면 안 될 때, 파티션 개수의 최솟값을 구하라. c가 파티션1과 파티션2에서 발견되므로 이와 같은 분류는 안 된다. 알고리즘 Greedy한 접근법을 이용해보자. ( 현재값을 기준으로 최적의 선택을 하는 방법 ) 1) 문자열의 문자를 좌측부터 하나씩 포인터로 지목한다. ( 현재 포인터 ) 2) 현재 포인터가 가리키는 문자의 마지막 포인터가 현재 포인터라면 파티션을 분리한다. ( 현재포인터 = 마지막 포인터 ) 그럼 마지막 포인터 정보를 알아야한다. 반복문을 돌려 문자열의 문자를 하나씩 체크한다. 문자의 마지막 인덱스가 무엇인지 HashMap 자료구조에 저장한다. 이제 Greedy한 접근법을 다시 해보자. 현재 포..

예제 ) 최소 몇 개의 구간을 없애야 겹치는 구간이 없을까? 몇 개를 없애야 할지 직관적으로 보이지 않는다. 이런 경우 문제를 뒤집어 보는 것도 좋다. 몇 개가 겹치는가 → 몇 개가 겹치지 않은가? 알고리즘 1) 시간이 빠른 순으로 정렬한다. 2) 0 부터 시작하여 하나씩 겹치는 구간은 제거한다. Greedy 접근법 ( 현재를 기준으로 최적의 값을 찾아가는 과정 ) 현재값 : 0 1은 0과 겹치므로 제거한다. 현재값 : 0 → 2 2는 0과 겹치지 않으므로 남는다. 현재값 : 2 3은 2와 겹치므로 제거한다. 현재값 : 2 4는 2와 겹치므로 제거한다. 3) 겹치지 않은 구간 2개이다. 총 5개의 구간에서 겹치지 않은 구간 2개를 빼면 겹치는 구간은 3개이다. 고로, 최소 3개의 구간을 없애야 겹치는 구..

예제) 미팅 스케줄이 아래 그림과 같을 때, 최소 몇 개의 미팅룸을 잡아야 하는가? 미팅룸에 시작시간 순서대로 미팅이 할당된다. 현재 생성된 미팅룸 중에서 가장 빨리 끝나는 시간(END)보다 START 시간이 빠르면 미팅룸을 하나 더 생성한다. 현재 가장 빨리 끝나는 시간을 기준으로 미팅룸을 만들지 안 만들지를 판단 ( Greedy 알고리즘 ) 알고리즘 1) 가장 빨리 끝나는 미팅룸 시간을 구하기 위해 최소 Heap을 생성한다. 미팅2는 9시에 시작하므로 최소 Heap 11시보다 작다. 미팅룸을 하나 더 생성한다. 미팅3은 10시에 시작하므로 최소 Heap 11보다 작다. 미팅룸을 하나 더 생성한다. 미팅4는 12시에 시작하므로 최소 heap 11보다 크다. 최소 heap 11을 제거하고 Heap을 재정..