🌈 [Section2] 7. 알고리즘 with Math

📕 오늘 배운 내용!

• 순열 (permutation)
• 조합 (Combination)
• 팩토리얼 (factorial)

---

✏️ 순열 (permutation)

순서에 상관 있게 요소 n개 중에 m개를 뽑는 경우의 수
nPr = n! / (n - r)!

• 순열의 모든 경우의 수를 나열할 경우
  ➜ 반복문 개수 (중첩반복문) == 요소를 뽑는 개수(r)
  ➜ 중복 요소는 제거
  (결과 변수에 넣기 전, 동일한 인덱스인지 검사하고, 동일하다면 넣지 않고 pass)

✔ 중복 순열 ( nπr )
순서 상관 있게 중복 가능한 n개중에서 r개를 선택하는 경우의 수
nπr = n^r

❗ 보통 방문 여부를 탐색하는 visited 메서드와 같은 템플릿을 사용 ( 검색해서 사용하기 )
[참고] https://velog.io/@jh129047/Java-permutation-library

✏️ 조합 (Combination)

순서에 상관없이 요소 n개 중에 m개를 뽑는 경우의 수
nCr = n! / (r! * (n - r)!)

• 조합의 모든 경우의 수를 나열할 경우
  ➜ 순열로 구할 수 있는 경우 찾기
  ( But, 한 번 조합한 요소는 다시 조합하지 않아야함 )
  ( Ex. 중접 for문을 사용할 때, 조건식의 i/j/k..는 i=0/j=i+1/k=j+1.. 이런 식)
  ➜ 순열로 구할 수 있는 경우에서 중복된 경우의 수를 나눔

✔ 중복 조합 ( nHr )
순서 상관 없이 중복 가능한 n개중에서 r개를 선택하는 경우의 수
nHr = n+r-1Cr

✔️ 순열과 조합의 한계점

• 뽑을 개수가 늘어나면 반복문의 수도 늘어남
• 뽑을 개수가 n개처럼 변수로 들어왔을 때 대응이 어려움
  ⠀
  ➜ 재귀를 사용하여 풀이하는 경우가 많음

---

✏️ n! (factorial, 팩토리얼)

n에서부터 1씩 감소하여 1까지의 모든 정수의 곱
n! = n(n-1)(n-2)(n-3)...1
( 0! 과 1!은 모두 1 )

---

✏️ 최대공약수

• 두개 이상의 수을 공통으로 나눌 수 있는 수들 중 가장 큰 것

✏️ 최소공배수

• 두개 이상의 수의 각각의 배수들 중 공통인 배수들 중 가장 작은 것

---

🌈 느낀점

오늘은 어려운 문제도 많았지만 그래도 페어님이 아이디어를 많이 내주셔서 영상으로 나와있는 문제를 제외하고 잘 푼 것 같다!
사실 같이 풀면서 5번 문제가 이해가 잘 안됐었는데 이 부분은 주말에 더 봐야할 것 같다!
그리고 요즘 조금식 나태해져가는 느낌을 받고 있어서 좀 더 노력해야할 것 같다.