→ 알고리즘 관련

컴퓨터 알고리즘을 공부하다 보면 시간복잡도에 대해서 당연히 많이 마주하게 되고, 보통은 O(n)처럼 Big-O 표기법을 사용한다. 하지만 시간 복잡도를 나타내는 방법에는 위 세 가지가 있다는 것을 알게 되었다. 이를 간단하게 정리해보려고 한다. 시간복잡도 간단하게 시간복잡도를 살펴보면 아래와 같이 정수 n을 받으면 0부터 n까지 더해주는 함수가 있다고 해보자. func solution(n: Int) -> Int { var result = 0 for i in 0..

힙(Heap) 이란? 힙은 최댓값 혹은 최솟값을 찾아내는 연산을 빠르게 하기 위해 이진트리를 기본으로 하는 자료구조이다. 구조는 자식노드, 부모노드로 구성이 되어있는데 직관적으로 알 수 있겠지만...(?) 삼각형으로 생각한다면 위 꼭짓점이 부모노드, 아래 두 꼭짓점에 위치한 노드가 자식노드라고 할 수 있다. 부모노드의 키값이 자식노드의 키 값보다 항상 큰 힙을 최대 힙, 부모노드의 키 값이 자식노드의 키 값보다 항상 작은 힙을 최소 힙이라고 부른다. 이 두 조건만 만족하게 된다면 숫자의 크기에 따른 순서는 상관이 없다.(예를 들면, 아래의 그림에서 보듯이 20이 느낌상 맨끝에 있어야 할 것 같은데 그렇지 않다던가...) 각 노드 위에 붙은 번호는 index라고 생각하면 된다. 힙에서의 index inde..

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..

재귀 함수를 활용한 경우 팩토리얼 구하기는 아마 재귀함수의 기본 중 기본이 아닐까... 생각해본다. 정수형 매개변수 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..