동적계획법 (Dynamic Programming) 처음에 나온 해답을 통해서 그다음 문제의 해답을 구한다. 간단히 말해 '점화식'을 이용하여 문제를 풀어나감 메모이제이션을 하는 것 => 리스트에 저장 메모이제이션 X => 그저 재귀함수 예제 문제를 풀면서 감을 익혀나가는 것이 가장 중요. 예제문제 1. 네트워크 선 자르기 - 1m 선을 자를 때 경우의 수: 1가지 - 2m 선을 자를 때 경우의 수: 2가지 1 + 1 2 - 3m 선을 자를 때 경우의 수: 2 + 1 = 3가지 1) 마지막 선의 길이를 1m로 한다고 하자, 남은 선의 길이는 2m이다. 2m 선을 자르는 경우의 수는 2가지 2) 마지막 선의 길이를 2m로 한다고 하자, 남은 선의 길이는 1m이다. 1m 선을 자르는 경우의 수는 1가지 - 4..

참고 서적 도서명: Data Science from Scratch (밑바닥부터 시작하는 데이터 과학) 저자 : Joel Grus 출판 : 프로그래밍 인사이트 Ch 12. Naive Bayse Naive Bayes •특성들 사이의 독립을 가정하는 베이즈 정리를 적용한 확률 분류기의 일종 •즉 Naive(순진하게) likelihood(가능도)를 곱해 계산해 나간다! Gaussian Naive Bayes 표본 평균과 표본 분산을 가진 정규분포 하에서 베이즈 정리를 사용하는 알고리즘 Multinomial Naive Bayes 설명 변수가 범주형 변수일 때 다항 분포 데이터에서 베이즈 정리를 사용하는 알고리즘 Bernoulli naive Bayes 설명 변수가 범주형 변수일 때, 범주가 2개밖에 없는 경우 베이즈..

문제 제목: 회의실 배정 (그리디) 문제 KEY POINT 회의실 배정이 최대가 되도록 구하면 되는 문제이다. 따라서 주어진 데이터에서 어떤 시간을 위주로 볼 것인가? 에대한 문제이다. 이 문제는 시작 시간이 중요한게 아니다. 회의가 끝나는 시간을 위주로 정렬하여, 빨리 끝나는 시간을 기준으로 봐야한다. 1. 입력 창 구현 n = int(input()) meet = [] for i in range(n): m1, m2 = map(int,input().split()) meet.append([m1,m2]) 2. lambda 함수를 이용하여 sorted 함수의 키 값 설정 list = sorted(list, key lambda x: (x[1],x[0])) 는 즉 x[1]의 값을 기준으로 오름차순 정렬을 하겠다는..

보호되어 있는 글입니다.

나이브 베이즈 분류 예시) 테니스를 좋아하는 한 사람이 있다고 하자. 만약, 이 사람이 1. 날씨가 좋고 2. 습도가 낮은 날에 테니스를 칠 확률은 얼마나 되는가? 주어진 데이터에 따라 경우가 다르겠지만, "1. 이 사람이 테니스를 많이 칠 수록, 2. 테니스를 쳤을 때, 해당 날씨가 좋고 습도가 낮은 경우가 많을 때"일수록 이 사람이 날씨가 좋고 습도가 낮은 날에 테니스를 칠 확률이 높아진다. 조건부 확률 이를 수학적 개념을 통해 알아보자. 먼저, 조건부 확률에 대해서 알 필요가 있다. 이해하기 쉽도록 "B가 주어졌을 때 사건 A의 조건부 확률"은 아래와 같다. 조건부 확률 이는 B사건 중에서 A사건이 동시에 발생한 경우를 나타낸다. 즉, 위의 예시에서 좋은 날씨와 낮은 습도가 고정되어 있을 때, 테니..

Mahalnobis Distance 노란색: 공분산 행렬 변수들간에 모두 독립적이고 Variance(분산)가 1로 정규화된다면 그 때 공분산 행렬은 항등원 행렬이 되며 이 때 마할라노비스 거리는 유클리디안 거리와 같아집니다. 즉, 마할라노비스거리는 변수들간 독립적일 때는 유클리디안 거리공식으로 바뀝니다. * 주의할 점: 마할라노비스 거리를 구할 때, KNN을 이용한 알고리즘을 구현하는 경우에는 예측할 데이터셋을 포함하여 공분산을 구하고, 해당되는 변수간의 거리를 구해야합니다... 예측할 데이터셋을 포함하지않으면, 그 전에 분포하는 데이터들끼리의 분포만을 고려하게 되어 제대로된 마할라노비스 거리구현이 어렵습니다. 파이썬으로 변수간의 공분산을 구하는 방법 중 두가지를 소개해드리겠습니다. 1. 넘파이를 이용하..

분산은 평균으로부터 얼마나 떨어져 있는 지를 표현한 것인데, 평균에서부터 떨어진 거리가 평균적으로 표현된 것입니다. 공분산이라는 것은 두 개의 데이터가 각각의 평균으로부터 얼마나 떨어져 있는가를 보는데 있어 두 변수가 얼마나 함께 변하는지를 확인한 것입니다. 데이터의 모든 특성의 범위를 같게 만들어주는 방법 교차검증을 위해 Train-Test로 분리하였을 경우 전체 데이터가 아닌 훈련 데이터에 대해서만 fit()을 적용해야한다. 1. StandardScaler - 평균 = 0 / 표준편차 = 1 - 표준화 Standardization 스크래치 코드 def standardize(x): """Standardize the original data set.""" return (x - x.mean(axis=0))..

*문제 출처는 프로그래머스에 있습니다. 문제 제목: 더 맵게 (2단계) 문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/42626 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다. 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코..

문제 제목: 최대힙 함수 살펴보기 heapq.heappush(heap, item): item을 heap에 추가 heapq.heappop(heap): heap에서 가장 작은 원소를 pop후 return. 비어있는 경우에는 IndexError가 호출된다. heapq.heapify(x): 리스트 x를 즉각적으로 heap으로 변환시킨다. ** 힙 함수는 모두 최소힙을 기반으로 작성됨. 최대힙을 구현하려면 음의 부호를 붙여서 push를 해준다. (pop할 때는 원래 값이 반환되어야하니 한번 더 음의 부호를 넣어준다.) 모범답안 import heapq as hq a = [] while True: n = int(input()) if n == -1: break if n == 0: # 숫자 0이 입력되면 최소힙에서 최솟..

문제 제목: 최소힙 - 힙 자료구조 함수 살펴보기 heapq.heappush(heap, item): item을 heap에 추가 heapq.heappop(heap): heap에서 가장 작은 원소를 pop후 return. 비어있는 경우에는 IndexError가 호출된다. heapq.heapify(x): 리스트 x를 즉각적으로 heap으로 변환시킨다. ** 힙 함수는 모두 최소힙을 기반으로 작성됨. 최대힙을 구현하려면 음의 부호를 붙여서 push를 해준다. (pop할 때는 원래 값이 반환되어야하니 한번 더 음의 부호를 넣어준다.) 모범답안 import heapq as hq a = [] while True: n = int(input()) if n == -1 break if n == 0: # 숫자 0이 입력되면 ..

자료구조는 우선순위(priority_queue)를 구현하기 위해 사용하는 자료구조 중 하나다. 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다는 점이 특징인데, 표로 나타내면 다음과 같다. 자료구조추출되는 데이터 스택(stack) 가장 나중에 삽입된 데이터 큐(queue) 가장 먼저 삽입된 데이터 우선순위 큐(priority_queue) 가장 우선순위가 높은 데이터 우선순위 큐를 구현할 때는 내부적으로 최소 힙(min_heap) 혹은 최대 힙(max_heap)을 이용한다. 최소 힙을 이용할때는 값이 가장 낮은 데이터가 먼저 삭제되며, 최대 힙은 값이 큰 데이터가 가장 먼저 삭제됨을 알아두자. 파이썬에서 우선순위 큐 라이브러리를 사용할때는 default값이 최소 최소 힙(min_heap)으..

참고 서적 도서명: Data Science from Scratch (밑바닥부터 시작하는 데이터 과학) 저자 : Joel Grus 출판 : 프로그래밍 인사이트 Ch 12. K- Nearest Neighbor (KNN) KNN은 모델을 만드는 것이 아님. 모델의 형태는 정해져있지 않고, 방법론 및 알고리즘이라고 일컫는다. -김성범 교수님(고려대학교) 모델은 특정 유형의 패턴을 인식하도록 학습된 파일임!!! KNN 분류 "내 이웃의 다수의 패턴으로 따라간다." 관측치를 정하고, 그 관측치에서 가까운 거리에 있는 이웃데이터를 탐색한다. 가까운 순서대로 "거리"를 구하고, 새로운 예측 데이터에대해 수행한다. KNN 알고리즘의 구분 및 특징 Instance-based Learning 각각의 관측치만을 이용하여 새로..