241226 SWEA 집합과 조합론

순열, 집합, 증명... 점점 더 수학적인 부분이 많아진다. 오늘도 정리해본다.

도중에 나오는 예시 혹은 문항은 SWEA의 문항임을 밝힌다.

 

1. 순열, 조합

n! = n * (n-1) * ... * 2 * 1

nPr = n! / (n - r)!

nCr = n! / r!(n - r)!

조합은 괄호로도 표현이 된다!

nC4 = (ⁿ₄) 이런식이긴 한데 텍스트로 입력할 수 있는지 모르겠다.

 

이 식은 "이항정리"라는 이론이라고 한다.

x^(n-k)*y^k 의 계수를 구하기 위한 식이며, 이는 nCk와 같다.

이를 귀납적으로 증명하기 위해서는 n=1일 때 성립함과, n=m인 경우 성립하면 n=m+1인 경우 성립한다는 것을 증명함으로써 가능하다.

또한, 해당 식에 x=1, y=1을 대입함으로써 부분집합의 개수가 2^n임을 알 수 있다.

 

참고 : 이항정리 - 나무위키

 

2. 집합

귀납법은 n=1, n=k, n=k+1일 경우를 증명해서 모든 단계에 대해 성립함을 증명하는 것.

귀류법은 해당 명제가 틀릴 경우 모순됨을 증명하여 명제가 옳음을 증명하는 방법.

 ( A - B ) ∩ ( B - A ) = ∅

해당 명제가 틀릴 경우, 공집합이 아니라 어떤 원소 x가 존재한다는 뜻이다.

x가 A에 존재하며, B에 존재하지 않는 원소인 경우, A-B에 존재하나 B-A에 존재하지 않기에 교집합에 존재하지 않음.

  ∃x (x∈A∧x ∉ B) ->  (x∈(A-B)∧x ∉ (B-A))

x가 A에 존재하지 않으며 B의 존재하는 원소인 경우, B-A에 존재하나 A-B에 존재하지 않기에 교집합에 존재하지 않음.

  ∃x (x ∉ A∧x∈B) -> (x ∉ (A-B)∧x∈(B-A))

x가 A에 존재하며 B에 존재하는 원소인 경우 A ∩ B에 존재함. 즉 A-B에도 B-A에도 존재하지 않기에 교집합에 존재하지 않음.

  ∃x (x∈A∧x∈B) -> (x ∉ (A-B)∧x ∉ (B-A))

x가 A에도 B에도 존재하지 않는다면, A-B에도 B-A에도 존재하지 않기에 교집합에 존재하지 않음.

  ∃x (x ∉ A∧x ∉ B) -> (x ∉ (A-B)∧x ∉ (B-A))

즉, 어떤 원소 x가 존재하지 않기에, 해당 명제는 옳다는 것이 증명됨.

 

3. 단사함수, 전사함수, 전단사함수

X 집합에 속하는 원소 a가 어떠한 수식 f(x)를 통해 Y집합에 속하는 원소 b가 되는걸 함수라고 이해하고 있다.

여기서, a와 b가 일대일로 대응하고 있다면 이걸 단사함수라고 한다.

모든 Y에 대응할 필요는 없다.

이를 증명하는 식은 f(x₁)=f(x₂)이면 x₁=x₂

단사함수의 예

 

그리고, 모든 Y에 대해 대응하고 있다면 (공역 = 치역) 이를 전사함수라고 한다.

원소 x₁과 x₂가 다르면서도 같은 함숫값 f(x₁)=f(x₂)을 가질 수 있다.

전사함수의 갯수를 구하기 위해서는 "스털링 수"를 사용할 필요가 있다고 한다.

S(m,n)으로 표기되며, 다음과 같이 재귀적으로 계산한다고 한다.

  S(m,n) = n * S(m-1,n) + S(m-1,n-1)

   : m개의 원소를 n개의 부분집합으로 나누는 방법의 가지수.

예를들어, X의 원소 개수가 5, Y의 원소 개수가 3인 전사함수의 개수를 구한다고 한다면,

  S(5,3) = 3 * S(4,3) + S(4,2) = 3 * 6 + 7 = 25

  S(4,3) = 3 * S(3,3) + S(3,2) = 3 * 1 + 3 = 6

  S(3,2) = 2 * S(2,2) + S(2,1) = 2 * 1 + 1 = 3

  S(4,2) = 2 * S(3,2) + S(3,1) = 2 * 3 + 1 = 7

즉, 25가지.

전사함수의 예

 

치역과 공역이 같고, 정의역과 공역의 원소 개수가 같은 경우 모든 원소가 일대일 대응이 되는 경우를 전단사함수라고 함.

이러한 경우, 역함수가 반드시 존재.

전단사함수의 예

 

원소가 m개인 집합에서 원소가 n개인 집합으로 가는 단사함수의 개수는 nPm가지가 된다.

(n개의 집합에서 m번 순서대로 선택하는 것과 같으므로)

 

4. 재귀함수와 빅오 표기법 (O() notation)

빅오 표기법도 생전 처음 듣는 용어였다.

시간 복잡도와 공간 복잡도를 "최악의 상황"으로 가정할 경우의 그래프를 나타낸 표기법이라고 한다.

한마디로 " 입력 크기가 커질수록 어떤 요소가 가장 큰 영향을 주는지를 파악하는 거"라고 한다.

핵심은 다음과 같다.

 

1) 가장 중요한 항만 남긴다 (차수가 높은 항)

 

• 작은 입력에서는 모든 항이 영향을 주지만, 큰 입력에서는 가장 빠르게 증가하는 항이 전체 성능을 지배하기 때문.
• 예: T(n) = 3n^2 + 2n + 5 → O(n^2)  (가장 큰 항만 남김)

2) 상수는 무시한다.

 

• 빅오 표기법은 크기의 성장률을 보기 때문에, 상수 계수는 영향을 주지 않습니다.
• 예: T(n) = 100n → O(n)

3) 입력 크기 n이 커질수록 성능을 표현한다.

 

대표적인 빅오 표기법은 다음과 같다.

 

• O(1): 상수 시간. 입력 크기에 상관없이 항상 일정한 시간이 걸립니다.
  • 예: 배열에서 첫 번째 원소를 가져오기.
• O(log⁡n): 로그 시간. 입력 크기가 커질수록 증가 속도가 느립니다.
  • 예: 이진 탐색.
• O(n): 선형 시간. 입력 크기에 비례해서 시간이 증가합니다.
  • 예: 배열의 모든 원소를 한 번씩 검사하기.
• O(n^2): 이차 시간. 입력이 커질수록 실행 시간이 제곱 비례로 증가합니다.
  • 예: 중첩된 루프에서 두 배열 비교하기.
• O(2^n): 지수 시간. 입력이 조금만 커져도 시간이 폭발적으로 증가합니다.
  • 예: 모든 가능한 부분 집합을 탐색하기.

참고 : ChatGPT

 

예시로, T(n) = T(n-1) + n 이라는 식을 빅오 표기법으로 표기하면,

  T(n) = T(n-1) + n

  T(n) = T(n-2) + (n-1) + n

  T(n) = T(n-3) + (n-2) + (n-1) + n

  T(n) = T(1) + 2 + 3 + ... + (n-2) + (n-1) + n

  T(1)은 초기 조건이므로 상수 c라고 하면, 2+3+...+(n-1)+n은 1+2+...+(n-1)+n - 1 로 표현할 수 있으며, 즉 (n(n+1)/2) -1 .

  결과적으로 T(n) = c + (n(n+1)/2) -1 이며, 가장 중요한 항만 남기고, 상수를 무시하면 다음과 같다.

  T(n) = O(n^2)

 

두번째로 T(n) = T(n/2) + 1 을 빅오 표기법으로 표기하면,

  T(n) = T(n/2) +1

  T(n/2) = T(n/4) + 1 = T(n/2) + 1 + 1

  T(n/4) = T(n/8) + 1 = T(n/4) + 1 + 1 = T(n/2) + 1 + 1 + 1

  T(n) = T(n/2^k) + k

  T(n/2^k)=T(1)이 되려면 2^k=n이어야 하며, 이는 log₂n=k로 나타낼 수 있음.

  즉 T(n) = T(1) + log₂n = O(log₂n)

 

5. 결론

이 후에도 몇 가지 문제들이 있었으나, 설명을 찾아봐도 잘 모르겠다. 특히 로그가 지수로 나오니까 아무리 봐도 알 수가 없어진다. 다음엔 로그 법칙을 더 알아봐야 할 것 같다.

그리고 계속해서 생각하는 점이지만, 텍스트로 수식을 적기가 쉽지 않다. 다음엔 수식 적는 법도 찾아서 깔끔하게 적어봐야겠다. 이 속도로 과연 입과 전까지 배워나갈 수 있을까 걱정이 되고 있다. 다른 사람들은 이런 문제들을 이미 많이 풀어봤을까? 문제를 보면 수식이 슈슈슉 하고 나오려나? 잘 따라갈 수 있도록 해야겠다.