초평면(hyperplane)은 임의의 공간을 양분하는 평면이다. 특정 차원에 국한되지 않고 모든 차원에 대해 1만큼 적은 차원을 가지며 공간을 양분한다. 데이터들이 좌표 공간에 놓여있을 때 클래스에 따라 데이터를 구분하는 초평면을 어떻게 그리는 것이 가장 좋을까? 초평면과 가장 가까운 데이터를 Support vector라고 하고 둘 사이의 거리를 Margin이라고 할 때, Margin을 최대화하는 초평면이 가장 좋다고 판단한다. Margin이 클수록 일반화 오차가 감소하며 작을수록 작은 섭동에 의해 클래스 분류가 바뀔 수 있어 과적합 문제를 발생시킨다. 초평면은 오로지 Support vectors에 의해 결정되며 다른 어떠한 학습 데이터들은 영향을 주지 못한다. 데이터가 섞여 있어 데이터의 클래스를 하나..
비선형분류모형 중 k-근접 이웃 분류(k-neareast neighbor : k-NN)가 있다. 이 분류기는 어떠한 데이터가 입력되면 입력 변수를 기준으로 주변의 데이터들 간의 거리를 계산하고 가장 “가까운” k개의 데이터들이 주로 속한 클래스에 할당시키는 방식으로 분류를 진행한다. 가까움에 대해 여러 가지의 정의가 있을 수 있다. 입력 변수 값이 연속적인 경우, 유클리디안 거리, 마할라노비스 거리, 코사인 유사도, 민코프스키 거리, 맨해튼 거리 등 여러 가지 평가 척도가 존재한다. 일상 생활에서 가장 많이 쓰이는 거리의 개념은 유클리디안 거리에 해당한다. 맨해튼 거리의 경우 위치 간의 수직, 수평 거리의 합을 의미하며, 민코프스키 거리는 유클리디안, 맨해튼 거리 등을 모두 포함할 수 있는 큰 범주의 거..
의사결정나무(decision tree) 의사결정나무는 비선형분류모델로 많이 사용되는 분류기 중 하나이며 데이터에 대한 분류 이유를 설명할 수 있다는 특징을 가지고 있다. 대부분의 머신러닝 모델들이 결과에 대한 해명을 하지 못한다는 사실에서 굉장한 장점이라는 것을 느낄 수 있다. 루트에서부터 리프까지 각 지점에 있는 기준에 의해 데이터가 순차적으로 분류된다. 또한 동일한 데이터 셋에 대해 여러 개의 다른 구조의 트리 모델을 학습시킬 수 있다. 의사결정나무 모델을 학습하는 알고리즘 중 Hunt’s algorithm은 다음과 같다. 특정 노드 A에 속해 있는 데이터들이 모두 동일한 클래스 B에 속해 있다면 노드 A는 클래스 B의 리프 노드라고 한다. 노드에 아무 데이터도 없다면 노드 A는 기본 클래스(defa..
결합 확률(joint probability)는 두 사건이 동시에 발생할 확률을 의미한다. 주변 확률(marginal probability)는 결합 확률들의 합으로 표현되는 함수로 훨씬 범위가 큰 사건의 확률을 의미한다. 조건부 확률(Conditional Probability)는 어떠한 사건이 이미 일어났다고 할 때 다른 사건이 일어날 확률을 의미한다. 이미 일어난 사건을 조건, 사전 정보(prior information)이라고 한다. 전체 확률의 법칙(Theorem of Total Probability)은 표본 공간을 서로 배반인 사상으로 분할했을 때 표본 공간에서 일어나는 사건 A가 각 사상의 사건이 일어날 확률과 사상에 대한 사건 A의 조건부 확률의 곱의 총합과 같다는 법칙이다. 베이즈 정리(Baye..
분류(Classification)는 입력된 데이터의 클래스(특정한 그룹을 의미하는 이산적인 값)를 예측하는 것이다. 분류는 회귀와 같이 지도학습에 속하며 학습 데이터로 입력과 클래스 값을 함께 제공하여 클래스에 대한 입력 데이터의 함수 형태의 모델을 학습시켜야 한다. 회귀 분석과 비슷하나 예측하고자 하는 값이 연속적인 값이 아닌 이산적인 값(클래스)에 해당한다. 학습된 모델의 분류 기준을 그래프 상에 나타낸 것을 결정 경계(decision boundary)라고 한다. 결정 경계(decision boundary)는 입력 데이터를 클래스에 따라 분류했을 때 그룹 간에 생기는 경계를 의미한다. 분류 모델의 성능 평가 분류 모델의 성능을 평가할 때 여러 가지 척도를 사용한다. 그 척도에는 정확도(Accuracy..
머신러닝으로 학습된 모델 성능 평가 머신러닝 알고리즘을 통해 모델은 학습 데이터에 대한 오차를 감소시켜 나간다. 하지만 사용자가 원하는 모델은 임의의 독립변수 값에 대해 적절한 종속 변수 값을 추정하는 모델이다. 즉, 일반화 오차(generalization error)가 적은 모델은 원하는 것이다. 따라서 학습된 모델의 일반화 오차를 평가하기 위해서는 학습에 사용되지 않은 임의의 테스트 데이터를 선택해야만 한다. 과적합(overfitting)과 과소적합(underfitting) 과적합은 모델이 학습데이터 추정에 초점이 맞추어져 일반적인 데이터에 대해서는 적절한 추정을 하지 못하는 상황이며, 과소적합은 학습이 제대로 되지 않아 모델의 성능이 떨어지는 상황이다. 과소적합의 경우 학습 데이터의 양을 늘려서 충..
정부는 보이지 않는 손이 그 역할을 제대로 수행할 수 있도록 각 개인의 재산권(property right)를 보장한다. 또한 대부분의 경우 시장에 작용하는 보이지 않는 손이 공동체의 경제적 후생을 증진시키도록 작용하지만 시장 실패(market failure)의 경우에는 정부가 시장에 개입하는 것이 요구된다. 시장 실패(market failure)는 시장에서 자원이 효율적으로 분배되지 않는 상황을 의미한다. 시장은 한 사람의 행동이 제3자의 경제적 후생에 영향을 미치는 외부효과를 반영하지 못하기 때문에 전체적인 효율을 증진시키지 못할 수 있다. 또한 특정한 개인이나 기업에 의해 시장 지배력(market power)이 행사되는 경우에도 시장 전체를 고려하면 자원 분배의 효율이 감소할 수도 있다. 이때 정부가..
대개 많은 경우 어떠한 상황 속에서 선택하게 된다. 이때 현재 상태에서 이루어지는 작은 변화를 한계적 변화(marginal changes)라고 한다. 이러한 한계적 변화는 상황의 마지막에서 이루어지며 그때의 변화로 인한 편익과 비용을 고려하여 편익이 더욱 커지도록 하는 방향으로 선택이 이루어진다. 이때 편익과 비용은 현재 상황에 따라 유동적으로 평가된다. 대개 소유량, 소비량 등의 상태에 따라 편익과 비용이 결정되기도 한다. 이러한 한계적 변화는 오로지 현재 시점만을 고려한 선택이므로 전체적인 경제적 이익과 거리가 있을 수 있다.
랜선 자르기 문제는 이진 탐색을 활용한 문제입니다. 랜선 길이의 최소값과 최대값을 통해 가장 작게 자를 수 있는 길이, 크게 자를 수 있는 길이를 구할 수 있습니다. 이 범위 내의 길이로 랜선을 잘라서 문제에서 요구하는 개수 이상을 만들고면서 동시에 길이를 최대화하여야 합니다. 이 길이를 찾기 위해서 이진탐색을 활용합니다. 범위의 가운데 길이로 랜선을 잘랐을 때 나오는 개수가 원하는 개수보다 작다면 토막의 길이는 더욱 작아져야하므로 범위의 상한을 가운데보다 1만큼 작은 값으로 변경합니다. 잘랐을 때 나오는 개수가 많거나 같으면 가운데 길이 미만의 길이로 나누었을 때는 더 작은 토막길이로 더 많거나 같은 랜선 토막을 만들어낼 수 있다는 의미가 되므로 범위의 하한을 가운데 길이로 변경합니다. 가운데 길이보다..
숫자 카드 2는 이진탐색을 사용하는 문제입니다. 숫자를 정렬시킨 후 이진 탐색을 하는 문제입니다. 2021.07.19 - [알고리즘/문제풀이] - [BOJ 1920번]수 찾기 [BOJ 1920번]수 찾기 수 찾기 문제는 빠른 정렬과 이진 탐색을 활용하는 문제입니다. N이 10만이기 때문에 NlogN의 시간복잡도를 가지는 정렬 알고리즘을 사용해야하며 탐색할 숫자의 개수도 10만이기 때문에 logM의 이 ark-hive.tistory.com 이전 문제와 비슷한 방법을 사용하나 테스트 케이스의 크기가 다르기 때문에 조금은 신경을 써야 했습니다. 정렬의 경우 퀵솔트의 경우 최악의 경우 N^2이 될 수 있어서 시간초과를 내었습니다. 따라서 항상 고르게 시간을 소요하는 병합 정렬을 이용해만 합니다. 이진 탐색의 경..
리스트에서 정렬된 원소 중 특정 원소를 logn 시간 내에 찾는 알고리즘이다. 혹은 특정 원소가 리스트에 없음을 확인하는 알고리즘이다. 리스트의 중간값과 찾고자 하는 값을 비교하고 만약 찾고자 하는 값이 더 크면 리스트의 하한을 중간보다 1만큼 높은 값으로 바꾸고, 더 작으면 리스트의 상한을 중간보다 1만큼 낮은 값으로 바꾼다. 탐색하는 범위를 절반씩 줄여나가면서 결국에는 원하는 값을 리스트에서 찾거나 찾지 못하게 된다. 절반씩 범위를 줄여나가므로 lgN만큼의 시간이 소요된다.
수 찾기 문제는 빠른 정렬과 이진 탐색을 활용하는 문제입니다. N이 10만이기 때문에 NlogN의 시간복잡도를 가지는 정렬 알고리즘을 사용해야하며 탐색할 숫자의 개수도 10만이기 때문에 logM의 이진 탐색 알고리즘을 사용해야 합니다. 작성한 코드는 다음과 같습니다. #include int N,M; int number[100020]; int temp; void quicksort(int low, int high) { if (low >= high) return; int pivot =number[high]; int index = low; int temp; for (int i = low;i
마인크래프트 문제는 지형을 평탄화할 수 있는 모든 경우를 고려하여 계산하는 문제이다. 평탄화된 지형의 최소 높이는 0, 최대 높이는 지면의 블록 개수와 인벤토리에 있는 블록 개수를 면적으로 나눈 값이다. 이 두 값 사이의 값을 높이로 가지기 위해 블록을 부수거나 쌓아야 하는 데 이때 가장 시간이 적게 걸리는 높이를 찾으면 된다. 작성한 코드는 다음과 같다. #include int N, M, B; int land[520][520]; int sum = 0; int time; int min=987654321; int height; int main(void) { scanf("%d %d %d", &N, &M, &B); for (int i = 0; i < N; i++) { for (int j = 0; j < M; ..
팰린드롬수 문제는 문자열을 다루는 문제이다. 문자열을 대칭적으로 확인하여 같지 않으면 no를 출력하고, 전부 같으면 yes를 출력하도록 함수를 작성하면 된다. 작성한 코드는 다음과 같다. #include #include char temp[10]; int func() { int length = strlen(temp); if (length == 1) { if(temp[0] == '0') return -1; else { return 1; } } else { for (int i = 0;i
- Total
- Today
- Yesterday
- 이분법
- 정렬
- 큐
- 이진탐색
- 영화
- 재귀함수
- 건이의 특제 떡국 끓이기
- Verilog
- C언어
- BOJ
- 알고리즘
- gem5
- 메이플스토리
- BFS
- C++
- 백준
- Push
- 구조체
- 영어 어휘
- 너비우선탐색
- 구현
- 백트래킹
- 스택
- recursive
- backtracking
- 애니메이션
- 베릴로그
- 취미
- 완전탐색
- Git
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 |