백준 복습 - 정수론 및 조합론

정수론 및 조합론 - 5086번: 배수와 약수

https://jh4995.tistory.com/141

정수론 및 조합론 - 5086번

---

정수론 및 조합론 - 1037번: 약수

https://jh4995.tistory.com/142

정수론 및 조합론 - 1037번

---

정수론 및 조합론 - 2609번: 최대공약수와 최소공배수

https://jh4995.tistory.com/143

정수론 및 조합론 - 2609번

---

정수론 및 조합론 - 1934번: 최소공배수

https://jh4995.tistory.com/146

정수론 및 조합론 - 1934번

---

정수론 및 조합론 - 2981번: 검문

https://jh4995.tistory.com/161

---

정수론 및 조합론 - 3036번: 링

1) 유클리드 호제법 추가공부

https://jh4995.tistory.com/147

정수론 및 조합론 - 3036번

---

정수론 및 조합론 - 11050번: 이항계수 1

https://jh4995.tistory.com/150

정수론 및 조합론 - 11050번

---

정수론 및 조합론 - 11051번: 이항계수 2

1) 동적 계획법(Dynamic Programming) 추가공부

2) 동적 계획법의 top-down 방식과 down-top방식의 비교에 대한 추가공부

3) 동적 계획법에서의 2차원배열 정적선언 혹은 동적선언 선택 가능여부

https://jh4995.tistory.com/151

정수론 및 조합론 - 11051번

---

정수론 및 조합론 - 1010번: 다리 놓기

1) 곱셈과 나눗셈 동시에 진행시 유의해야하는 점 복습

https://jh4995.tistory.com/153

정수론 및 조합론 - 1010번

---

정수론 및 조합론 - 9375번: 패션왕 신해빈

https://jh4995.tistory.com/160

---

정수론 및 조합론 - 1676번: 팩토리얼 0의 개수

1) 해당 풀이에서 조건문에 (if 를 쓰는 경우 / while 을 쓰는 경우) - 각각 왜 다른지 복습

https://jh4995.tistory.com/155

---

정수론 및 조합론 - 2004번: 조합 0의 개수

1) 1676번 문제의 풀이와 비교해서 변경된 점 복습

https://jh4995.tistory.com/159

정수론 및 조합론 - 2004번

---

정수론 및 조합론의 경우

5086번부터 3036번까지 6개의 정수론 부분과 나머지 6개의 조합론 부분으로 구성되어 있다

 

- 정수론 부분에서는 최대공약수와 최소공배수 구하는 것이 주된 내용이다

이를 위해서는 다른 방법도 있지만, 결국 유클리드 호제법을 이용하는 것이 가장 간단하면서 중요하다

가장 까다로운 2981번에 대해서는 전체적인 복습이 필요하다

// 최대공약수(Greatest Common Divisor) 구하기
int GCD(int a, int b)
{
	if(b == 0)
	{
		return a;
	}
	else
	{
		return GCD(b, a % b);
	}
}

// 최소공배수(Least Common Multiple) 구하기
int LCM(int a, int b)
{
	return (a * b) / GCD(a, b);
}

 

- 조합론 부분에서는 mCn 의 형태를 기본으로 놓고, 이를 m! / n! (m-n)! 혹은 mPn / n! 으로 바꾸면서 계산한다

이 과정에서 분모에 위치하게되는 팩토리얼의 숫자 범위에 의해서 오버플로가 발생할 수 있으므로,

n!을 한 번에 나누지않고 1부터 n까지의 숫자를 하나씩 나누는 방식으로 바꾸는 등의 다른접근이 필요하기도 하다

또한 동적계획법이라는 알고리즘이 존재한다

// 동적계획법
int dp[1001][1001];

int cal(int n, int k)
{
	for (int i = 0; i <= n; i++)
	{
		for (int j = 0; j <= k; j++)
		{
			if (i == j || j == 0)
			{
				dp[i][j] = 1;
			}
			else
			{
				dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % 10007;
			}
		}
	}
	return dp[n][k];
}