→ 알고리즘 관련

Dynamic Programming 동적 프로그래밍, 다이나믹 프로그래밍, 동적 계회법으로 불리는 Dynamic Programming은 큰 문제를 작은 문제로 나누고 작은 문제의 답들을 이용해 원래 문제의 답을 찾는 방법이다. 주어진 문제를 최대한 많이 이용할 수 있는 작은 문제들로 나누는 게 핵심이라고 생각한다. (그래야 재사용이 많이 가능하고, 메모리를 적게 쓴다) Dynamic Programming 의 예시 피보나치수열 가장 쉬운 예로는 피보나치 수열이 있다. 피보나치수열은 아래와 같이 표현할 수 있다. f(0) = 1 f(1) = 1 f(n) = f(n-1) + f(n-2) when n > 1 만약 값을 재사용하지 않는다면...? 아래와 같이 5번째 값을 구하기 위해서는 15번의 연산이 필요하다...

반복문으로 순열 (Permuation) 구하기순열이란 n개의 원소에서 r 개를 뽑아 순서를 구분하여 나열한 경우 (nPr) 이다. 만약 r 이 정해져 있다면 아래처럼 r 번의 반복문으로 구할 수 있다. 3개를 뽑는 경우를 고려하여 3번 반복문을 사용하기 때문에 시간복잡도는 O(n^3) 이다.func permutations(_ array: [T]) -> [[T]] { var permutationArray: [[T]] = [] for i in 0..위의 코드의 단점위의 코드의 가장 큰 단점은 r 에 대해서 자유롭지 않다는 점이다. 4개를 뽑는다면 반복문을 하나더 넣어줘야 한다. 그렇기 때문에 재귀함수를 사용하여 r 에 대응할 수 있게 만들 수 있다. 재귀 함수를 활용하여 순열 (Permuation..

재귀 함수를 활용한 경우팩토리얼 구하기는 아마 재귀함수의 기본 중 기본이 아닐까... 생각해본다. 정수형 매개변수 n을 입력으로 받는다. 함수는 n이 0일 때 1을 반환하고, 그렇지 않은 경우에는 n에 n - 1을 곱한 값을 반환한다. 이러한 구조를 통해 팩토리얼을 재귀적으로 계산할 수 있다.func factorial(_ n: Int) -> Int { return n == 0 ? 1 : n * factorial(n - 1)} 재귀 함수에서의 주의사항재귀 함수를 사용할 때에는 종료 조건을 명확히 설정하는 것이 중요하다. 위의 코드에서는 n이 0일 때 1을 반환하여 재귀 호출이 멈추도록 만든다. 이를 통해 함수가 무한히 호출되는 것을 방지하고, 올바른 결과를 반환할 수 있다. 재귀 함수를 활용하지 않는..

진수 변환스위프트 안에서 2진수를 10진수로 10진수를 2진수로... 그 외에도 다양한 진수를 쉽게 바꿀 수 있는 함수가 있다. 은연중에 나는 Int("123") 이런식으로 넣어주면 자동으로 Int 로 변환되어 나와서 별 생각 없이 사용하고 있었는데 이것은 사실 10진법으로 전환해주는 로직이였다. 10진수를 n진수로 바꾸기999999를 2진수, 16진수로 바꾸고 싶다면?let v = 999_999print(String(v, radix: 2))// Prints "11110100001000111111"print(String(v, radix: 16))// Prints "f423f"print(String(v, radix: 16, uppercase: true))// Prints "F423F" n진수를 10진수로 ..

유클리드 호제법이란? 드디어 알고리즘을 공부하다가 처음 마주한 녀석이다. 두 양의 정수 최대공약수를 구하는 방법으로 유클리드 알고리즘이 있다. 아래의 설명이 가장 이해하기 쉬운것 같아서 가져왔다. Swift로 구현하기 최대공약수를 영어로 하면 Greatest Common Divisor 이기 때문에 보통 GCD 라 한다. 결과값이 나올때까지 자기자신을 계속 사용하는 재귀함수를 구현하여 구할 수 있다. a > b 일 경우 a = bq + r 이기 때문에 r 을 a % b 로 구할 수 있어 반복이 가능하다. 만약 여기서 a < b 일 경우에도 b 가 0 이 되지 않기 때문에 결국 a < b 일 경우 gcd(a, b) = gcd(b, a) 로 결국 가기 때문에 고려할 필요가 없다. func gcd(_ a: In..