Selection Algorithms, Number Theory, Permutation and combinations
선택 알고리즘, 정수론, 순열과 조합
Contents
1️⃣ 선택 알고리즘 (Selection Algorithms)
2️⃣ 정수론 (Number Theory)
3️⃣ 순열과 조합 (Permutation and Combination)
4️⃣ 이항계수 (Binomial coefficient)
1️⃣ 선택 알고리즘 (Selection Algorithms)
선택 알고리즘의 원리와 동작 #1 - 개요
선택 알고리즘(Selection Algorithms)이란 주어진 배열에서 i번째 작은 원소를 찾는 알고리즘이다.
선택 알고리즘의 원리와 동작 #1 - 퀵 정렬과 선택 알고리즘 비교
퀵 정렬 (Quick Sort):
먼저 피벗(pivot) 값(예시에서는 5)을 선택하였다.
배열은 피벗 값보다 작은 값들(1, 4, 3, 2)과 큰 값들(8, 6, 7)로 나다.
이 두 서브 배열에 대해 재귀적(Recursive)으로 정렬을 수행하게 된다.
시간 복잡도:
- 평균 시간: Θ(n log n), 최악의 경우 시간: Θ(n²)
재귀적(Recursive) "재귀적"이라는 말은 어떤 함수나 알고리즘이 자기 자신을 반복적으로 호출하는 방식을 의미한다. 쉽게 말해, 문제를 더 작은 문제로 쪼개서 해결하는 방식이다. 예를 들어, 위의 예제인 퀵 정렬에서 재귀적이라는 것은, 배열을 피벗을 기준으로 두 개의 작은 배열로 나눈 후, 이 작은 배열들에 대해 다시 퀵 정렬을 반복적으로 수행하는 것을 말한다. 이렇게 계속해서 배열을 나누고 정렬하다 보면, 더 이상 나눌 수 없을 때 최종적으로 모든 배열이 정렬되게 된다.
선택 알고리즘 (Selection Algorithm):
선택 알고리즘은 숫자(피벗 값)를 선택하고, 선택된 숫자가 고려 중인 그룹에 포함되는지를 확인한다.
만약 숫자가 포함된다면 (이미지에서 왼쪽 서브 배열), 그 그룹 내에서 다시 검색이 시작된다.
숫자가 포함되지 않으면 (오른쪽 서브 배열) 해당 그룹은 고려하지 않는다.
시간 복잡도:
- 평균 시간: Θ(n), 최악의 경우 시간: Θ(n²)
각 시간 복잡도 비교:
Θ(n log n): 중간 효율이다. 예를 들어, 퀵 정렬의 평균적인 경우가 이 시간 복잡도를 가지는데 n이 커져도 비교적 효율적이다.
Θ(n): 가장 효율적인 함수이다. 데이터 크기가 n일 때, 입력 크기 n에 비례하여 처리 시간이 증가한다. 입력 크기가 커져도 비교적 덜 느려진다. 기수정렬, 계수정렬이 해당된다.
Θ(n²): 가장 비효율적인 함수이다. n이 커지면 시간 복잡도가 빠르게 증가한다. 예를 들어, 버블 정렬이나 삽입 정렬 같은 알고리즘의 최악의 경우가 이 시간 복잡도를 가지게 된다.
결론: **Θ(n log n)**은 보통 효율적인 정렬 알고리즘에서 사용되며, **Θ(n)**은 선형적으로 증가하므로 더 효율적이다.
**Θ(n²)**은 비효율적이기 때문에 큰 데이터셋에 사용하기 적합하지 않다. 따라서, **Θ(n²)**이 가장 효율이 낮은(즉, 가장 느린) 함수라고 할 수있다.
선택 알고리즘의 원리와 동작 #2 - 퀵 정렬과 선택 알고리즘 세부 절차 비교
퀵 정렬 (Quick Sort)
partition(A, p, r)을 사용하여 배열을 분할한다..배열의 왼쪽 부분을 재귀적으로 정렬한다.
quickSort(A, p, q)배열의 오른쪽 부분을 재귀적으로 정렬한다.
quickSort(A, q+1, r)
퀵 정렬은 배열을 분할한 후, 각 부분 배열을 다시 정렬하는 과정을 반복적으로 수행하는 알고리즘이다.
선택 알고리즘 (Selection Algorithm)
마찬가지로
partition(A, p, r)을 사용하여 배열을 분할한다.pivot값과 선택하려는 i값을 비교하여, 그 값이 속해 있는 부분만 선택한다.select(A, __ , __)
선택 알고리즘은 선택하려는 값이 속한 부분만 집중적으로 탐색하여 선택하는 방법을 사용한다. 이 과정에서 partition을 사용해 배열을 나누고, 해당 부분만 다시 탐색하는 특징이 있다.
두 알고리즘 모두 분할(Partition) 과정을 공유하고 있으며, 퀵 정렬은 배열 전체를 재귀적으로 정렬하는 반면, 선택 알고리즘은 필요한 값이 있는 부분만 탐색하는 방식이다.
✅선택 알고리즘에서 퀵정렬이 언급되는 이유는 무엇인가요?
선택 알고리즘이 퀵 정렬을 언급하는 이유는 분할(Partition) 방법을 동일하게 사용하기 때문이다. 퀵 정렬이 배열 전체를 정렬하기 위해 이 분할 과정을 사용하는 반면, 선택 알고리즘은 배열의 일부만 탐색해 원하는 값을 효율적으로 찾는다. 참고로 퀵 정렬(Quick Sort)은 분할 정복(Divide and Conquer) 알고리즘을 사용한다. 이 알고리즘은 문제를 더 작은 하위 문제들로 나누고, 그 하위 문제들을 각각 해결한 다음, 다시 결합하여 최종 해결을 얻는 방식이다.
선택 알고리즘의 원리와 동작 #3 - 선택 알고리즘의 동작1
이 과정은 선택 알고리즘 중 하나인 퀵 셀렉트(Quick Select) 알고리즘을 시각화한 것으로, 퀵 정렬에서 사용하는 분할(Partition) 기법을 사용하여 원하는 순위(k번째 작은 값)를 빠르게 찾아내는 방식이다.
입력 배열: 위의 배열에서 2번째로 작은 원소를 찾는 것이 목표이다.
분할 과정: 배열이 피벗 값 15를 기준으로 두 부분으로 나뉘었다. 피벗 값 15은 배열 내에서 어떤 위치에 있는지 확인할 수 있다.
피벗 값보다 작은 값들:
8, 11, 3피벗 값보다 큰 값들:
31, 48, 20, 29, 65, 73
왼쪽 그룹에서 2번째 작은 원소를 찾음: 왼쪽 그룹은 이미 작은 값들로 이루어져 있으며, 이 안에서 2번째 작은 값은 8이다.
✅ 선택 알고리즘은 하나가 아니라 여러개 인건가요?
선택 알고리즘은 k번째 작은 값이나 큰 값을 찾기 위한 여러 가지 알고리즘을 포괄하는 용어이다. **퀵 셀렉트(Quick Select)**는 그 중 하나이며, 효율적이고 많이 사용되는 방법이다. 정렬, Median of Medians 등 다양한 알고리즘이 존재하며, 문제의 성격에 따라 적절한 알고리즘을 선택할 수 있다.
선택 알고리즘의 의사코드와 분석#1 - 선택 알고리즘의 의사코드
💡요약: 이 알고리즘은 **퀵 정렬(Quick Sort)**에서 사용하는 분할(Partition) 방식과 동일한 아이디어를 사용하며, 배열을 분할한 후 필요한 부분만 탐색하여 i번째 작은 원소를 찾고있다. 이 과정을 통해 배열 전체를 정렬하지 않고도 원하는 원소를 효율적으로 찾을 수 있게된다.
시간 복잡도는 평균적으로 **O(n)**이지만, 최악의 경우에는 **O(n²)**가 될 수 있다.
입력 변수:
A: 배열,p, r: 배열의 시작과 끝 인덱스,i: 찾고자 하는 작은 원소의 순서
기본 구조:
종료 조건: 배열에서 원소가 하나만 남은 경우(
p = r), 그 원소를 반환합니다. 이때i는 1이 된다.partition(A, p, r)을 호출하여 배열을 분할하고, 피벗을 기준으로 배열을 두 그룹으로 나눈다.k = q - p + 1: 여기서k는 피벗이 전체 배열에서 몇 번째 작은 원소인지를 의미한다.
분기 처리:
if (i < k): 만약 찾고자 하는i번째 원소가k보다 작다면, 이는 왼쪽 그룹에 위치한다는 의미이므로, 왼쪽 그룹(A[p, q-1])에서 다시select를 호출한다.else if (i == k): 만약i가k와 같다면, 피벗 값이 바로 우리가 찾는 값이므로 피벗(A[q])을 반환한다.else:i가k보다 크다면, 이는 오른쪽 그룹에 위치해 있다는 의미이므로, 오른쪽 그룹(A[q+1, r])에서 다시select를 호출한다.
선택 알고리즘의 의사코드와 분석 #2 - 평균적인 복잡도를 가질때
선택 알고리즘의 평균적인 경우의 시간 복잡도 분석을 살펴보자. 이 분석은 퀵 셀렉트(Quick Select) 알고리즘의 시간 복잡도가 평균적으로 **O(n)**이라는 것을 증명하는 과정이다.
분석의 주요 요소:
T(n)의 재귀식:
T(n)≤1n∑k=1nmax[T(k−1),T(n−k)]+Θ(n)
이 식은 배열을 피벗을 기준으로 분할하고, 분할된 배열 중 큰 쪽을 처리하는데 필요한 시간 복잡도를 나타내고 있다. 여기서 중요한 것은 배열을 나눈 후 어느 쪽을 선택하느냐에 따라 시간 복잡도가 달라진다는 점이다.
재귀 호출을 제외한 오버헤드:
- 분할 과정에서 피벗을 선택하고 배열을 나누는 비용은 **Θ(n)**이다. 이는 각 단계마다 발생하는 기본적인 처리 비용이다.
최대값(max)의 처리:
max[T(k-1), T(n-k)]: 이는 분할된 배열의 두 부분 중 더 큰 부분을 선택하여 처리하는 비용을 나타낸다. 예를 들어, 배열을 피벗으로 나눴을 때 왼쪽이나 오른쪽 부분 중 더 큰 부분을 처리하는데 걸리는 시간 복잡도를 나타낸다.
T(n) = O(n) 증명**:
이 재귀식을 분석한 결과, 평균적인 경우의 시간 복잡도가 **T(n) = O(n)**임을 증명할 수 있다.
T(n)≤cn 임을 추정 후, 증명법을 사용하여 **O(n)**임을 증명하였다.
또한 **T(n) = Ω(n)**임은 자명하기 때문에 최종적으로 **T(n) = Θ(n)**으로 정리된다.
선택 알고리즘의 의사코드와 분석 #3 - 최악의 복잡도를 가질때
퀵 셀렉트(Quick Select) 알고리즘은 최악의 경우 **Θ(n²)**의 시간 복잡도를 가질 수 있다. 이는 피벗이 계속해서 최악의 위치에 선택되어 배열을 매우 불균형하게 나누는 경우 발생한다.
분석 내용:
T(n)의 재귀식:
최악의 경우, 배열이 매우 불균형하게 분할된다. 즉, 배열이 피벗을 기준으로 0: n-1로 나뉘게 되어, 한쪽만 계속 처리해야 하는 상황이 발생한다. 이로 인해 재귀적으로 처리해야 할 배열의 크기가 매번 1씩 감소하게 된다.
이 경우, 시간 복잡도는 다음과 같이 표현됩니다: T(n)=T(n−1)+Θ(n)
여기서
T(n-1)은 크기가 n-1인 배열을 처리하는 시간,\Theta(n)은 분할에 소요되는 시간이다.
분할이 0: n-1로 이루어짐:
- 피벗 값이 매번 최악의 선택이 되어 한쪽 부분 배열만 계속해서 처리해야 하는 경우를 의미한다. 이 상황에서는 분할이 매번 불균형하게 이루어져서 가장 비효율적인 방식으로 진행된다.
시간 복잡도 계산:
- 이러한 재귀식이 n번 반복되므로, **총 시간 복잡도는 Θ(n²)**가 된다. 이는 최악의 경우 퀵 셀렉트 알고리즘의 성능이 매우 떨어지는 경우를 나타낸다.
개선된 선택 알고리즘 #1 - 기존 선택 알고리즘의 단점
💡요약: 기존 선택 알고리즘의 문제는 분할의 불균형에 있다. 이에 따라 수행 시간이 영향을 받기 때문이다. 이 단점을 개선하기 위한 포인트는 최악의 경우여도 분할의 균형이 보장되도록 해야한다. 그리고 이 균형을 유지하기 위한 오버헤드가 지나치게 크면 안된다.
이를 개선하기 위해서는 균형 잡힌 분할을 보장하고 중앙값을 활용해야한다. 이러한 방식은 Median of Medians 알고리즘의 아이디어를 반영한 것으로, 피벗 선택을 더 현명하게 하여 최악의 경우에도 성능을 보장하는 데 도움이 된다.
개선된 선택 알고리즘 #2 - 개선된 선택 알고리즘 아이디어
1. 원소들을 그룹화(Group the elements)
배열의 원소들을 일정 개수 이상의 그룹으로 묶는다.
이렇게 그룹화함으로써 분할의 불균형(imbalance in partitioning) 문제를 완화할 수 있다. 즉, 최악의 경우에 배열이 매우 불균형하게 나누어지는 것을 방지한다.
2. 그룹의 중앙값 활용(Utilize the median of the group)
각 그룹의 중앙값을 계산한 후, 이를 선택 알고리즘에서 **피벗(pivot)**으로 활용한다.
중앙값은 그룹 내에서 중간에 위치한 값으로, 이를 피벗으로 사용하면 배열을 더 균형 있게 나눌 수 있다.
그림에서처럼 각각의 그룹에서 중앙값을 선택하면, 더 적절한 피벗을 사용하여 배열을 보다 효율적으로 분할할 수 있다.
개선된 선택 알고리즘 #3 - 5개의 원소로 그룹핑 시에 원소들의 대소 관계(inequality)
Median of Medians 알고리즘에서 각 그룹을 묶은 후, 각 그룹의 중앙값을 기준으로 원소들을 분할하는 과정을 보여주고있다. 이는 분할의 불균형을 방지하고, 최악의 경우에도 성능을 보장할 수 있다.
설명:
각 그룹의 중앙값(The median of each group)
5개의 원소로 이루어진 각 그룹에서 중앙값을 선택하여 분할의 기준점으로 사용
각 그룹의 중앙값은 네모로 표시되어 있으며, 이 중앙값들이 다시 그룹의 분할에 사용됨
M보다 작은 원소와 큰 원소(Elements smaller than M and elements larger than M)
M은 분할의 기준이 되는 중앙값이다.M보다 작은 원소들은 그룹 내에서
M보다 작은 원소들로 표시되고, 이들은 검정색 원으로 나타내고 있다.M보다 큰 원소들은 그룹 내에서
M보다 큰 원소들로 파란색 원으로 표시되고있다.
최악의 경우에도 균형 유지(Maintain balance even in the worst case)
최악의 경우에도 7n/10 + 2 개 이상의 원소가 처리되기 때문에, 최악의 경우에도 상당히 균형 있게 분할할 수 있음을 강조하고 있다.
이는 분할이 지나치게 한쪽으로 치우치지 않도록 중앙값을 사용하여 불균형을 줄이는 데 기여한다.
개선된 선택 알고리즘 #4 - 개선된 선택 알고리즘의 의사코드
개선된 알고리즘인 Median of Medians 방식을 기반으로 하는 linearSelect 함수의 동작 방식을 나타내고 있다. 최악의 경우에도 균형 잡힌 분할을 보장하는 선택 알고리즘이다. 이를 통해 시간 복잡도 **O(n)**를 유지하면서 원하는 i번째 작은 원소를 찾을 수 있게 된다.
원소 수가 5개 이하인 경우:
- 만약 배열의 원소가 5개 이하이면, 원소를 직접 선택하고 알고리즘을 종료한다.
5개씩 원소를 그룹화:
- 배열의 원소들을 5개씩 묶어서 총 [n/5]개의 그룹으로 나눈다.
각 그룹의 중앙값 찾기:
각 그룹에서 중앙값을 찾는다. 그룹의 크기가 5개라면, 중앙값은 3번째 원소이다.
이렇게 구한 중앙값들을 m1,m2,…라고 한다.
중앙값들의 중앙값 MMM 찾기:
다시 이 중앙값들에서 중앙값 MMM을 구한다. 이를 위해 linearSelect 함수를 재귀적으로 호출하여 중앙값 MMM을 찾는다.
원소의 개수가 홀수면 중앙값이 하나이므로 문제 없고, 짝수일 경우에는 두 중앙값 중 하나를 선택한다.
MMM을 기준으로 배열 분할:
- MMM을 기준으로 배열을 분할합니다. MMM보다 작은 값들은 왼쪽에, 큰 값들은 오른쪽에 배치합니다.
재귀적 호출:
- 원하는 값을 찾기 위해 분할된 두 그룹 중에서 적합한 쪽을 선택하여 1~6 단계를 반복적으로 수행한다. 이때 linearSelect 함수를 다시 호출한다.
개선된 선택 알고리즘 #5 - 개선된 선택 알고리즘의 의사코드 분석
💡요약: pivot(M)보다 크거나 작은 원소가 7n/10 + 2개 이상이라는 설명은, 선택 알고리즘에서 피벗 선택 후에도 여전히 충분히 많은 원소들이 남아 있어 재귀적 호출이 필요하다는 것을 의미한다. 이 설명을 통해 Median of Medians 알고리즘이 최악의 경우에도 시간 복잡도를 **O(n)**으로 유지할 수 있음을 보장한다.
T(n/5): n개의 원소를 5개씩 그룹으로 묶어서 각 그룹의 중앙값을 찾는 데 걸리는 시간
T(7n/10 + 2): 피벗(M)보다 크거나 작은 원소 중 적어도 7n/10 + 2 개 이상의 원소가 남는 경우, 즉 분할 후 처리해야 하는 원소들의 양을 나타낸다. 피벗을 기준으로 남은 큰 쪽의 배열을 처리하는 데 걸리는 시간이다.
Θ(n): 배열을 피벗으로 나누는 데 필요한 시간(분할 오버헤드)을 의미한다.
2️⃣ 정수론 (Number Theory)
정수론의 개요와 적용 사례 #1 - 정수론의 주요 대상
정수론은 정수를 대상으로 하는 학문으로써 매우 넓은 수학 분야로, 소수, 산술함수, 정수방정식은 그중 대표적인 주제들 중 하나이다.
- 소수 (Prime Numbers): 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수
산술함수 (Arithmetic Functions):
최대공약수 (Greatest Common Divisor, GCD)
최소공배수 (Least Common Multiple, LCM)
소인수분해 (Prime Factorization)
등등
정수방정식 (Diophantine Equations): 다양한 방법으로 정수해를 구하는 과정
정수론의 개요와 적용 사례 #2
- 암호학과 소수(Cryptography and Prime numbers)
정수론에서 소수는 암호학의 핵심 요소이다. 특히, 소수의 곱을 소인수분해하는 것이 매우 어려운 문제임을 활용하여 RSA와 같은 암호 알고리즘이 설계되었다. 또한 이산 로그 문제와 같은 정수론적 문제를 기반으로 한 암호 시스템도 많이 사용되고 있다. 소수의 이러한 특성 덕분에 현대 암호학은 매우 강력한 보안을 제공할 수 있게 되었다.
💡RSA 알고리즘은 두 개의 큰 소수를 사용하여 공개키와 개인키를 생성한다. 공개키는 누구나 접근할 수 있고 개인키는 소유자만이 알고 있는 비밀이다. 메시지는 공개키를 사용해 암호화되고, 개인키를 통해 복호화된다. RSA의 보안은 두 개의 큰 소수를 곱하여 얻은 n을 소인수분해하는 것이 매우 어려운 문제라는 것에 기반하였다.
정수론의 개요와 적용 사례 #1
- 컴퓨터공학에서의 정수론 사례
정수론은 컴퓨터공학에서 다양한 분야에 걸쳐 중요한 역할을 한다. 암호학뿐만 아니라 난수 생성, 오류 검출, 해시 함수, 그래픽스, 압축, 분산 시스템 등 컴퓨터공학의 다양한 분야에서 중요한 역할을 하고 있다. 정수론의 이론적 성질들이 실제 시스템의 안정성, 보안, 효율성을 높이는 데 기여하기 때문이다. 그중 대표적인 사례들을 소개하면 다음과 같다.
왼쪽:
암호학 (Cryptography): 앞서 설명한 대로, 정수론은 암호화 방법(예: RSA)에 사용된다.
의사난수 생성기 (Pseudo-Random Number Generator): 난수 생성은 암호학, 시뮬레이션, 통계 등 여러 분야에서 필요로 한다. 의사난수 생성기(Pseudo-Random Number Generator, PRNG)는 예측할 수 없는 난수를 생성해야 하는데, 이를 위해 정수론적 알고리즘을 자주 사용한다.
소수 판별기 (Prime Testing): 숫자가 소수인지 여부를 판단하는 알고리즘으로, 암호 시스템에서 필수적이다.
오른쪽:
소인수분해 (Prime Factorization): 압축 알고리즘은 데이터를 효율적으로 저장하고 전송하기 위해 사용된다. 소인수분해와 같은 정수론적 기술을 활용하여 데이터 중복을 최소화하고 더 작은 크기로 압축할 수 있다. 예를 들어 영상 압축이나 오디오 압축에서 정수론적 개념이 사용된.
소수 생성기 (Prime Generation): 안전한 암호화 키를 생성하기 위해 큰 소수를 생성하는 과정이다.
해시 함수 (Hash Function): 주어진 데이터를 고정된 크기의 해시값으로 변환하는 알고리즘으로, 암호학과 데이터 무결성 검증에 사용된다. 해시 함수는 모듈러 연산과 같은 정수론적 연산을 활용하여 충돌을 최소화하고, 데이터를 고유하게 변환하는 역할을 한다. 예를 들어, SHA-256과 같은 암호 해시 함수는 블록체인과 디지털 서명에서 중요한 역할을 한다.
에라토스테네스의 체(Sieve of Eratosthenes)
💡Keyword: 제곱근 탐색 최적화(Square root search optimization), 배수 제거 방식(Method of eliminating multiples), 암호학(Cryptography), 기본적인 수학 알고리즘(Basic Mathematic Algorithms)
소수를 효율적으로 판별하기 위한 고전적인 방법 중 하나이다. 에라토스테네스의 체는 2부터 순차적으로 탐색하면서 소수의 배수를 제거하는 방식으로 소수를 판별하는 알고리즘이다.
에라토스테네스의 체가 작동하는 원리는 다음과 같다:
1차원 리스트 생성: 구하고자 하는 소수의 범위만큼 크기의 1차원 리스트를 생성한다. 이 리스트는 해당 숫자가 소수인지 아닌지를 나타낸다.
소수의 배수 제거: 2부터 시작하여 현재 숫자가 지워지지 않은 상태(즉, 소수일 가능성이 있는 경우)라면, 그 숫자의 배수에 해당하는 숫자들을 리스트에서 끝까지 탐색하며 지운다. 처음 선택된 숫자는 지워지지 않는다.
소수 출력: 리스트의 끝까지 2번 과정을 반복한 후, 리스트에 남아 있는 모든 수는 소수이므로 이를 출력한다.
알고리즘의 동작 과정을 살펴보자. ⬇️
- 리스트에서 숫자 1은 소수가 아니므로 먼저 제거된다. 그리고 2를 선택하여, 소수임을 확인한다. 2는 소수이기 때문에 지워지지 않는다.
- 2의 배수들이 모두 제거되었다. 4, 6, 8, 10, 12, 14 등 2의 배수인 숫자들이 모두 리스트에서 지워진다. 그 결과, 2는 남아있고, 그 배수들이 모두 제거되었다.
- 이제 3이 소수임을 확인하고 3의 배수들을 제거한다. 9, 15, 21, 27 등 3의 배수인 숫자들이 지워졌다.
- 5가 소수임을 확인하고, 5의 배수들을 제거한다. 25가 지워지며, 이로써 리스트에서 남아 있는 소수 후보들이 정리되었다.
- 남아 있는 숫자들이 모두 소수임을 나타낸다. 최종적으로 2, 3, 5, 7, 11, 13, 17, 19, 23, 29가 소수로 확인되었다.
Sieve of Eratosthenes의 의사코드를 살펴보자 ⬇️
M(시작 수)와 N(종료 수)의 범위를 설정하고, A(소수 리스트)를 사용하여 소수를 구하는 과정이다.
A 리스트 초기화: 리스트의 각 요소를 인덱스 값으로 초기화한다. 예를 들어, A[2] = 2, A[3] = 3과 같은 방식으로 설정된다.
N의 제곱근까지 탐색: 반복문을 통해 N의 제곱근까지만 탐색한다. 이는 효율적인 소수 판별을 위한 중요한 최적화 방식이다. 소수가 아닌 수는 해당 수의 배수들로 표시된다.
소수의 배수 지움: 현재 숫자가 소수가 아니면 넘어가고, 소수인 경우 그 수의 배수들을 제거한다.
최종 소수 출력: N까지의 소수 값을 출력하는 과정이다.
💡중요 N의 제곱근까지만 탐색하는 이유는 수학적으로 N = a * b일 때, a와 b가 모두 N의 제곱근보다 클 수 없기 때문이다. 제곱근 이상부터는 이미 배수들이 지워졌기 때문에 탐색을 더 이상 할 필요가 없다. 이 말은 불필요한 연산을 줄일 수 있어 큰 수의 소수를 구할 때 매우 효과적이다.
Sieve of Eratosthenes의 파이썬 코드를 살펴보자 ⬇️
import math
M, N = map(int, input().split()) #1
A = [0] * (N + 1) #2
for i in range(2, N + 1): #3
A[i] = i
for i in range(2, int(math.sqrt(N)) + 1): # 4 제곱근까지만 수행
if A[i] == 0: #5
continue
for j in range(i + i, N + 1, i): # 6 배수 지우기
A[j] = 0
for i in range(M, N + 1): #7
if A[i] != 0:
print(A[i])
#1 :
M,N은 사용자 입력으로 받아들인 범위 값이다.M부터N까지의 소수를 구하려고 한다..#2 :
A는N까지의 숫자를 담는 리스트로, 초기에 모두 0으로 초기화된다.#3 : 2부터 N까지의 숫자를 리스트
A에 저장한다. 이때, 초기값은 해당 인덱스 값을 가진다.#4 : 2부터 N의 제곱근까지 반복문을 수행한다. 이는 효율성을 위해서 제곱
근까지만 탐색하는 부분이다.
#5
A[i]가 0인 경우(이미 배수로 지워진 숫자)는 넘어간다.#6 소수의 배수들을 지우는 과정이다.
i의 배수들은 0으로 설정하여 소수가 아님을 표시한다.#7 M부터 N까지 범위 내에서 리스트
A에 0이 아닌 숫자(즉, 소수)들을 출력한다.
💡중요한 부분
효율성: 에라토스테네스의 체는 소수를 찾기 위한 매우 효율적인 알고리즘다. 시간 복잡도는O(n log log n)으로, 특히 큰 범위에서 소수를 찾을 때 성능이 뛰어나다. 알고리즘을 최적화할 때 중요한 고려 사항 중 하나는 시간 복잡도와 공간 복잡도인데, 이 알고리즘은 그 점에서 효율적이다.
리스트 사용법: 이 알고리즘은 1차원 리스트를 활용하는데, 이는 소프트웨어 개발에서 흔히 사용되는 자료구조이다. 리스트를 다루는 기술과 자료를 효율적으로 처리하는 방법에 대해 배울 수 있다. 또한 리스트 초기화, 순차 탐색, 요소 제거 등의 동작이 포함되어 있어 데이터 처리의 기본 개념을 연습할 수 있다.
배수 제거 최적화: 현재 숫자의 배수를 제거할 때 불필요한 연산을 줄이는 것이 중요하다. 예를 들어, 특정 숫자의 배수를 제거할 때 그 숫자의 제곱부터 시작하면 이미 제거된 숫자를 다시 처리하는 것을 피할 수 있다. 이는 알고리즘 최적화에서 중요한 개념이다.
병렬 처리: 에라토스테네스의 체는 병렬 처리로도 구현할 수 있는 가능성이 있다. 예를 들어, 여러 코어를 사용하는 경우 각 코어가 숫자의 일부분을 담당해 배수를 제거하는 방식으로 성능을 더욱 높일 수 있다.
유클리드 호제법(Euclidean algorithm)
💡Keyword: 최대공약수(GCD), 모듈러 연산(MOD), 재귀함수(Recursion Function), 암호학(Cryptography), 기본적인 수학 알고리즘(Basic Mathematic Algorithms)
유클리드 호제법은 두 수의 최대공약수(GCD, Greatest Common Divisor)를 구하기 위해 모듈러(MOD) 연산을 사용하는 알고리즘이다. 두 수를 나눈 나머지를 구하는 연산을 반복하여 최대공약수를 계산한다. A와 B를 나눈 나머지 Q를 구한다. 유클리드 호제법에서는 나머지가 0이 될 때까지 이 과정을 반복하며, 마지막으로 남은 값이 두 수의 최대공약수(GCD)이다.
Euclidean Algorithms 예시 ⬇️
유클리드 호제법을 이용해 두 수, 270과 192의 최대공약수(GCD)를 구하는 과정을 시각적으로 살펴보자
첫 번째 단계: 큰 수 270을 작은 수 192로 MOD 연산(나눗셈 후 나머지 계산)을 수행한다. 270 % 192 =78
나머지가 78이므로 다음 단계로 진행한다.
두 번째 단계: 앞에서 나온 나머지 78을 새로운 작은 수로 삼아, 192와 다시 MOD 연산을 수행한다. 192 % 78 = 36
나머지가 36이므로 다음 단계로 진행한다.
세 번째 단계: 동일하게 78과 36으로 MOD 연산을 수행한다. 78 % 36 = 67
나머지가 6이므로 다음 단계로 진행한다.
마지막 단계: 이제 36과 6을 가지고 MOD 연산을 수행한다.
36 % 6 = 0
나머지가 0이 되었으므로, 이때 작은 수 6이 최대공약수가 된다.
최종적으로 gcd (270,192) = 6이 된다. 즉, 270과 192의 최대공약수는 6이다.
Euclidean Algorithms 의사코드 ⬇️
gcd(a, b):
if b가 0이면:
a가 최대 공약수
else:
gcd(작은 수, 큰 수 % 작은 수) # 재귀 함수 형태로 구현
gcd(a, b): 두 수 a와 b의 최대공약수를 구하는 함수이다.
조건문:
b = 0인 경우, 이때 남은 수 a가 최대공약수가 된다.
그렇지 않다면, 재귀 호출을 통해 다시 두 수의 최대공약수를 구한다. 이때, 새로운 두 수는 기존의 작은 수와 큰 수를 작은 수로 나눈 나머지로 설정된다.
재귀 호출(Recursive call): 이 과정이 나머지가 0이 될 때까지 반복되며, 결국 최대공약수를 구할 수 있다.
Euclidean Algorithms 파이썬 코드 ⬇️
def gcd(a, b):
if b === 0:
return a
else:
return gcd(b, a % b # 재귀 함수 형태로 구현
함수 정의:
gcd(a, b)는 두 수 a와 b의 최대공약수(GCD)를 구하는 함수조건문:
if b == 0: 만약 두 번째 인수 b가 0이 되면, 첫 번째 인수 a가 최대공약수로 반환된다. 이는 유클리드 호제법의 종료 조건이다.그렇지 않다면,
gcd(b, a % b)를 호출하여 재귀적으로 나머지를 계산하고, 이 과정을 반복한다.
MOD 연산: 큰 수 a를 작은 수 b로 나눈 나머지를 계산한다. 이 나머지를 다시 함수에 넣어서 계속해서 나눗셈을 반복한다.
재귀 호출: 나머지가 0이 될 때까지 재귀적으로 호출되며, 그 결과 a가 최대공약수로 반환되게 된다.
3️⃣ 순열과 조합 (Permutation and Combination)
💡Keyword: P(n,r), nPr 점화식(Recurrence relation), 동적계획법(Dynamic programming), 이항계수(Binomial coefficient), 순열의 순서 계산
순열과 조합의 중요성 (Importance of Permutation and Combination) ⬇️
순열과 조합은 fundamental principles of algorithms in the field of discrete probability(이산확률)이다. 이는 특정 집합에서 요소를 선택하고 배열하는 다양한 경우의 수를 계산하는 기초적인 개념이라고 할 수 있다. 순열은 선택한 원소들의 순서가 중요할 때 사용하는 방식이다. 반면에 조합은 선택된 원소들의 순서가 중요하지 않으므로, 어떤 원소들이 선택되었는지만을 따지는 경우에 사용된다.
응용 분야:
- Weather prediction, disease prediction, and outcome prediction에서 순열과 조합은 매우 중요하다. 이 개념들은 다양한 경우의 수를 계산하고 분석하는 데 사용되며, predictive algorithms 개발에 필수적인 역할을 한다.
사고방식 훈련:
- training in recurrence relations과 recursive thinking의 훈련에 매우 중요한 역할을 한다. 순열과 조합을 이해하고 사용하는 것은 문제 해결에서 사고의 유연성을 높이고, 복잡한 문제를 더 작은 단위로 나누어 해결하는 능력을 향상시킬 수 있다.
💡소프트웨어 엔지니어로서 알아야 할 중요한 부분:
Fundamentals of Discrete Probability and Algorithms: 순열과 조합은 알고리즘 개발에서 자주 등장하는 개념이다. 특히, backtracking, dynamic programming 등과 같은 알고리즘을 구현할 때 중요한 기반이 된다.
Predictive Models and Data Analysis: 순열과 조합을 이해하면 probability-based predictive models을 구축하거나, 데이터 분석에서 다양한 경우의 수를 효율적으로 처리할 수 있다. 특히 기상 예측, 승부 예측 등의 분야에서 중요한 역할을 한다.
Recursive Thinking: 순열과 조합은 training in recursive thinking을 훈련하는 데 매우 유용하다. 이는 복잡한 문제를 작은 부분으로 나누어 해결하는 데 도움이 되며, dynamic programming과 같은 고급 알고리즘의 이해를 돕는다.
순열의 개념 ⬇️
- 서로 다른 원소들을 순서를 고려하여 일렬로 배열하는 것을 순열이라고 한다. 즉, 순열에서는 선택된 요소들의 순서가 매우 중요하다.
순열의 수: 서로 다른 n개의 원소 중에서 r개를 선택하여 배열하는 순열의 수는 P(n, r) 또는 nPr로 나타낸다. 이는 선택된 원소들을 어떻게 배열하는지가 중요한 경우의 수를 계산할 때 사용된다.
순열의 예시 ⬇️
첫 번째 예:
- 5개의 숫자 (1, 2, 3, 4, 5)를 일렬로 나열한 순열의 예시이다. 3 1 2 5 4
두 번째 예:
- 5개의 숫자 중 3개를 뽑아 일렬로 나열한 예시이다.
순열에서는 숫자를 어떻게 배열하는지가 중요하다. 5개 전체를 사용하거나 일부를 선택해 나열할 때, 선택된 숫자의 순서에 따라 다른 결과가 나오게 된다.
순열의 점화식 Recurrence relation of permutation ⬇️
순열이 점화식을 통해 구체적으로 어떻게 계산할 수 있는지를 알아보자
전체 원소를 나열하는 경우
상황: n개의 원소가 있다고 가정한다. 이 모든 원소를 나열하는 경우를 생각해 보자
핵심 아이디어:
n개의 원소 중에서 마지막에 들어갈 원소를 먼저 선택한다. 그러면 이제 나머지 n−1 개의 원소를 남은 자리에서 배치하는 문제로 바뀐다.
즉, 전체 n개를 배치하는 문제는 마지막 원소를 하나 고르고 나머지 n−1개를 배치하는 문제로 나눌 수 있게된다.
마지막 자리에 들어갈 원소를 고르는 경우의 수는 n가지.
남은 n−1 개를 나열하는 경우의 수는 P(n−1,n−1)
이를 점화식으로 표현하면: P(n,n) = n × P (n−1, n−1)
여기서 P(n,n)은 n개의 원소를 전부 다 배열하는 경우의 수이다.
결과:
마지막 자리까지 모든 원소를 나열하게 되면 결국 P(n,n) = n ! (팩토리얼)로 계된다.
즉, n개의 원소를 모두 나열하는 경우의 수는 𝑃(𝑛, 𝑛) = 𝑛 × (𝑛 − 1) × ⋯ × 1 = 𝑛! 이 된다.
중요 포인트: 모든 원소를 순서를 고려해 나열할 때는 팩토리얼 계산을 통해 쉽게 계산할 수 있다.
일부 원소만 나열하는 경우
상황: 이번에는 n개의 원소 중 일부, 예를 들어 r개만 선택하여 나열하는 경우를 생각해 보자. 예를 들어 5개의 원소 중에서 3개만 선택해 나열하는 경우처럼.
핵심 아이디어:
먼저, n개 중에서 일부 r개의 원소를 선택하고 그 선택된 r개의 원소를 일렬로 나열한다.
동시에 나머지 n−r 개의 원소도 나열하는 경우를 함께 고려하여 전체 경우의 수를 구할 수 있게된다.
이 과정을 점화식으로 표현하면 아래와 같다. 여기서 PP(n,n)은 n개의 원소를 모두 나열하는 순열의 경우의 수이고, P(n,r)은 r개의 원소를 선택해 나열하는 경우의 수이다.
- 이전에 도출한 공식에 따르면, P(n,n)=n! 이다. 따라서 이 식을 사용하여 다시 정리하면
- 따라서 P(n, r) 즉 n개의 원소 중 r개를 선택해 나열하는 경우의 수는 다음과 같다.
결과:
n개의 원소 중 r개를 선택해 나열하는 경우의 수는 전체 순열의 경우의 수에서 남은 원소를 나열하는 경우의 수를 나눈 것과 같다는 것을 알 수 있다.
중요 포인트: 일부 원소만 선택해 배열할 때는 n! 을 사용하여 비율을 계산한다. 선택하지 않은 원소들의 팩토리얼로 나눈다는 점을 기억해야 한다.
순열의 순서 ⬇️
순열(Permutation)은 N!로 계산되며, 각 자리에 원소를 배치하는 경우의 수이다. 이 방식은 알고리즘 설계에서 자주 사용된다..
문제의 정의:
순열은 N개의 숫자나 문자를 일렬로 배열하는 방법을 말한다. 즉, N개의 원소를 순서대로 나열하는 경우의 수를 구하는 문제이다. 이를 N! (팩토리얼)로 계산한다.
- N!: 예를 들어, 3개의 숫자 1, 2, 3을 배치하는 순열은 3! = 6가지가 있다.
정렬된 순열: 나열된 순열들을 영문 사전 순서처럼 정렬한다고 가정하자. 즉, 순서를 기준으로 각 순열이 사전식으로 정렬된다.
2. 문제 해결 방식:
순서 K가 주어지면, 그 순서에 해당하는 순열을 구하는 문제이다.
- 예를 들어, 3개의 숫자 1, 2, 3의 4번째 순서에 해당하는 순열은 2 3 1이다.
또는 임의로 주어진 순열의 정렬된 순서를 구하는 문제이다.
- 예를 들어, 2 3 1이라는 순열이 있을 때, 이 순열이 사전 순서로 몇 번째인지 구하는 문제이다.
3. 문제의 예시: 3자리 숫자
- 3자리 숫자 1, 2, 3을 일렬로 나열한 순열들은 위의 이미지와 같다.
자릿수에 따른 순열의 순서 ⬇️
자릿수에 따른 순열의 순서를 계산하는 방법을 알아보자. 각 자릿수의 가능한 순서와 그에 따른 재귀적 계산 과정을 통해 특정 순열이 사전 순서에서 몇 번째에 해당하는지를 구하는 방식을 보여주고 있다.
순열의 순서 구하기 공식:
cnt2: 3번째 자리에 올 수 있는 숫자의 순서
cnt1: 2번째 자리에 올 수 있는 숫자의 순서
3!, 2!, 1!의 계수는 해당 자릿수의 경우의 수를 나타낸다.
계산은 위에 올려져있는 숫자를 그대로 대입하면 된다.
순서에 따른 순열 구하기 #1 ⬇️
주어진 K번째 순열을 어떻게 구할 수 있을까? 이 과정은 사전순 순열 문제에서 K번째 순열을 빠르게 찾아내기 위한 방식인데 각 자릿수의 경우의 수를 배수(cnt)로 계산하여 K번째 순열을 효율적으로 찾아낸다. 이러한 K번째 순열을 찾는 문제는 재귀적 사로를 필요로한다.
아래의 설명은 순서를 출력하는 방법을 간단한 단계로 개념적 설명하고 있다.
주어진 값(K)과 현재 자리(N)에서 만들 수 있는 경우의 수를 비교
N - 1 자리에 올 수 있는 가능한 경우의 수를 계산하고, 이 경우의 수가 주어진 K와 비교된다.
- 이때, 가능한 경우의 수는 각 자리의 원소들이 나머지 자리에 배치되는 순열의 수를 의미한다.
2. 경우의 수를 배수(cnt)로 증가시킴
1번 과정에서 K가 더 작아질 때까지 순열의 순서를 1씩 늘리면서 가능한 경우의 수를 배수(cnt)로 증가시킨다.
- 이 과정은 K번째 순열을 결정하기 위한 반복 과정이다.
3. K가 더 작아지면 순열에 값을 저장하고, K 값을 업데이트
- K가 더 작아지면 현재 순열에 그 값을 저장하고, K에서 (경우의 수 × (cnt - 1))를 빼서 K 값을 업데이트한다. 이를 통해 다음 자리에 올 원소를 결정한다.
4. 순열이 완성될 때까지 1~3 단계를 반복
- 이 과정을 순열이 완성될 때까지 반복한다. 각 자리에 올 수 있는 값들을 계산하여 K번째 순열을 구한다.
순서에 따른 순열 구하기 #2 ⬇️
이제 실제 예시를 들어 더 구체적인 순서로 K값을 사용해 순열을 결정하는 과정을 알아보자. 아래의 이미지는 자리별 숫자 배정 과정을 보여주고 마지막 이미지는 K값을 갱신하며 정확한 순열을 찾는 과정을 설명하고있다. 이 두 과정은 동시에 이루어진다. 즉 K값을 사용하여 각 자리에 올 수 있는 숫자를 선택하고, 선택된 숫자에 따라 K값을 갱신하며, 이를 반복해서 최종적인 순열을 구하는 방식이다.
첫 번째 이미지 설명 (순열 자리에 숫자 배정 과정):
단계 1: 첫 번째 자리 결정
첫 번째 자리에서 남은 숫자 중 K값이 포함된 숫자를 결정다.
주어진 K값이 6 × 1 보다 작기 때문에 첫 번째 자리에 1이 배치된다.
- K값을 갱신할 필요가 없다.
단계 2: 두 번째 자리 결정
남은 숫자 중에서 두 번째 자리에 들어갈 수 있는 숫자 3이 결정다.
K(3) > 2×2를 만족하는 조건에 따라 3이 배치된다.
K값은 K = K − (2×(2−1)) = 1로 갱신된다.
단계 3: 세 번째 자리 결정
남은 숫자 중에서 세 번째 자리에 들어갈 수 있는 숫자 2가 결정된다.
- 현재 자리에서 K값을 갱신할 필요가 없다.
단계 4: 마지막 자리
- 마지막 자리에 남은 숫자 4가 배치됩니다.
최종 순열: 1 3 2 4
두 번째 이미지 설명 (K값 갱신 과정):
단계 1: 첫 번째 자리 계산
첫 번째 자리에 올 수 있는 숫자 중에서 1이 선택됩니다.
- K값은 변경되지 않으며, K=1K = 1K=1로 그대로 유지됩니다.
단계 2: 두 번째 자리 계산
두 번째 자리에 올 수 있는 숫자 중에서 3이 선택됩니다.
남은 미사용 숫자 중 2가 존재하며, K값이 이에 해당합니다.
K값은 K=K+2×F[2]=3K = K + 2 \times F[2] = 3K=K+2×F[2]=3으로 갱신됩니다.
단계 3: 세 번째 자리 계산
세 번째 자리에 올 수 있는 숫자 2가 선택됩니다.
- K값은 갱신되지 않으며, K=3K = 3K=3로 유지됩니다.
최종 순열: 1 3 2 4
순서에 따른 순열 구하기 의사코드 ⬇️
이 코드는 주어진 순서에 해당하는 순열을 구하는 방법을 설명하고 있다. 예를 들어, N개의 숫자로 만들 수 있는 순열에서 "k번째" 순열을 알고 싶을 때 이 방법을 사용할 수 있다. 즉, 주어진 순서가 몇 번째 순열인지 그 순열 자체를 구하는 방식이다.
자리마다 미사용 숫자를 확인하고, cnt 값을 이용해 K값을 업데이트하면서 원하는 순열을 찾아낸다.
이 과정은 자리별로 가능한 숫자를 효율적으로 선택하여 K번째 순열을 구할 수 있게 해준다.
1. F 리스트 초기화 (팩토리얼 값 저장):
F 리스트는 각 자리에서 만들 수 있는 경우의 수를 저장하기 위한 리스트이다.
각 자리별로 팩토리얼 값을 계산해서 리스트에 저장하는데, 이는 해당 자리에서 만들 수 있는 순열의 개수를 나타낸다.
- 예: F[1]=1!F[1] = 1! 등으로 리스트가 채워진다.
2. 입력값 처리 (inputList):
- inputList[0] == 1 인 경우, K번째 순열을 출력하는 문제를 다룬다. 이때, K번째 순열을 구하기 위한 입력을 받는다.
3. N만큼 반복 (자리별 순열 계산):
자리마다 가능한 순열을 계산하고, 현재 순서에서 그 자리에 배치될 수 있는 숫자를 찾아낸다.
cnt 값은 각 자리마다 남은 미사용 숫자를 이용해 배치할 수 있는 숫자를 정하는 데 사용된다.
4. cnt 값 비교 후 K값 갱신:
각 자리마다 배치될 수 있는 순열의 개수를 계산한 후, 현재의 K값과 비교하여 그 자리에 어떤 숫자가 들어갈지를 결정한다.
cnt 값이 현재 순열에 포함되면, 그 값을 선택하고 K값을 갱신한다.
- 이미 사용된 숫자는 체크하고 그 자리는 넘어간다.
5. 결과 출력 (S 리스트 출력):
- S 리스트에 각 자리마다 선택된 숫자를 저장하여, 최종적으로 K번째 순열을 구해낸다. 마지막에는 완성된 순열을 출력한다.
주어진 순열의 순서 구하기 의사코드 ⬇️
이 알고리즘을 쉽게 이해하기 위해 마라톤 경주를 예로 들어보자. 만약 10명의 마라톤 선수가 있을 때, 내가 특정 선수가 몇 번째로 도착했는지 알고 싶다고 생각해보면, 첫 번째 선수가 몇 번째로 도착했는지, 두 번째 선수가 몇 번째로 도착했는지 등을 계속 계산하면서 내가 목표로 하는 선수가 몇 번째로 도착했는지 확인하는 과정이라고 보면 된다. 이 방식은 자리마다 가능한 경우의 수를 계산해서 특정 순열이 전체 순열 중 몇 번째인지 계산하는 것이다.
이 코드는 특정 순열이 전체 순열에서 몇 번째인지 계산하는 방법을 설명하고 있다. 즉 이미 정해진 순열이 전체에서 몇 번째 인지 계산하는 방식이다. 순열의 순서를 계산하려면 팩토리얼과 같은 개념을 사용한다. 각 자리가 결정되면 나머지 자리에 들어갈 수 있는 숫자의 경우의 수를 계산해서 순서를 찾을 수 있다.
주어진 자리에서 가능한 경우의 수 계산:
현재 순서에서 해당 자리에 어떤 숫자가 올 수 있는지 계산한다. 예를 들어, 첫 번째 자리에 숫자가 올 수 있는 경우의 수는 남은 숫자들의 순열을 계산한 결과이다.
S리스트에 저장된 숫자가 현재 자리에 올 수 있는지를 체크한다.
자리별로 계산 반복:
- 매 자리마다 그 자리에 올 수 있는 숫자를 결정하고, 그 후에 남은 숫자들로 만들 수 있는 순열의 개수를 계산한다.
이미 사용한 숫자는 제외:
- 사용된 숫자는 다시 사용할 수 없기 때문에, 그 숫자를 사용했다고 표시해야 한다.
최종 순서 계산:
- 각 자리에서의 계산을 반복한 후, 최종적으로 순서를 구하고 결과를 출력한다.
cnt: 현재 순서를 계산하기 위한 변수.
for loop: 각 자리에 올 수 있는 숫자를 차례로 확인하면서, 가능한 순열의 개수를 계산하는 역할
inputList: 이미 사용한 숫자를 확인하고, 사용되지 않은 숫자만 가지고 순서를 계산한다.
조합의 개념 ⬇️
💡키워드: C(n,r) nCr, 𝐶 𝑛, 𝑟 = 𝐶 𝑛 − 1, 𝑟 + 𝐶(𝑛 − 1, 𝑟 − 1) 파스칼의 삼각형(Pascal's triangle), 동적 계획법, 이항계수
- 서로 다른 n개의 원소들을 순서를 고려하지 않고 r개를 선택하는 것을 조합이라고 한다. 즉, 선택된 원소들의 순서가 중요하지 않으며, 어떤 원소들이 선택되었는지만 중요하다.
조합의 수: 서로 다른 n개의 원소 중에서 r개를 선택하는 조합의 경우의 수는 C(n,r) 또는 nCr로 나타낸다. 원소들을 선택할 때 순서를 고려하지 않기 때문에 순열(P(n, r) 또는 nPr) 과는 다른 방식으로 계산된다.
조합의 예시⬇️
주어진 5개의 숫자(1, 2, 3, 4, 5) 중에서 3개의 숫자를 선택하는 경우이다.
이때 순서 없이 선택하기 때문에, 2, 4, 5를 선택했을 때 2-4-5, 4-2-5, 5-4-2 모두 동일한 조합으로 취급된다. 순서는 중요하지 않으며, 어떤 숫자들이 선택되었는지만 중요하다.
조합에서는 선택된 원소들의 순서가 중요하지 않다는 점이 핵심이다. 이와 달리, 순열은 원소의 순서가 중요하다는 차이점이 있다.
이와 같은 조합 개념은 확률 이론, 통계적 분석에서 자주 사용된다.
조합의 공식⬇️
n개의 원소 중에서 순서 없이 r개의 원소를 선택하는 것을 조합이라고 한다. 이를 C(n,r)로 나타낸다.
선택한 r개의 원소를 일렬로 배열하는 것은 순열과 관련된 문제로, 이는 P(r,r) 또는 P(n,r)로 나타낸다.
공식 유도:
- 조합과 순열의 관계:
이는 조합으로 선택한 r개의 원소를 순서를 고려하지 않고 선택한 후, 선택된 원소들을 순서대로 배열하는 과정을 설명하고 있다.
- 순열에서 조합 유도:
여기서 조합에 선택된 원소를 순서대로 배열하는 경우의 수를 계산할 때, 순열의 계산법을 사용한다.
- 조합 공식: 위 식을 C(n,r)에 대해 정리하면
즉, n개의 원소 중 r개를 순서 없이 선택하는 경우의 수는 전체 팩토리얼을 선택한 r개의 원소의 팩토리얼과 나머지 원소들의 팩토리얼로 나눈 값으로 구할 수 있다.
결론적으로 조합 공식은 선택한 원소들의 순서를 고려하지 않기 때문에, 순열과 달리 r!로 나누는 과정이 포함된다. 조합의 공식은 확률, 통계, 그리고 알고리즘 설계에서 매우 중요한 도구이다. 여러 가지 선택과 배열의 경우의 수를 계산할 때 필수적으로 사용되는데 실생활에서는 로또 번호를 선택하거나 팀 구성에서 멤버를 고르는 문제 등을 해결할때 유용할 수 있다.
중요: 조합의 점화식 ⬇️
조합의 점화식은 n개의 원소 중에서 r개를 선택하는 문제를 두 가지 선택으로 나누어 해결할 수 있다는 개념을 기반으로 한다.
과정 설명:
n개의 원소 중에서 하나를 선택하는 경우와 하나를 선택하지 않는 경우로 나누어 생각할 수 있다.
이때, 하나의 원소를 선택한 후 남은 n−1개의 원소 중에서 r−1 개의 원소를 선택하는 경우와, 하나의 원소를 선택하지 않고 남은 n−1 개의 원소 중에서 r개의 원소를 선택하는 경우의 수를 더하면 전체 경우의 수가 된다.
공식 유도:
- 이를 점화식으로 표현하면
즉, 하나를 선택하고 나머지를 고르는 경우와, 하나를 선택하지 않고 나머지를 고르는 경우의 수를 합한 것이 전체 경우의 수가 된다는 뜻이다.
특수한 경우, n개의 원소 중에서 모두 선택하는 경우 또는 아무것도 선택하지 않는 경우는 선택할 방법이 하나밖에 없기 때문에 n개 중 n개를 모두 선택하는 경우, n개 중 0개를 선택하는 경우, 1개 중 1개를 선택하는 경우의 수는 한 가지므로
결과적으로 조합의 점화식은 작은 문제로 쪼개서 해결하는 재귀적 접근 방식이다. 이는 매우 효율적이며, 동적 계획법에서 메모이제이션을 통해 계산을 최적화 할 때 많이 사용한다. 특히, 이 공식은 파스칼의 삼각형을 통해 그래픽적으로도 쉽게 확인할 수 있다. 각 값은 그 위의 두 값의 합으로 구해지는 구조이다.
이항계수(Binomial Coefficient) ⬇️
조합을 배우면서 이항계수가 갑자기 등장한 이유는, 이항계수가 조합의 수를 나타내는 중요한 방식이기 때문이다. 이항계수와 조합은 사실 같은 개념을 다르게 표현한 것이다.
쉽게 설명하자면 조합은 n개의 원소 중에서 r개를 순서 없이 선택하는 경우의 수를 구하는 방식이다. 이 조합의 수는 공식으로 C(n,r)로 나타낼 수 있다. 이항계수는 조합의 수를 나타내는 수학적 표현이다. 즉
위의 공식은 조합의 경우를 나타내는 수학적 공식과 동일하다.
이항정리는 (a+b)^n 같은 식을 전개할 때 나오는 식을 뜻한다. 이때, 각 항의 계수를 구하는 데 필요한 값이 바로 이항계수이다. 이항정리에서 이항계수는 각각의 항이 얼마나 많이 나타나는지를 조합 방식으로 계산하는 것이기 때문에, 조합의 개념이 필요하다.
C(n,r)은 이항계수이다. 이는 n개의 항 중에서 r개의 항을 선택하는 조합의 수를 나타 낸다.
a^n-r 과 b^r은 각각의 항에 해당하는 변수들이 조합되는 방식이다.
(a + b)² = a² + 2ab + b² 에서 2ab 앞의 2가 이항계수이다. 이는 a와 b가 한 번씩 등장하는 조합의 수를 의미한다.
파스칼의 삼각형(Pascal’s Triangle) ⬇️
파스칼의 삼각형은 조합을 시각적으로 표현한 것으로, 이를 통해 이항계수 및 조합의 관계를 쉽게 이해할 수 있도록 도와준다.
파스칼의 삼각형 구조:
파스칼의 삼각형은 숫자들을 삼각형 형태로 배열한 도형이다. 각 숫자는 그 위쪽의 두 숫자의 합으로 구할 수 있다
이를 수식으로 나타내면: C(n,r) = C(n−1, r−1) + C(n−1,r) 이는 조합의 점화식 𝐶 𝑛, 𝑟 = 𝐶 𝑛 − 1, 𝑟 + 𝐶(𝑛 − 1, 𝑟 − 1)과 동일하다. 즉, n번째 행의 r번째 값은 그 위쪽 n−1 번째 행에서 왼쪽 대각선 값과 바로 위에 있는 값의 합이다.
숫자의 의미:
파스칼의 삼각형에서 각 숫자는 이항계수(Binomial Coefficient)에 해당한다. 예를 들어, 삼각형의 5번째 행은 (a+b)^5 의 전개에서 각 항의 계수를 나타낸다.
예를들어: C(5,2) = 10 이 값은 (a+b)^5를 전개할때 a³b²항 앞에 붙는 계수이다.
시각적 특징:
- 삼각형의 가장자리에는 항상 1이 나타나며, 중간 숫자는 위쪽의 두 숫자의 합으로 결정된다. 예를 들어, 15는 5와 10을 더해서 나온다.
이항계수 - 파스칼의 삼각형을 동적계획법에 적용 1 ⬇️
아래 테이블은 동적 계획법 (Dynamic Programming, DP)을 사용하여 이항계수 C(n, k)를 계산하는 과정을 시각적으로 나타내고 있다. 또한 DP 테이블은 메모이제이션의 일종으로, 각 계산된 값을 테이블에 저장하고 이를 재사용하는 방식이다. 소프트웨어 엔지니어는 이러한 방식으로 알고리즘을 최적화하고 성능을 향상시키는 방법을 습득해야 한다.
동적 계획법은 이전 계산 결과를 저장하여 중복 계산을 피하기 때문에 시간 복잡도가 크게 줄어든다. 테이블을 사용하기 때문에 작은 문제의 해를 저장하고 재사용하므로 큰 문제도 효율적으로 해결이 가능하다.
DP 테이블 설명:
N: 총 개수 (총 원소의 수), k: 선택된 원소의 수.
이 테이블의 각 셀 D[N][k] 는 N개의 원소 중 k개의 원소를 선택하는 경우의 수, 즉 이항계수 C(N, k) 를 나타낸다.
DP 테이블 구조:
첫 번째 열의 값은 모두 1이다. 이는 원소를 0개 선택하는 경우의 수가 항상 1이기 때문이다.
첫 번째 행은 1 뒤에 0이 채워져 있다. 이는 원소의 수보다 선택할 수 있는 수가 클 수 없기 때문이다.
대각선에 있는 값은 1이다. 이는 N개의 원소 중 N개를 모두 선택하는 경우의 수는 항상 1이기 때문이다.
DP 테이블 채우기:
- 점화식 𝐷[𝑖][𝑗] = 𝐷[𝑖− 1] [𝑗] + 𝐷[𝑖− 1] [𝑗−1]을 사용하여 테이블을 채운다. 즉, 현재 셀 D[i] [j]는 바로 위의 셀과 왼쪽 위의 셀의 합으로 계산된다.
이항계수 - 파스칼의 삼각형을 동적계획법에 적용 2 ⬇️
점화식 (Recurrence Relation)을 사용하여 동적 계획법 (Dynamic Programming, DP) 테이블을 채우는 방법을 살펴보자. 테이블의 각 셀은 이항계수 (Binomial Coefficients)를 나타내며, 이 값들은 파스칼의 삼각형 구조를 따른다.
조합 점화식 수식: D[i] [j] = D [i−1] [j] + D [i−1] [j−1]
위의 수식은 파스칼의 삼각형에서 사용되는 점화식이다.
D[i] [j]는 i개의 원소 중에서 j개의 원소를 선택하는 경우의 수이다.
D[i-1] [j]는 i-1개의 원소 중에서 j개의 원소를 선택하는 경우이다 (즉, i번째 원소를 선택하지 않는 경우).
D[i-1] [j-1]는 i-1개의 원소 중에서 j-1개의 원소를 선택하는 경우 (즉, i번째 원소를 선택하는 경우).
이 수식은 삼각형에서 한 값이 바로 위 두 값의 합으로 이루어진다는 원리를 나타내고 있다.
예시: 𝐷 [ 4 ] [ 2 ] 의 값을 계산하려면 n번째 원소를 선택하지 않는 경우인 𝐷 [ 3 ] [ 2 ] 와 n번째 원소를 선택하는 경우인 𝐷 [ 3 ] [ 1 ] 의 값을 더해야 한다. D[4][2] = D[3][2] + D[3][1] 즉 결과는 3 + 3 =6이 된다.
D[4][2]는 4개의 원소 중에서 2개를 선택하는 경우의 수를 의미한다.
이 값을 구하려면 D[3][2]와 D[3][1]을 더해야 합니다. 즉: D[4][2]=D[3][2]+D[3][1]
D[3][2]는 3개의 원소 중 2개를 선택하는 경우로 3이고, D[3][1]은 3개의 원소 중 1개를 선택하는 경우로 3이다. 따라서, D[4][2] = 3 + 3 = 6이 된다.
3 + 3 = 6은, 3개의 원소 중에서 2개 또는 1개를 선택하는 조합의 수를 더한 값이다.
테이블 구조:
테이블에서 i는 총 개수를, j는 선택된 개수를 나타낸다.
각 셀의 값은 파스칼의 삼각형의 원리를 따라 계산되며, 초기값으로 테이블 가장자리에 1이 채워진다.
예를 들어, D[5][2]는 10으로, 이는 5개의 항목 중 2개를 선택하는 조합의 수를 나타낸다. D[5][2] = D[4] [2] + D[4] [1] 즉 6 + 4 = 10
이항계수 - 파스칼의 삼각형을 동적계획법에 적용 3 ⬇️
DP 테이블을 계산하기 위해 필요한 초기화 과정(Initialization of DP Table)을 알아보자. 동적 계획법(Dynamic Programming)을 사용할 때, 기본값을 먼저 설정한 후 점화식을 통해 값을 채우는 것이 중요하다. 이 과정에서 테이블의 특정 위치를 미리 초기화해야 한다.
D[i] [1] = i
- i개의 원소 중에서 1개를 뽑는 경우는 항상 i가지이다. 예를 들어, 3개의 원소 중 1개를 뽑는 경우는 3가지이기 때문에 D[3][1]=3이 된다.
D[i] [0] = 1
- 어떤 원소도 선택하지 않는 경우의 수는 항상 1이다. 즉, i개의 원소 중 0개를 선택하는 경우는 1가지 방법밖에 없다. 예를 들어, 5개의 원소 중 0개를 선택하는 경우는 1이므로 D[5][0]=1 이다.
D[i] [i] = 1
- i개의 원소 중에서 모두를 선택하는 경우도 항상 1가지이다. 예를 들어, 4개의 원소 중 4개 모두를 선택하는 경우는 한 가지 방법밖에 없기 때문에 D[4][4]=1 이다.
💡소프트웨어 엔지니어로서 알아야 할 중요한 부분:
- DP 테이블 초기화는 동적 계획법에서 매우 중요한 단계로, 경계 조건을 설정하는 작업이다. 소프트웨어 엔지니어로써 경계 조건을 정확하게 설정한 후, 점화식에 따라 나머지 값을 계산하는 방식으로 문제를 해결할 수 있다.
이항계수 구하기 의사코드 ⬇️
목표: N개의 원소 중에서 K개의 원소를 선택하는 경우의 수, 즉 이항계수를 계산하는 것. 이를 위해 DP 테이블을 활용하여 점진적으로 값을 구할 수 있다.
변수 설정:
N: 총 개수 (원소의 수).
K: 선택된 원소의 수.
D: 이항계수를 저장할 DP 리스트.
초기화 단계:
첫 번째 반복문에서 DP 테이블을 초기화한다.
D[i] [1] = i: i개에서 1개를 선택하는 경우의 수는 항상 i이다.
D[i] [0] = 1: i개에서 아무것도 선택하지 않는 경우의 수는 항상 1입이다
D[i] [i] = 1: iii개에서 모두 선택하는 경우의 수도 항상 1이다.
DP 테이블 채우기:
두 번째 반복문에서 실제로 점화식을 사용해 값을 계산한다.
D[i-1] [j]: i−1개의 원소 중에서 j개의 원소를 선택하는 경우의 수 (현재 원소를 선택하지 않은 경우).
D[i-1] [j-1]: i−1 개의 원소 중에서 j-1개의 원소를 선택하는 경우의 수 (현재 원소를 선택한 경우).
결과 출력: 최종적으로 D[N][K]는 N개의 원소 중 K개의 원소를 선택하는 경우의 수, 즉 이항계수가 된다.
이항계수 구하기 파이썬 코드 ⬇️
입력 처리
input = sys.stdin.readline
N, K = map(int, input().split())
N: 총 원소의 개수, K: 선택할 원소의 개수
사용자로부터 N과 K를 입력받아 이항계수를 계산한다.
DP 테이블 초기화
D = [[0 for j in range(N+1)] for i in range(N+1)]
D 테이블은 이항계수를 저장할 2차원 리스트이다.
크기는 N+1 × N + 1로 설정한다. N + 1을 사용하는 이유는 0부터 N까지의 값을 포함하기 위해서이다.
초기값 설정 (위에서 자세히 설명)
for i in range(0, N+1):
D[i][1] = i
D[i][0] = 1
D[i][i] = 1
4. 이항계수 계산 (동적 계획법 적용)
for i in range(2, N+1):
for j in range(1, i):
D[i][j] = D[i-1][j] + D[i-1][j-1] # 조합의 기본 점화식
점화식: D[i] [j] = D[i−1] [j] + D[i−1] [j−1]
D[i-1][j]: i−1개의 원소 중에서 j개를 선택하는 경우
D[i-1] [j-1]: i−1개의 원소 중에서 j-1개를 선택하고 i번째 원소를 추가하는 경우
이를 통해 현재 D[i] [j] 값을 구한다.
5. 결과 출력
print(D[N][K])
- 최종적으로 D[N][K] 값을 출력한다. 이는 N개의 원소 중 K개를 선택하는 이항계수를 의미한다.
💡소프트웨어 엔지니어로서 파스칼의 삼각형을 통해 알아야 할 중요한 부분:
재귀적 사고(recursive thinking): 파스칼의 삼각형은 재귀적인 구조를 가지고 있다. 각 값은 위쪽 두 값의 합으로 계산되는데 여기서 재귀적 사고란 문제를 작은 하위 문제들로 반복적으로 쪼개서 해결하는 사고 방식을 의미한다. 즉, 자기 자신을 반복적으로 호출하는 구조를 통해 문제를 해결하려고 하는 방식이다.
점화식의 활용 능력(Ability to apply recurrence relations): 이항계수는 점화식을 사용하여 계산하는데 점화식은 문제의 재귀적인 관계를 나타내는 수학적 공식이다. 즉, 큰 문제를 작은 문제로 나누는 규칙을 공식으로 표현한 것을 뜻한다. 파스칼의 삼각형은 C(n, k) = C(n−1, k−1) + C(n−1, k) 이렇게 표현이 가능하다. 참고로 이와 같은 점화식을 기반으로 한 문제는 컴퓨터 알고리즘에서 매우 흔하다.
동적 계획법을 활용한 문제 최적화 방법: 파스칼의 삼각형은 동적 계획법(DP)의 대표적인 예시이다. 큰 문제를 작은 하위 문제로 쪼개고, 그 결과를 저장해 재사용하는 동적 계획법 방식으로 효율성을 높이기 때문이다. 파스칼의 삼각형에서, 위쪽에서 계산된 값들을 저장해 두고, 이를 재사용해 다음 값을 계산하는 방식은 메모이제이션(Memoization)과 동일하다.
조합과 이항계수의 다양한 응용: 확률 계산, 경우의 수 계산, 백트래킹 알고리즘, 최적화 문제 등에서 조합의 개념은 필수적이다. 조합을 이용해 다양한 경우의 수를 계산할 수 있으며, 이는 컴퓨터 과학에서 데이터 처리, 알고리즘 설계, 경로 탐색 문제 등 여러 문제 해결에 핵심적으로 사용된다.
수학적 도구로써의 활용: 파스칼의 삼각형은 알고리즘 설계 외에도 확률과 통계, 그래프 이론, 네트워크 분석 등에서도 활용된다. 예를 들어, 확률적 모델에서 사건의 조합을 계산하거나, 빅데이터 분석에서 조합을 이용한 선택 문제를 해결할 때 이항계수는 중요한 역할을 한다.
선택 알고리즘 요약
정수론 요약
순열과 조합 요약
