인공지능 (13) 썸네일형 리스트형 P VS NP, 다항시간, 지수시간, 결정적 알고리즘, 비결정적 알고리즘 이번 글에서는 P와 NP에 대해 다뤄 보도록 하겠습니다. 솔직히 저도 한글로 되어있던지, 영어로 되어있는 글이든 읽으면서 도대체 무슨 말인가라고 할 정도로 이해가 되지 않더군요. 자꾸 반복해 읽어도 조금 이해가 되는 듯 말 듯 여전히 어려운 개념이지만 같이 공부해 봅시다. P vs NP 만약 다항식 시간(polynomial time) 내 결정적 알고리즘(a deterministic algorithm)으로 해결할 수 있는 컴퓨터적인 문제(Computional problem) x 가 있다면 x 는 P의 클래스 안에 있다. 만약 다항식 시간(polynomial time) 내 비결정적 알고리즘(a non-deterministic algorithm)으로 해결할 수 있는 컴퓨터적인 문제(Computional pro.. 최적화 0-1 knapsack problem (배낭 채우기) 이번 글에서는 동적 알고리즘을 통해 0-1 knapsack problem (배낭 채우기)를 다뤄보도록 하겠습니다. 배낭 채우기 문제는 크게 탐욕 알고리즘을 이용한 fractional knapsack problem과 동적 알고리즘을 이용한 0-1 knapsack problem 이 있습니다. 주어진 배낭(배낭이 담을수 있는 한계 무게가 존재)과 여러 가지 물건(무게와 물건의 가치가 있는)들이 있습니다. 배낭에 최대한 많은 물건을 담으면서 최대한의 가치를 도출해 내는 문제입니다. 만약 여러분이 시계방을 털었을때 가져온 가방 안에 시계를 10개까지 담을 수 있다고 했을 때 스와치나 티쏘가 아닌 롤렉스나 IWC 같은 고가 혹은 그 이상의 시계를 털어야 한다는 개념(?)인 것입니다. 이것을 배운 도독이라면 제일 비.. 최적화 - 동적 알고리즘(Dynamic programming) 이번에는 동적 알고리즘과 이것을 통해 0-1 knapsack problem (배낭 채우기)를 다루려고 합니다. 우선적으로 동적 알고리즘에 대해 알아보자면 사전적 의미로서 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법이라고 되어 있습니다. 그리고 그 대표적인 예로 재귀 함수 형태의 피보나치 수열이 떠오를 텐데요. 예를 들어 f(1)을 넣게 되면 1, f(2)를 넣게 되면 f(1) + f(0) = 2, f(3) = f(1) + f(2) = 3, f(4) = f(3) + f(2) =5...... 이렇게 됩니다. 하지만 이 함수를 메모리 관리적인 차원에서 본다면 매우 비효율적이라고 할 수 있습니다. f(7)을 컴퓨터에서 컴파일했을때 f(7)을 구하기 위해서 f(7) = f(6) + f(5) 를 호출하.. 최적화 - 탐욕 알고리즘, activity selection problem 이전 글에서 최적화에 대한 개념에 대해 알아봤습니다. 이번 글에서는 대표적인 최적화 문제 중 하나인 An activity selection problem과 이를 해결하기 위한 Greedy-Algorithm 또는 탐욕 알고리즘에 대해 다뤄보도록 하겠습니다. An activity selection problem (활동 선택 문제) 활동 선택 문제는 쉽게 말하면 한 강의실에서 여러 개의 수업을 하려고 할 때 겹치지 않고 한 번에 가장 많은 수업들을 고르는 알고리즘입니다. A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 시작시간 1 3 0 5 3 5 6 8 8 2 12 끝시간 4 4.5 6 7 9 9 10 11 12 14 16 위의 스케줄들을 가지고 가장 많은 개수의 일정을 만들어라는 문제가 주어.. 최적화 Optimisation 글을 올리기 앞서 저는 인공지능을 대해 뛰어난 지식을 갖추진 못했지만 제가 학교 다닐 때 배웠던 인공지능에 대해 조금 더 제대로 알고 싶은 마음에 제가 공부한 것을 같이 공유하고 싶어 블로그를 개설했습니다. 단순히 사전적 내용을 덧붙이기보다는 제가 이해한 내용을 알기 쉽게 표현하려 노력하겠습니다. 오류나 부족한 부분들이 존재할 수 있으니 미리 양해 부탁드리고 혹시 제가 잘못 알고 있는 부분이 있다면 겸허히 받아들여 더 발전할 수 있도록 노력하겠습니다. 일단 최적화의 사전적 의미란 주어진 범위 안에서 최댓값 또는 최솟값을 찾아 자원 또는 비용의 효율성을 추구하는 것입니다. 이것이 인공지능에서는 어떤 의미로 씌는지 알아보도록 하겠습니다. 수학 문제를 풀게 될 때 우리는 단 하나의 정답을 찾아야 합니다. 수많.. 이전 1 2 다음
