L.O.K

동적계획법(Dynamic Programing)이란? 복잡하고 어려운 문제를 작은 단위로 '분할'한 후 다시 '결합'하여 최적의 답을 구하는 방법 동적계획법은 분할된 모든 경우의 수를 검토한다. 중복되는 경우의 검토 비용을 줄이기 위해 기존의 결과를 저장한다. Longest Palindrome SubString 예제) 문자 수열이 주어질 때, 대칭을 이루는 부분수열 중 최대길이를 구하라. [ b, a, a, b, c ] Palindrome이란, 정방향으로 읽어도 역방향으로 읽어도 같은 배열을 의미한다. b, a, a, b 는 → 으로 읽어도 ← 으로 읽어도 같다. 이런 성질을 가진 부분수열 중 최대길이를 구해야 한다. Palindrome은 몇가지 특징을 가진다. 1) Prlindrome 성질을 가진 가장 ..

동적계획법(Dynamic Programing)이란? 복잡하고 어려운 문제를 작은 단위로 '분할'한 후 다시 '결합'하여 최적의 답을 구하는 방법 동적계획법은 분할된 모든 경우의 수를 검토한다. 중복되는 경우의 검토 비용을 줄이기 위해 기존의 결과를 저장한다. Maximum Product SubArray 예제) 정수로 구성된 한 수열이 주어질 때, 곱이 최대가 되는 부분수열을 구하라. [ 3, -2, 1, 0, -8, 9 ] 동적계획법을 발상하기 어려운 문제다. 부분수열로 분할할 수 있는 경우의 수가 너무 많다. Top에서 Down하면서 분할하기가 쉽지 않다. 그래서 일반적으로는 브루트포스 방법을 생각하게 된다. [ 3 ], [ 3, -2 ] [ 3, -2, 1] [ 3, -2, 1, 0 ] [ 3, -2..

동적계획법(Dynamic Programing)이란? 복잡하고 어려운 문제를 작은 단위로 '분할'한 후 다시 '결합'하여 최적의 답을 구하는 방법 동적계획법은 분할된 모든 경우의 수를 검토한다. 중복되는 경우의 검토 비용을 줄이기 위해 기존의 결과를 저장한다. Maximum Sum SubArray 예제) 정수로 구성된 한 수열이 주어질 때, 합이 최대가 되는 부분수열을 구하라. [ 5, -2, 9, -15, 8 ] 동적계획법을 발상하기 어려운 문제다. 부분수열로 분할 할 수 있는 경우의 수가 너무 많다. Top에서 Down하면서 분할하기가 쉽지 않다. 그래서 일반적으로는 브루트 포스 방법을 생각하게 된다. [ 5 ] , [ 5 ,-2 ] , [ 5, -2, 9 ] , [ 5, -2, 9, -15 ] , [..

동적계획법(Dynamic Programing)이란? 복잡하고 어려운 문제를 작은 단위로 '분할'한 후 다시 '결합'하여 최적의 답을 구하는 방법 동적계획법은 분할된 모든 경우의 수를 검토한다. 중복되는 경우의 검토 비용을 줄이기 위해 기존의 결과를 저장한다. Decoding Ways A, B, C, D , ... , X, Y, Z가 1, 2, 3, 4, ... , 24, 25, 26 에 매칭될 때 , 주어진 수들로 만들 수 있는 디코딩 개수는 몇 개인가? [ 2, 3, 1, 1, 2, 4, 5 ] Top-Down 문자는 한 자리수 거나 두 자리수로 표현된다. 2는 B를 의미하고 23은 W를 의미한다. [ 2, 3, 1, 1, 2, 4, 5 ] 는 [ B , 3, 1, 1, 2, 4, 5 ] 와 [ W, ..

동적계획법(Dynamic Programing)이란? 복잡하고 어려운 문제를 작은 단위로 '분할'한 후 다시 '결합'하여 최적의 답을 구하는 방법 동적계획법은 분할된 모든 경우의 수를 검토한다. 중복되는 경우의 검토 비용을 줄이기 위해 기존의 결과를 저장한다. 최소 동전 개수 ( Min Coin Change ) 동전 2원, 3원 5원이 있다. 각 동전은 무수히 많이 존재한다. 합이 11원이 되는 최소 동전 개수를 구하라. Top-Down 11원은 3가지 경우로 분할된다. 3가지 경우의 동전 개수 중 최소를 구해야 한다. 그럼 분할을 계속해보자. 4원은 3가지 경우가 있다. 2원 + 2원 1원 + 3원 -1원 + 5원 각 가격 별 최소 동전 개수의 배열은 아래와 같다. 1원 이나 음수인 경우 -1을 삽입하여..

동적계획법(Dynamic Programing)이란? 복잡하고 어려운 문제를 작은 단위로 '분할'한 후 다시 '결합'하여 최적의 답을 구하는 방법 동적계획법은 분할된 모든 경우의 수를 검토한다. 중복되는 경우의 검토 비용을 줄이기 위해 기존의 결과를 저장한다. 최소 경로 비용 합 ( Minimum Path Sum ) 타일 안에서 이동은 오른쪽이나 아래쪽만 가능하다. 각 타일에 비용이 할당되어 있을 때, 시작부터 끝까지 가는 최소 비용을 구하라. Top-Down 목적지에 도달할 수 있는 경우의 수는 A와 B 두 가지이다. A와 B의 비용을 구해 최소값을 선택하면 된다. A는 C와 D의 최소비용이다. Top-Down 방식을 적용하면 이렇게 하나씩 구하면 된다. 중복되는 경로의 비용을 저장하여 최소비용을 검토한..

동적계획법(Dynamic Programing)이란? 복잡하고 어려운 문제를 작은 단위로 '분할'한 후 다시 '결합'하여 최적의 답을 구하는 방법 동적계획법은 분할된 모든 경우의 수를 검토한다. 중복되는 경우의 검토 비용을 줄이기 위해 기존의 결과를 저장한다. Min Cost Climbing Stairs 사람은 한번에 한 칸 혹은 두 칸의 계단을 오를 수 있다. 계단을 오르는데 필요한 비용(cost)이 있다고 가정할 때, 꼭대기까지 오를 수 있는 최소비용을 얼마인가? Top-Down 계단4(꼭대기)에 도달하려면 계단2에서 두칸 뛰거나 계단3에서 한칸 뛰어야 한다. 계단을 뛰는데 걸리는 비용을 트리로 표현해보자. 계단2에서 계단4까지는 비용이 4가 든다. 그러나 Top-Down 방식이므로 계단2까지 오는데 ..

동적계획법(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가 발생할 확률 결..