[알고리즘] 순환(Recursive) 개념과 기본 예제 3 정리

순환(Recursive) 개념과 기본 예제 3 정리

Designing Recursion; 순환 알고리즘의 설계

1. 순환 알고리즘 설계

• 적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야 함
• 모든 case는 결국 base case로 수렴해야 함

KeyPoint - 암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꾸어라

2. 예제 - 순차 탐색

• data[0]에서 data[n-1] 사이에서 target을 검색한다

    // 6. 순차 탐색 - 변경 전
    func search(data: [Int], n: Int, target: Int) -> Int {
            for i in 0..<n {   // '0' -> 배열의 시작 인덱스를 뜻하는 암시적 매개변수
                if data[i] == target {
                    return i
                }
            }
            return -1
    }

    // →  보통 배열 인덱스의 시작은 '0'으로 생각하기 때문에 시작 인덱스 값은 별도로 변수를 사용하지 않고 
    //    암시적 매개변수를 사용하였다

위 반복문을 순차 알고리즘으로 변경하려면 매개변수를 명시화한다
위에서 0으로 한 암시적 매개변수를 명시적 매개변수로 변경하면 된다

    // 6. 순차 탐색 - 변경 후
    // 'begin' 매개변수 추가
    func search2(data: [Int], begin: Int, end: Int, target: Int) -> Int {
            if begin > end {
                return -1
            } else if target == data[begin] {
                return begin
            } else {
                return search2(data: data, begin: begin + 1, end: end, target: target)
            }
    }

2. 예제 - 이진 검색(Binary Search)

이진 검색 알고리즘 - 배열의 값들이 크기 순으로 정렬되었을 때 사용하는 검색 알고리즘

    // 7. 이진 검색
    func binarySearch(data: [Int], begin: Int, end: Int, target: Int) -> Int {
            if begin > end {
                return -1
            } else {
                let middle = (begin + end) / 2
                if data[middle] == target {
                    return middle
                } else if data[middle] > target {
                    return binarySearch(data: data, begin: begin, end: middle - 1, target: target)
                } else if data[middle] < target {
                    return binarySearch(data: data, begin: middle + 1, end: end, target: target)
                }
            }
            return -1
    }

• data[middle] 이 target보다 작으면 end 매개변수에 middle -1을 전달한다
• data[middle] 이 target보다 크면 begin 매개변수에 middle +1을 전달한다

• 코드 Github 링크
  https://github.com/devssun/Algorithm-Study/blob/master/Algorithm/Inflearn/Algorithm-Inflearn/main.swift