기본 콘텐츠로 건너뛰기

knapsack problem (배낭문제)

Knapsack Problem Definition in Wikipedia 배낭 문제 ( Knapsack Problem   냅색 프라블럼 [ * ] )는  조합 최적화 의 유명한 문제이다. 간단하게 말하면, 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. 이 배낭문제는 짐을 쪼갤 수 있는 경우(무게가  소수 일 수 있는 경우)와 짐을 쪼갤 수 없는 경우(이 경우 짐의 무게는 0 이상의 정수만 가능) 두 가지로 나눌 수 있는데, 짐을 쪼갤 수 있는 경우의 배낭문제를  분할가능 배낭문제 ( Fractional Knapsack Problem ), 짐을 쪼갤 수 없는 경우의 배낭문제를  0-1 배낭문제 (0-1  Knapsack Problem )라 부른다. 이 문제는 쪼갤 수 있는 경우에는  그리디 알고리즘 으로  다항 시간 에, 쪼갤 수 없는 경우에는  동적계획법 (Dynamic Programming)등으로  의사 다항 시간 에 풀 수 있다. 단, 쪼갤 수 없는 경우는  NP-완전 이기 때문에 알려진 다항 시간 알고리즘은 없고,  FPTAS 만 존재한다. 배낭 문제에 대한 FPTAS는  오스카 이바라 와  김철언 이  1975년 에 개발하였다. ZeroDivision Error https://airbrake.io/blog/python-exception-handling/zerodivisionerror-2 Greedy metrics
최근 글

Principal Components Analysis - Georgia Tech - Machine Learning

[machine learning] k means algorithm

#!/usr/bin/python """ skeleton code for k-means clustering mini-project """ import pickle import numpy import matplotlib.pyplot as plt import sys sys.path.append("../tools/") from feature_format import featureFormat, targetFeatureSplit def Draw(pred, features, poi, mark_poi=False, name="image.png", f1_name="feature 1", f2_name="feature 2"): """ some plotting code designed to help you visualize your clusters """ ### plot each cluster with a different color--add more colors for ### drawing more than 4 clusters colors = ["b", "c", "k", "m", "g"] for ii, pp in enumerate(pred): plt.scatter(features[ii][0], features[ii][1], color = colors[pred[ii]]) ### if you like, place red stars over points that are POIs (just for funsies) if mark_poi: for ii, pp in enumerate(pred): ...

Udacity - Retrieve Accuracy using Decision Tree

sklearn decision tree split을 2, 50로 설정하고 accuracy를 비교한다. import  sys from  class_vis  import  prettyPicture from  prep_terrain_data  import  makeTerrainData   import  matplotlib.pyplot as plt import  numpy as np import  pylab as pl   features_train, labels_train, features_test, labels_test  =  makeTerrainData()   ########################## DECISION TREE ################################# ### your code goes here--now create 2 decision tree classifiers, ### one with min_samples_split=2 and one with min_samples_split=50 ### compute the accuracies on the testing data and store ### the accuracy numbers to acc_min_samples_split_2 and ### acc_min_samples_split_50,...

[Google Tag Manager] button click event tracking

Google Tag Manager를 이용하여 버튼 클릭 이벤트 트래킹을 하려면? (Google Tag Manager 컨테이너 Script가 정상적으로 적용되었다는 가정하에 진행) 1. Event Tracking 시나리오 상품페이지에 'SNS 공유하기' 버튼을 얼마나 클릭하는지 효율 분석이 필요하다. ex) 카카오톡 공유하기, Facebook 좋아요, Twitter 멘션, SMS 2. 데이터 수집 1) GA event tracking script 방식 a. 공유하기 클릭 이벤트 스크립트 구성 Event Category : sharesns Event Action : kakao 또는 facebook 또는 twitter Event Label : 공유페이지명(필수값 아님) 시나리오 GA Event Tracking Code Sample kakaotalk button click ga('send', 'event', 'sharesns', 'kakao', '공유페이지명'); facebook button click ga('send', 'event', 'sharesns', 'facebook', '공유페이지명'); twitter button click ga('send', 'event', 'sharesns', 'twitter', '공유페이지명'); 위 코드를 모든 공유하기 버튼이 있는 페이지에 적용한다. 2) Google Tag Manager 컨테이너 방식 Google Tag Manager(이하 GTM)은 Container Script를 공통 소스 영역(ex. 푸터)에 적용하고 컨테이너에 필요한 Script를 Tag란 형식으로 적용하는...

[Hadoop] Snappy 설치

What is Snappy? - 구글에서 자체 개발한 압축 라이브러리 - 라이브러리 주소 http://code.google.com/p/snappy - 2015.01.05 현재 최신 버전은 snappy-1.1.1(?) 설치 과정 1. tar 파일 다운로드 https://code.google.com/p/snappy/downloads/list?can=1&q= 2. tar 파일 압축 풀기 3. root 계정으로 snappy 설치 1) 개인적으로 설치한 fedora에 gcc컴파일러, g++ 컴파일러가 없어 함께 설치하였다. g++      yum install gcc-c++ gcc      yum -y install gcc 2) snappy 폴더 이동 3) ./configure --enable-shared 4) make 5) sudo make install 4. snappy native library를 하둡에 복사한다. 1) cp /usr/local/bin/libsnappy.* $하둡홈/lib/native/Linux-amd64-64 2) cp /usr/local/bin/libsnappy*.* $하둡홈/lib/native/Linux-i386-32 가장 중요한 사실!!!! - mac에서는 snappy 설치시 .so파일이 아닌 .dylib파일이 생성된다. - native library는 Cygwin, Mac OS X 환경에서 동작하지 않는다.( Native Libaries 참조 ) Sample Source @Override public int run(String[] args) throws Exception { JobConf conf = new JobConf(SequenceFileCreator.class); conf.setJobName("SequenceFileCreator"); conf.setMapperClass(Dis...