알고리즘/이론
-
유클리드 알고리즘, 확장 유클리드 알고리즘알고리즘/이론 2021. 4. 20. 20:07
유클리드 알고리즘을 이용한 여러 코드를 짜 봅시다! 유클리드 알고리즘으로 GCD 구하기 GCD 즉, 두 수의 최대 공약수를 구하기 위해서 유클리드 알고리즘을 사용할 수 있습니다 두 수 a, b (a>b) 가 있을 때 a를 b로 나눈 나머지가 0이면 b는 a, b의 GCD이다 라는 알고리즘이 유클리드 알고리즘인데요. 이 때 나머지가 0이 아니면 0이 될 때까지 b와 a%b의 수로 위 과정을 반복해 줍니다. swift 코드로 알아볼게요 func gcd(_ a: Int, _ b: Int) -> Int{ var a = a, b = b if a < b { swap(&a, &b) } if a == b { return a } else if b == 0 { return a } else { return gcd(b, a ..
-
최단 경로 (다익스트라, 플로이드 워셜 알고리즘)알고리즘/이론 2021. 3. 14. 20:53
본 글은 '이것이 취업을 위한 코딩 테스트다 with 파이썬' 책을 공부하며 기록합니다. 단, iOS를 공부하고 있기 때문에 swift 언어로 코드를 바꿔보고 있습니다. 최단 경로 가장 짧은 경로를 찾는 알고리즘. '길 찾기' 문제 라고도 불린다. 상황에 맞는 효율적 알고리즘이 정해져 있다! 예 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 보통 그래프를 이용하여 표현되고, 각 지점은 노드로, 지점 간 연결된 도로는 간선으로 표현된다. 보통은 최단 거리를 출력하는 문제가 많다. 대표적 알고리즘 다익스트라 최단 경로 알고리즘 플로이드 워셜 벨만 포드 알고리즘 다익스트라 최단 경로 알고리즘과 플로이드 워셜 알고리즘이 가..
-
부품 탐색 문제를 여러 알고리즘으로 풀어보기 with 시간 복잡도알고리즘/이론 2021. 3. 6. 21:42
문제 N개의 부품 배열에서 M개의 문의 부품이 있는지 확인하여 "yes", "no"를 출력한다. 1 ≤ N ≤ 1,000,000 (100만) 1≤ M ≤ 100,000 (10만) → 최댓값 100만 이진 탐색 이용 let n = Int(readLine()!)! var inputs = readLine()!.split(separator: " ").map { return Int($0)!} print(n) print(inputs) let m = Int(readLine()!)! let targets = readLine()!.split(separator: " ").map { return Int($0)! } inputs.sort() for t in targets { binarySearch(inputs, t) } fu..
-
이진 탐색알고리즘/이론 2021. 2. 24. 21:22
본 글은 '이것이 취업을 위한 코딩 테스트다 with 파이썬' 책을 공부하며 기록합니다. 단, iOS를 공부하고 있기 때문에 swift 언어로 코드를 바꿔보고 있습니다. 순차 탐색 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례로 확인하는 방법. 데이터의 정렬 여부와 상관없이 앞에 있는 원소부터 하나씩 확인한다. 시간복잡도는 O(N) func sequentialSearch(n: Int, target: String, array: [String]) -> Int { for i in 0.. Int? { if start > end { return nil } let mid = (start + end) / 2 if array[mid] == target { return mid } else ..
-
정렬알고리즘/이론 2021. 2. 11. 17:22
본 글은 '이것이 취업을 위한 코딩 테스트다 with 파이썬' 책을 공부하며 기록합니다. 단, iOS를 공부하고 있기 때문에 swift 언어로 코드를 바꿔보고 있습니다. 퀵 정렬(quick sort) 가장 많이 사용되는 알고리즘 데이터의 특성을 파악하기 어렵다면 퀵 정렬이 유리 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식 피벗 사용 : 교환하기 위한 기준 평균 시간 복잡도 $O(NlogN)$ 그러나 최악의 경우 (데이터가 이미 정렬이 되어 있을 경우) O(N^2)이다 일반적 퀵 정렬 코드 var array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8] func quick_sort(array: inout [Int], start: Int, end: Int) { ..