회귀분석 독립 변수와 종속 변수 사이의 관계를 선형으로 가정하고 함수의 형태를 학습하는 알고리즘입니다. 입력되는 독립 변수에는 양적 입력, 질적 입력이 있으며 그 선형성 확립을 위한 그것들의 변환까지 포함됩니다. 양적 입력의 경우 연속적인 값으로 값끼리 연산이 가능하며 질적 입력인 경우 서로 연산이 불가능하기 때문에 one hot coding(하나의 항목만 1(참)으로 표시하는 방식)을 통해 값을 표현합니다. 단순회귀분석 단순회귀분석은 회귀분석 중 1개의 독립변수와 종속변수 사이의 관계를 학습하는 기법입니다. 수식으로 y=bx+a+e로 표현할 수 있으며, a는 y절편, b는 회귀계수, e는 오차를 의미합니다. 오차 e는 독립변수 xi 값 각각에 대해 독립적으로 존재하는 확률변수이며 N(0, σ^2)의 정..
최근 알파고 사건을 발단으로 인공지능에 대한 관심이 높아지고 있다. 인공지능은 무엇이고, 이에 수반하는 머신러닝은 도대체 무엇인가? 인공지능(Artificial Intelligence)는 strong AI와 weak AI로 구분된다. strong AI(Artifical General Inteligence)는 사람과 같이 스스로 생각하고, 여러 분야의 문제를 훌륭하게 해결할 수 있는 AI이다. weak AI(Narrow AI)는 특정 분야의 문제에 대해서만 뛰어난 해결 능력을 보이는 AI이다. 머신러닝은 약한 인공지능(weak AI)를 구현하는 알고리즘의 일종이다. 컴퓨터 프로그램이 경험을 통해 자동으로 개선되도록 하는 알고리즘이다. 구체적으로 말해서, 어떠한 측정 기준을 가지는 분야의 작업이 어떠한 경험..
조합 0의 개수 문제는 소인수 분해시 2와 5의 개수를 활용하는 문제입니다. 팩토리얼 값을 소인수 분해했을 때 5의 개수를 구하는 방법은 팩토리얼에서 처음의 항을 5로 나눈 수 + 25로 나눈 수 + 125로 나눈 수 + .... 식과 같다. 이런 방식으로 2와 5의 개수를 찾고 그 중 가장 작은 값이 0의 개수가 된다. 작성한 코드는 다음과 같다. #include long long int n, m; long long int five, two; long long int d; int main(void) { scanf("%lld %lld", &n, &m); d = 5; while (1) { if ((n< d)) break; five += (n / d); d *= 5; } d = 2; while (1) { i..
팩토리얼 0의 개수 문제는 팩토리얼 값을 소인수분해를 하였을 때 2와 5의 지수 중 최소값을 활용하는 문제입니다. 0의 개수는 2와 5의 지수 중 최소의 개수와 동일하다는 사실을 이용하면 됩니다. 작성한 코드는 다음과 같습니다. #include int N; int result = 1; int cnt = 0; int two, five; int temp; int main(void) { scanf("%d", &N); for (int i = 1; i five) printf("%d\n", five); else printf("\n", two); } } 문제의 지문은 다음의 링크에서 확인할 수 있습니다. https://www.acmicpc.net/problem/1676
패션왕 신해빈 문제는 경우의 수를 이용한 문제입니다. (같은 종류의 개수 + 1) 항들의 곱에 -1을 한 값이 옷을 입을 수 있는 경우의 수가 됩니다. 작성한 코드는 다음과 같습니다. #include #include int T; int n; char temp[100]; char clothes[300][100]; char cnt[300]; int limit; int result = 1; int k; int main(void) { scanf("%d", &T); for (int i = 0; i < T; i++) { scanf("%d", &n); result = 1; limit = 0; for (int j = 0; j < 2*n; j++) { scanf("%s", temp); if (j % 2 == 1) { f..
다리 놓기 문제는 조합을 사용하는 문제입니다. mCn의 공식을 활용하여 문제를 해결할 수 있습니다. 작성한 코드는 다음과 같습니다. #include int T; int N, M; int result = 1; int main(void) { scanf("%d", &T); for (int i = 0; i < T; i++) { result = 1; scanf("%d %d", &N, &M); for (int j = 0; j < N; j++) { result = result * (M--) / (j + 1); } printf("%d\n", result); } } 문제의 지문은 다음의 링크에서 확인할 수 있습니다. https://www.acmicpc.net/problem/1010
이항 계수 2문제는 이항 계수 점화식뿐만 아니라 다이나믹 프로그래밍 기법을 활용하는 문제입니다. (n, k) = (n-1, k-1) + (n-1, k)라는 사실과 배열을 활용하여 (n, k)를 미리 계산한 후 출력함으로써 풀 수 있습니다. 다이나믹 프로그래밍을 할 때 기교를 발휘하면 배열의 크기는 1차원 배열 [1001]까지 줄일 수 있습니다. 작성한 코드에서는 2차원 배열 [2][1001]로 작성하였습니다. #include //NCK int N, K; int result[2][1001]; int i=1; int main(void) { scanf("%d %d", &N, &K); result[0][0] = 1; result[1][0] = 1; while (1) { for (int j = 1; j < 100..
링 문제는 원주의 비율과 최대공약수를 활용하는 문제입니다. 원주가 반지름에 비례한다는 사실을 이용하여 회전수를 구하고 최대공약수를 이용하여 기약분수 형태로 출력함으로써 문제를 해결할 수 있습니다. 작성한 코드는 다음과 같습니다. #include //기약분수는 최대공약수로 생성 int N; int temp, temp1, temp2; int gcd(int a, int b) { int temp; if (a < b) { temp = b; b = a; a = temp; } while (a % b != 0) { temp = b; b = a % b; a = temp; } return b; } int main(void) { scanf("%d", &N); scanf("%d", &temp1); for (int i = 0;..
이항 계수 1 문제는 조합의 식을 이용하는 문제이다. nCk = n!/(n-k)!/k!이라는 사실을 이용하여 for문으로 값을 계산하면 된다. 작성한 코드는 다음과 같다. #include //NCK int N, K; int result = 1; int main(void) { scanf("%d %d", &N, &K); for (int i = 0; i < K; i++) { result = result * N / (i + 1); N--; } printf("%d\n", result); } 문제의 지문은 다음의 링크에서 확인할 수 있다. https://www.acmicpc.net/problem/11050
검문 문제는 최대공약수를 활용하는 문제이다. 두 수를 어떤 수로 나누었을 때 나머지를 같게 하는 수는 두 수의 차의 모든 약수이다. 또한 두 수의 차의 모든 약수는 두수를 나머지가 같게 나눈다. 위의 명제는 귀류법과 a=bq+r의 식을 활용하여 증명할 수 있다. 위의 두 문장은 두 수를 나누었을 때 나머지를 같게 만드는 어떤 수가 두 수의 차의 약수와 동일하다는 것을 알려준다. M개의 수를 나머지가 같게 만드는 어떤 수를 찾아야하므로 M개의 수를 정렬하고 순차적으로 두 수의 차의 최대공약수를 계산하여야 한다. 최종적으로 M개의 수를 나누었을 때 같은 나머지를 같게 하는 어떤 수들을 약수로 같는 최대공약수가 얻어진다. 이 최대공약수의 모든 약수를 출력함으로써 문제는 해결된다. 주의할 점은 마지막에 구한 최..
최소공배수 문제는 최대공약수와 최소공약수의 관계를 활용하여 해결할 수 있다. 두 수를 최대공약수로 나누었을 때의 몫들과 최대공약수를 곱하면 최소공배수를 구할 수 있다는 특성을 이용하여 문제를 해결합니다. 최대공약수는 유클리드 호제법을 이용하여 O(lgn)으로 구할 수 있습니다. 유클리드 호제법에 대한 내용을 다음과 같습니다. 2021.07.10 - [알고리즘/이론] - [알고리즘/이론][정수론] 유클리드 호제법 [알고리즘/이론][정수론] 유클리드 호제법 두 양의 정수 a, b에 대해서 a를 b로 나눈 나머지로 다시 b를 나누는 과정을 반복했을 때 마지막에 나머지가 0일 때 나누는 수가 a, b의 최대 공약수가 된다는 정리이다. 증명 a와 b를 동시에 나누는 ark-hive.tistory.com 작성한 코..
두 양의 정수 a, b에 대해서 a를 b로 나눈 나머지로 다시 b를 나누는 과정을 반복했을 때 마지막에 나머지가 0일 때 나누는 수가 a, b의 최대 공약수가 된다는 정리이다. 증명 a와 b를 동시에 나누는 약수는 b로 a를 나누었을 때 나오는 나머지와 b를 동시에 나눈다. a는 b의 배수와 나머지의 합으로 표현되는 데 b는 공통인 약수로 나누어지기 때문에 나머지 또한 공통인 약수로 나누어져야만 a가 나누어질 수 있다. 따라서 공통인 약수는 b와 나머지 사이에서도 공통이 된다. 또한 최대 공약수 또한 같아진다. 만약 최대 공약수가 다르다고 가정하면 나머지와 b사이의 최대공약수는 a와 b를 동시에 나눌 수 있기 때문에 모순이 생기게 된다. 이러한 최대공약수가 공통인 특성을 이용하여 반복적으로 수식을 계산함..
최대공약수와 최소공배수 문제는 최대 공약수와 최소공배수의 특성을 이용한 문제입니다. 두 수에 대한 기본 정의를 활용하여 문제를 해결할 수 있습니다. for문을 사용하여 모든 수에 대해 특성을 만족하는지 나누어서 확인하면 됩니다. 최대 공약수는 1부터 작은 수까지, 최대 공배수는 큰 수보다 크다는 점을 이용하면 for문 반복 횟수를 줄일 수 있습니다. 작성한 코드는 다음과 같습니다. #include int A, B; int GCD; int temp; int main(void) { scanf("%d %d", &A, &B); if (A > B) { temp = A; A = B; B = temp; } for (int i = 1; i
약수 문제는 약수의 성질을 이용하는 문제입니다. 어떤 수의 모든 약수가 주어졌을 때 가장 작은 약수와 가장 큰 약수를 곱하면 어떤 수가 된다는 성질을 이용하면 됩니다. 작성한 코드는 다음과 같습니다. #include int N; int min = 987654321; int max = 0; int temp; int main(void) { scanf("%d", &N); for (int i = 0; i max) max = temp; } printf("%d\n", min * max); } 문제의 지문은 다음의 링크에서 확인할 수 있습니다. https://www.acmicpc.net/pr..
배수와 약수 문제는 정수의 특성을 활용하는 문제이다. 서로 같지 않은 자연수는 약수 관계, 배수 관계, 아무것도 아닌 관계 중 1가지를 가지게 된다. 이 점을 유의하여 나머지를 기준으로 분류하여 요구하는 문장을 출력하면 된다. 작성한 코드는 다음과 같다. #include int num1, num2; int main(void) { while (1) { scanf("%d %d", &num1, &num2); if (num1 == 0 && num2 == 0) break; else { if (num2 % num1 == 0) { printf("factor\n"); } else if (num1 % num2 == 0) { printf("multiple\n"); } else { printf("neither\n"); } ..
AC문제는 큐를 활용한 문제이다. 큐의 pop을 활용하는 문제로 뒤집기 함수로가 추가된 문제이다. 뒤집기의 경우 pop할 때 경우에 따라 head와 tail 중 1개를 선택하여 1만큼 이동시키면 된다. 주의할 점은 테스트 케이스의 입력이 큰 편이라 수행시간에 여유가 없다는 점이다. 가능하면 O(n+p)의 시간에 수행하여야 한다. 문제를 풀면서 놓쳤던 부분은 다음과 같다. 먼저 모든 처리를 하고 출력을 할 때 출력형식에 맞추어 출력하는 것에 모든 것의 성패가 달렸다는 점을 느낄 수 있었다. 다 풀었다고 느꼈을 때 자만하지 말고 끝까지 주의를 기울여 풀어야 한다는 점이다. 입력에서도 입력 버퍼에 무엇이 있는지 주의를 기울여야 한다는 점이다. ps에서 끝까지 방심하지 말라는 교훈을 얻은 것 같다. 작성한 코드..
회전하는 큐는 데크를 사용하여 푸는 문제입니다. front에서만 pop이 될 수 있으므로 뽑아낼 원소의 위치와 front사이의 가능한 두 개의 거리를 비교하여 거리가 작은 쪽으로 로테이션합니다. 뽑아낼 원소를 모두 뽑아내기 위해 로테이션하는 총 횟수를 계산하여 출력함으로써 문제를 해결할 수 있습니다. 작성한 코드는 다음과 같습니다. #include #define size 100 int N, M; int extracted[100]; int index_extracted; int total_op; int deque[size]; int front = 0, back = 1; int temp_front, temp_back; void rotate_clock() { deque[back]=deque[(front+1+si..
덱은 양방향에서 입력과 출력이 모두 가능한 자료구조입니다. 양방향의 입출력으로 인해 환형의 형태를 가진다는 점을 주의하며 이전의 큐 문제와 비슷하게 코드를 작성를 하여야 합니다. 2021.07.08 - [알고리즘/문제풀이] - [BOJ 18528번]큐 2 [BOJ 18528번]큐 2 큐 2 문제는 자료구조 큐를 활용하여 해결할 수 있는 문제이다. 자료구조 큐에 대한 학습을 하였다면 어려움없이 무난하게 풀 수 있는 문제이다. 큐에 대한 내용은 다음 링크에 확인할 수 있다. 2 ark-hive.tistory.com 작성한 코드는 다음과 같습니다. #include #define size1 20020 int N; int temp; int x; int deque[size1]; int front; int back=..
프린터 큐는 큐를 활용해서 푸는 문제이다. 다만 단순히 큐만을 사용하는 문제는 아니었다. 큐에 있는 원소의 우선순위 중 가장 높은 수를 알아야 하는 데 이때 구글링을 해보면 우선순위 큐를 사용하는 유저들이 많았다. 아직 우선순위 큐에 대해 다루지 않았기 때문에 이번 풀이에서는 계수를 이용해서 문제를 풀었다. 해당 우선순위를 가지는 값의 개수를 저장하는 배열을 선언하고, 이 배열을 조사함으로써 현재 큐에서 우선순위가 가장 큰 경우를 찾고 그 값에 따라 큐에서 pop을 한 값을 다시 push할지 하지 않을 지 결정하는 식으로 해결하였다. 관찰한 값을 표시하기 위해 flag 변수가 필요했고, 구조체를 활용하여 flag와 우선순위 값을 묶고, 구조체를 원소로 하는 배열을 선언하였다. 다른 풀이에서는 구조체가 아..
요세푸스 문제 0은 큐를 활용하여 풀 수 있는 문제이다. 사람들이 큐에서 K-1번 쉬프트 로테이션을 한 후 pop을 하여 사람의 번호를 추출함으로써 해결할 수 있다. 작성한 코드는 다음과 같다. #include #define size 2000 //http://ark-hive.tistory.com/ //사람들이 큐에서 쉬프트로테이션을 하면 어떻게 될까? int N, K; int queue[size]; int head, tail; int pop() { head += 1; head %= size; return queue[(head +size - 1)%size]; } void push(int x) { queue[tail] = x; tail += 1; tail %= size; } int main(void) { s..
- Total
- Today
- Yesterday
- 이진탐색
- 완전탐색
- 메이플스토리
- 구현
- 애니메이션
- 너비우선탐색
- Git
- C++
- Verilog
- 영화
- recursive
- 베릴로그
- 영어 어휘
- 큐
- 백준
- 이분법
- 재귀함수
- 건이의 특제 떡국 끓이기
- 구조체
- 스택
- BOJ
- 취미
- 정렬
- BFS
- C언어
- Push
- gem5
- backtracking
- 알고리즘
- 백트래킹
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |