이번 포스팅에서는 이산수학의 한 개념으로써 조합에서 중복을 확인하는 방법이다. 알고리즘에서는 완전탐색의 경우에서 시간복잡도를 줄이는 기법으로 많이 활용된다.  예시문제: 세 사람의 심리적 거리,

https://kau-algorithm.tistory.com/27 간단한 알고리즘 - 정수론 이 글은 학회 회원 랑이집사님의 허락을 받아 에브리타임 게시글을 그대로 가져왔습니다. 코딩테스트에서 나오는 비주류 유형이 몇가지 있는데, 그중 하나인 정수론에 대해 적어보려고 합니다. kau-algorithm.tistory.com 심화 정수론!!! 기본 안내서 pdf 및 블로그 정리 모음 https://rkm0959.tistory.com/category/PS/PS%20%EC%A0%95%EC%88%98%EB%A1%A0%20%EA%B0%80%EC%9D%B4%EB%93%9C 'PS/PS 정수론 가이드' 카테고리의 글 목록 rkm0959.tistory.com 증명을 정리해놓은 심화 과정들!! https://site.th..

어떤 수의 자릿수를 구하는 알고리즘은 크게 세 가지로 생각할 수 있다. 1. 나머지 연산자를 이용하기 아이디어 중학교 수학시간에 자릿수에 대해서 배웠다. 자연수 k = 소수(0.xxx) x 10ⁿ으로 나타낼 때 k는 n자리 자연수라고 표현한다. 예를 들어 1234 = 0.1234 x 10⁴ 이므로 1234는 네 자리 자연수이다. 따라서 10으로 나눈 몫이 0이 될때까지 계속 나누면 나눈 횟수가 자리수가 된다. 구현 #include using namespace std; int digit(int n){ int ret = 0; while(n!= 0){ n /= 10; ret++; } return ret; } int main() { int num; cin >> num; cout > n; int digit = f..

숫자 데이터를 처리하다 보면 각각의 자리를 직접 분해하여 가져와야 하는 경우가 생긴다. 자릿수를 구하는 알고리즘은 간단한데 자릿수를 분해하는 알고리즘은 조금 까다롭다. 1. 자릿수 분해란? 자연수의 자리를 하나씩 분해하는 것이다. 예를 들어 145를 자릿수 분해하면 일의 자리:1 십의자리: 4 백의 자리: 5 이렇게 분리할 수 있다. 자릿수를 분해하는 알고리즘은 크게 string을 이용하는 방법과 수학적인 방법을 떠올릴 수 있다. 2. 자릿수 분해 알고리즘 1) 반복문 이용하기 아이디어 중학교때 배운 자릿수의 개념을 이용하여 하나씩 가져오는 것이다. 구현 벡터를 이용하면 되는데 이 경우에 자릿수는 벡터의 크기이다. #include #include using namespace std; int a, b; v..

https://www.acmicpc.net/workbook/view/824 문제집: FFT (koosaga) www.acmicpc.net 나중에 풀 실력이 되면 플레를 찍고 모든 알고리즘을 마스터한 뒤 건드려볼 예정.... 그날이 올까?

[백준] 14502번 연구소를 풀다가 화딱지가 나서 겨우겨우 구현했다. 이게 과연 쓸 일이 있을까 해서 그냥 남겨둔다. 백트래킹으로 1차원 배열의 조합은 구현해봤어도 2차원 배열의 조합은 처음 해본다. 생각보다 생각해내기 어려웠다.... 직접 손으로 써보면서 겨우 찾아냈다.. y좌표가 증가하는 순으로 x좌표가 무조건 0부터n-1까지가 아니라 다음 탐색에서 y랑 같을 때만 x이고 그 다음부터는 0부터 n-1까지이다. x부터가 아니라 바로 x+1부터로 하면 되지 않냐? 하는 의문이 들지만 해보면 처음 채울 때에 첫째칸이 안채워진다. 따라서 x부터 하는게 맞다. #include using namespace std; int map[4][4]; int cnt; void print() { for (int i = 0..

1. 개념 간단한 순열과 조합은 기본적인 조건문과 반복문으로 출력할 수 있다. N개의 숫자 중에서 M개를 뽑아 순열, 조합하는 경우를 구해보자. 예를 들어 1~5까지 숫자 중에서 2개를 순열, 중복순열, 조합, 중복조합으로 뽑는다고 해보자. 참고로, 순열은 순서의 개념이 포함되므로 모든 숫자들을 나열하는 경우이고, 조합은 순서의 개념이 없으므로 출력되는 숫자들은 오름차순, 중복조합의 경우 비내림차순이 된다. 2. 구현 코드로 보면 다음과 같다. 순열(P) //순열 #include using namespace std; int check[6]; int main(void) { //ex) P(5, 3) for (int i = 1; i