---

⚡ Computional Thinking

---

💡 약하다고 생각한 부분을 다시 한번 짚고 넘어가는 시간

📌 집합과 조합론

🔷 두 집합 A와 B에 대해 A가 B의 부분 집합임을 증명한다는 것은 A의 임의의 원소가 B에 포함됨을 보이는 것과 같다.

• 모든 4의 배수는 2의 배수다. -> 4k = 2(2k)

🔷 조합론

• 경우의 수를 따지는 문제들

• 개수는 C를 이용하여 표현하기도 하지만 괄호 표현을 더 많이 쓴다.

  💡 순열: nPk = n! / (n-k)!

  💡 조합: nCk = n! / ((n-k)! * k!)

📌 재귀

🔷 재귀식들을 O() notation 수준으로 풀기

1. T(n) = T(n-1) + 1, T(0) = 1

O(n)

2. T(n) = T(n-1) + n, T(0) = 1

O(n^2)

3. T(n) = T(n-1) + logn, T(0) = 1

O(nlogn)

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

O(logn)

🔷 재귀는 자기 자신을 호출하는 함수이다.

• 함수는 입력이 있으며, 자기 자신의 입력과 동일한 입력으로 자기 자신을 호출하면 당연히 끝나지 않는다.
• 기저조건에 신경을 잘 쓰도록 하자.

함수란 어떤 문제를 해결하는 방법을 코딩한 것

• 함수가 어떤 문제의 단 한 케이스만을 해결하는 것이 아니다.
• 제대로 코딩되었다면 해결하는 문제의 모든 케이스들을 해결해야 한다.

💡 다르게 생각하기!
어떤 문제를 해결하려다 부분 문제를 만났는데, 원래 해결하려던 입력 케이스와 동일한 문제에 속하지만 "크기가 더 작은" 입력 케이스를 해결하는 것이 그 부분 문제였다. 즉, 부분 문제가 동일한 문제인 경우!