-
[스위프트 : 알고리즘] 재귀 : 최대공약수 (6 / 6) : GCD: 재귀호출: 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수스위프트: Swift/알고리즘 : Algorithms in Swift 2018. 10. 4. 18:37
안녕하세요 ! 씩이 입니다!
저는 Swift 와 iOS 를 공부하고 연구하는 대딩 ( 대학생 ) 이구요!
같은 분야를 공부하는 분들에게 조금이라도 도움이 주고 싶어서 공부하는 것들을 공유합니다.
제 3자가 있다고 가정하고 설명하기 때문에 존대를 하지 않는점 이해 부탁드립니다.
공유가 미래 라고 생각합니다.
한국의 모든 개발자분들 존경합니다!
- Swift version : Swift 4.2 ( 18.09. 01 ~ ) Swift 언어
- 참고한 것들
- 씩이 Github
- 자료구조 소스파일 있습니다.
- iOS 관련 자료들, 정보들 정리해 두었습니다.
- 스위프트로 구현한 자료구조 : DataStructures in Swift4
- Swift4 : 연결리스트 (1 / 3) : #LinkedList : #DataStructrue : #자료구조
- Swift4 : 연결리스트 (2 / 3) : #LinkedList : #값 추가하기, push, append : #값 삽입하기,insert
- Swift4 : 연결리스트 (3 / 3) : #LinkedList : #값 제거하기, pop, removeLast, remove(at: )
- Swift4: 스택: #Stack: #자료구조: #DataStructure: #쌓기
- [스위프트 : 자료구조] 큐 (1 / 4): Queue: #자료구조: #배열로 구현한 큐: #배열의원리
- [스위프트 : 자료구조] 큐 (2 / 4): Queue: #자료구조: #연결리스트: #더블연결리스트: #DoublyLinkedList
- [스위프트 : 자료구조] 큐 (3 / 4): Queue: #자료구조: #Stack으로 구현: #더블스택: #DoubleStack: #제일좋음
- [스위프트 : 자료구조] 큐 (4 / 4): Queue: #자료구조: #RingBuffer: #링버퍼로 구현한 큐: #고정된배열: #마지막!!
- 스위프트: 트리: Tree: #자료구조: #깊이우선탐색: #레벨정렬탐색: #검색알고리즘: Swift4
- 스위프트: 이진 탐색 트리(1 / 2): #BinarySearchTree: #자료구조: #배열과 비교: #트리: #탐색: #삽입: #삭제
- 스위프트: 이진 탐색 트리(2 / 2): #BinarySearchTree: #자료구조: #배열과 비교: #트리: #탐색: #삽입: #삭제
- [스위프트 : 자료구조] AVL Tree: 자가 균형 트리: #balance: #트리의 높이: #rotation메소드: #성능오짐
- 스위프트로 구현한 알고리즘 : Algorithms in Swfit4
- [스위프트 : 알고리즘] 재귀호출 (1 / 6) : recursive: 재귀호출 : 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수
- [스위프트 : 알고리즘] 재귀 : 팩토리얼 (2 / 6) : factorial: 재귀호출 : 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수
- [스위프트 : 알고리즘] 재귀 : 거듭제곱 (3 / 6) : Power: 재귀호출 : 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수
- [스위프트 : 알고리즘] 재귀 : 피보나치 수열(4 / 6) : Fibonacci: 재귀호출 : 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수
- [스위프트 : 알고리즘] 재귀 : 하노이의 탑 (5 / 6) : Hanoi: 재귀호출: 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수
- [스위프트 : 알고리즘] 재귀 : 최대공약수 (6 / 6) : GCD: 재귀호출: 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수
- Swift 주제별 분류
- Swift4 : 제어 전달 명령문( Control Transfer Statement ) : #continue, #break, #return 키워드
- Swift4 : 클래스와 구조체 : #값을 대하는 방식 : #참조타입, 값 타입 : #===
- Swift4 : 프로퍼티 : #Property : #get, set : #willSet, didSet
- Swift4 : 메소드 : #Method : #영향력 범위 : #self : #mutating : #값타입 수정
- Swift4 : 프로토콜 1 : #Protocol : #설계 : #요구사항 : #델리게이트 패턴 전처리 (1 / 2)
- Swift4 : 프로토콜 2 : #델리게이트 패턴 : #델리게이션 (2 / 2)
- Swift4 : 제네릭 : #Generics : #왜필요해? : #where키워드 : #제약사항걸기
- Swift4 : 자동 참조 카운팅 : #Automatic Referece Counting : #ARC :#강한참조 : #Strong Reference Cycle : #메모리 누수
- Swift4 : 클로저: Closure: #표현방식: #왜필요해?: #효율적: #간결성: #생략
재귀 : 최대 공약수: GCD (6 / 6) in Swift4
(feat . 최대 공배수)
- 최대공약수가 뭐야?
- by 나무위키
- 유클리드 호제법이 뭐야?
- 알겠고 그래서 어떻게 쓰는건데 ?
- 유클리드 호제법 문제해결 과정
- 재귀호출 요구사항 재귀호출에 대해 모른다면 클릭
- 재귀의 호출은 문제 내에서 범위가 점점 작은 방향, 즉 하위문제에 대해 이루어 져야 한다.
- 재귀 호출은 더 이상 반복되지 않는 종료 조건이 있어야 한다.
- 구성
- 전체 구성을 보고 큰그림 그리세요.
- 재귀호출, 반복문 으로 2개 구현할 예정.
12345678public func example( description:String, excute:()->() ) // 헬퍼메소드public func processTime(blockFunction: () -> ()) -> Floatpublic func gcd_recur(a:Int, b:Int) -> Int // 재귀호출로 구현한 최대공약수public func gcd_for(a:inout Int, b:inout Int) -> Int // 반복문 으로 구현한 최대공약수public func lcm(a: Int, b: Int) -> Int //private func gcdProcess (a:inout Int, b:inout Int) // 헬퍼 메소드cs - 구현 : gcd_recur
- gcd 는 greatest common dividor 의 약자입니다. 최대공약수^^
- 재귀호출로 구현한 최대공약수
- 나머지가 없을 경우 ( a % b == 0 )인 경우가 재귀호출의 종료조건이 됩니다. -> 요구사항 1 만족
- 재귀호출로 매개변수에 a 에는 a 보다 작은 b, b 에는 b 보다 작은 a % b 가 입력되쥬? 작아지므로 - > 요구사항 2 만족
123456789101112public func gcd_recur(a:Int, b:Int) -> Int { // greatest common divisorif a == b { return a }else if a > b { //if a % b == 0 { return b } // 요구사항 1. 종료조건else { return gcd_recur(a: b, b: a % b) }// 요구사항 2. 입력값 a 가 a보다 작은 b로, b 는 a % b 로 작아짐.}else{if b % a == 0{ return a } // 종료조건else { return gcd_recur(a: a, b: b % a) } // a < b 인 경우엔 a, b 의 위치만 바꿔주면 되쥬?}}cs - 실행 과 결과
- 구현 : gcd_for
- 반복문으로 구현한 최대공약수
- b 는 이전 반복의 수행이 완료된 후의 b 이기 때문에 이전의 r (a % b) 가 되겠쥬? a % b == 0 일 때 종료조건이 됩니다.
- inout 키워드
- 스위프트의 함수의 매개변수는 기본적으로 상수(let) 입니다.
- 매개변수를 변수로 바꿔서 값이 변경가능하게 하는 것이 inout 키워드 입니다.
- inout 키워드를 사용한 함수를 호출할 경우에는 매개변수에 &키워드를 붙여 메모리 주소값을 전달합니다. 더 알고싶다면
- gcdProcess 는 단순히 두 변수 a, b 위치 바꾸기 위한 거라서 따로 구현은 안할게요.
123456789101112131415public func gcd_for(a:inout Int, b:inout Int) -> Int {// 함수 내부에서 변수 a, b 가 변경되므로 inout 을 붙인 것입니다.if a == b { return a }else if a > b {while b != 0 { // 종료조건let r = a % ba = bb = r}return a}else { // a < b 인 경우에 a, b 위치만 바꿔주면 됩니다^^gcdProcess(a: &b, b: &a)return b}}cs - 실행 과 결과
- 구현 : lcm ( 최소 공배수 )
- 최소 공배수 덤으로 구현해볼까요. 너무 간단해서..
- 원하는 두 수에서 최대공약수를 나눈 값이 최소 공배수 거든요.
123public func lcm(a: Int, b: Int) -> Int {return a * b / gcd_recur(a: a, b: b)// 두 정수의 곲 / 최대 공약수 하면 최소공배수 나옴.}cs - 실행 과 결과
- 수행속도
- 는 굳이 비교하지 않겠습니다. 연산이 별로 없기 때문에 그냥 오지게 빨라욧
- Helper 메소드 ( 궁금하실 까봐^^.. )
1234567891011public func example( description:String, excute:()->() ) {print("---Example of \(description)---")excute()}public func processTime(blockFunction: () -> ()) -> Float {let startTime = CFAbsoluteTimeGetCurrent()blockFunction()let processTime = CFAbsoluteTimeGetCurrent() - startTimereturn (Float(processTime))}cs '스위프트: Swift > 알고리즘 : Algorithms in Swift' 카테고리의 다른 글
댓글