코딩테스트 볼 때 참고 자료

알고리즘 문제를 풀 때, 수학적으로는 생각이 나는데 코드로 생각이 안날 때! 참고하면서 익히려고 적는 글입니다.

계속 추가될 예정입니다!

---

Factorial(!)

• 수학적 정의: 자연수의 계승 또는 팩토리얼은 그 수보다 작거나 같은 모든 양의 정수의 곱이다.
• 수식: 

팩토리얼 공식

func factorial(_ n: Int) -> Int {
  var n = n
  var result = 1
  while n > 1 {
    result *= n
    n -= 1
  }
  return result
}

*👩🏻‍🏫 : 재귀로도 작성해보자.

func factorialRecursion(_ n: Int) -> Int {
if n==0 { return 1 }
return n * factorialRecursion(n - 1)
}

순열(Permutation)

• 수학적 정의: 순열 또는 치환은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다.
  -> 서로다른 n개 중에 r개를 선택하는 경우의 수(순서 상관 있음)
• 구현 방법: factorial 식을 응용하면 된다.
• 수식: 

// 순열 경우의 수의 count 구할 때
func permutations(_ n: Int, _ r: Int) -> Int {
  var n = n
  var answer = n
  for _ in 1..<r {
    n -= 1
    answer *= n
  }
  return answer
}

*👩🏻‍🏫 : 순열 경우의 수 리스트를 구해보자.

// 순열 생성하기, a배열에서 n번째 index까지의 순열 경우의 list를 print
// Niklaus Wirth의 재귀 알고리즘
func permuteWirth<T>(_ a: [T], _ n: Int) {
  if n == 0 {
    print(a)   // 현재 순열들을 print 해준다.
  } else {
    var a = a
    permuteWirth(a, n - 1)
    for i in 0..<n {
      a.swapAt(i, n)
      permuteWirth(a, n - 1)
      a.swapAt(i, n)
    }
  }
}

 

 

 

조합(Combination)

• 수학적 정의: 조합론에서 조합은 집합에서 서로 다른 n개의 원소 중에서 순서에 상관없이 r개를 선택하는 것이다.
  -> 서로 다른 n개 중에 r개를 선택하는 경우의 수(순서 상관 없음)
  -> 즉 순서와 상관없이 원소의 종류와 갯수가 같으면 같은 것으로 취급한다.
  (ex. [1,2,3] == [3,2,1] == [1,3,2])
• 구현 방법: 순열과 팩토리얼을 응용하면 된다.
• 수식: 

( *참고 : nCr = nPr / r! )

// 조합 공식에 순열이 포함되어있으므로, 다음과 같이 응용하면 된다.
func combinations(_ n: Int, choose k: Int) -> Int {
  return permutations(n, k) / factorial(k)
}

*👩🏻‍🏫 : 조금 더 큰 숫자에 대비해보자.

// 큰 숫자가 인자로 들어올 수도 있음을 대비한 위의 식보다 약간 빠르다.
func quickBinomialCoefficient(_ n: Int, choose k: Int) -> Int {
  var result = 1
  for i in 0..<k {
    result *= (n - i)
    result /= (i + 1)
  }
  return result
}

*👩🏻‍🏫 : 보다 더 큰 숫자에 대비해보자.

Dynamic Programming을 이용하여 팩토리얼과 나눗셈 계산의 필요성을 극복한 방법

• 원리: 파스칼의 삼각형에 기초함.

• 구현 방법: DP. 첫번째 loop에서 첫째줄 가장 바깥쪽 삼각형을 채운다.
                  다른 loop에서는 이전 줄로부터 추가된 두 숫자에 대해 계산해서 추가해 나가면 된다.

func binomialCoefficient(_ n: Int, choose k: Int) -> Int {
  var bc = Array(repeating: Array(repeating: 0, count: n + 1), count: n + 1)

  for i in 0...n {
    bc[i][0] = 1
    bc[i][i] = 1
  }

  if n > 0 {
    for i in 1...n {
      for j in 1..<i {
        bc[i][j] = bc[i - 1][j - 1] + bc[i - 1][j]
      }
    }
  }

  return bc[n][k]
}

 

*참조 링크

raywenderich/swift-algorithm-club : link

 

 

틀린부분이 있거나, 더 좋은 방법이 있다면 댓글로 남겨주세요! 
🌈댓글은 언제나 환영입니다🙏🏻