SQLite로 데이터베이스를 활용하려다 Realm이라는 새로운 모바일 데이터베이스를 발견하고 이를 사용해 보기로 한다. 사용방법이나 튜토리얼이 모두 한글로 자세히 설명이 되어 있기에 금방 익숙해 질 수 있을 것 같다. 아래의 페이지를 참고하자.

 https://realm.io/kr/


 아직 자세히는 모르지만 직접 DB에 접속하여 스키마를 구현하는 것이 아니라, 개발 코드 내에서 Realm model의 Object를 상속받은 클래스를 정의하면 자동으로 DB에 해당 형태로 스키마를 구현하는 듯 하다. 즉 클래스의 프로퍼티를 정의하면 DB의 컬럼이 설정된다고 보면 될 것 같다. 그리고 SQL이 아니라 일반 객체의 메서드를 이용하는 것 처럼 DB의 데이터를 조작할 수 있다.


 이전에 만들었던 FoodVO를 대체하는 Realm 오브젝트 클래스를 만들어보자. 먼저 Realm을 사용하기 위한 framework를 Xcode에 추가해준다.




  Food.swift라는 오브젝트 클래스 파일을 만들고 아래와 같이 작성한다.


Food.swift

import Foundation
import RealmSwift

class Food: Object {
    
// Specify properties to ignore (Realm won't persist these)
    dynamic var name: String = ""
    dynamic var expDate: Date = Date(timeIntervalSinceNow: 0)
    private dynamic var categoryRawState = FoodCategory.Grain.rawValue
    public var category: FoodCategory {
        get {
            return FoodCategory(rawValue: categoryRawState)!
        }
        set {
            categoryRawState = newValue.rawValue
        }
    }
    
//  override static func ignoredProperties() -> [String] {
//    return []
//  }
}

enum FoodCategory : Int {
    case Grain, Potato, Sugars, Pulses, SeedsAndNuts, Vegetables, Mushrooms, Fruits, Meat, Eggs, Seafoods, Seaweed, MilkProducts, FatAndOils, Drinks, Seasoning, Etc
    static var count: Int { return FoodCategory.Etc.rawValue + 1 }
    
    var description: String {
        switch self {
        case .Grain : return "곡류"
        case .Potato : return "감자류"
        case .Sugars : return "당류"
        case .Pulses : return "두류"
        case .SeedsAndNuts : return "종실류"
        case .Vegetables : return "채소류"
        case .Mushrooms : return "버섯류"
        case .Fruits : return "과실류"
        case .Meat : return "육류"
        case .Eggs : return "난류"
        case .Seafoods : return "어패류"
        case .Seaweed : return "해조류"
        case .MilkProducts : return "유제품류"
        case .FatAndOils : return "유지류"
        case .Drinks : return "음료"
        case .Seasoning : return "조미료류"
        case .Etc : return "기타"
        }
    }
}

 데이터베이스에서는 enum 타입을 인식하지 못하므로, 실제 데이터베이스에 저장될 값은 private로 지정하여 Int 형태로 저장되게 하며, 코드 상에서만 enum타입으로 인식될 수 있도록 public 프로퍼티를 따로 설정하여 준다. enum타입인 FoodCategory를 해당 클래스에 동시에 선언해주었다. FoodCategory에는 단순 case만 입력한 것이 아니라 추가적으로 몇개의 데이터가 있는지 정적 변수를 추가하였으며, 각각에 대한 설명을 반환하는 변수 또한 추가하였다.



 이제 기존 코드를 수정하여 Realm 데이터베이스에 저장하고 값을 가져 올 수 있게 하자.


RefrigeratorTableViewController.swift

import UIKit
import RealmSwift

class RefrigeratorTableViewController : UITableViewController {
    var list = Array<Food>()
    var dateFormat = DateFormatter()
    
    override func viewDidLoad() {
        dateFormat.dateFormat = "yyyy-MM-dd"
        dateFormat.locale = Locale.init(identifier: "ko_KR")
        list.append(Food(value: ["name":"서울우유", "category":FoodCategory.MilkProducts, "expDate":dateFormat.date(from: "2017-04-20")!]))
        list.append(Food(value: ["name":"3분짜장", "category":FoodCategory.Etc, "expDate":dateFormat.date(from: "2017-07-31")!]))
    }
    
    override func tableView(_ tableView: UITableView, numberOfRowsInSection section: Int) -> Int {
        return list.count
    }
    
    override func tableView(_ tableView: UITableView, cellForRowAt indexPath: IndexPath) -> UITableViewCell {
        let row = list[indexPath.row]
        let cell = tableView.dequeueReusableCell(withIdentifier: "SokoCell")!
        cell.textLabel?.text = row.name
        cell.detailTextLabel?.text = "유통기한: \(dateFormat.string(from: row.expDate))"
        
        return cell
    }
    
    override func tableView(_ tableView: UITableView, didSelectRowAt indexPath: IndexPath) {
        NSLog("Touch Table Row at %d", indexPath.row)
    }
    
    @IBAction func unwindToMainViewController(segue : UIStoryboardSegue) {
        
    }
    
    @IBAction func unwindToMainViewControllerAndRefreshList(seque : UIStoryboardSegue) {
        
    }

}


위 코드는 데이터베이스에 저장하는 코드가 아닌 Realm 객체로 테이블 뷰에 표시하는 코드이다. 이 코드로 실행이 되는지 테스트하고 진행한다.



'재료 추가' View Controller를 조금 더 완성시켜서 컴포넌트에 입력한 값을 저장할 수 있도록 만든다. 먼저 Swift파일을 하나 새로 생성해서 'AddFoodViewController.swift'라 이름 짓고 아래와 같이 storyboard의 ViewController와 연결한다. 또한 카테고리를 표현하는 PickerView도 추가한다.



 값을 읽어올 컴포넌트를 아래와 같이 연결한다.



 '닫기'와 '추가' 버튼을 unwind segue로 미리 RefrigeratorTableViewController에 생성한 unwindToMainViewController(segue:) 메서드로 연결한다. 그리고 '닫기'버튼의 Identifier를 'AddCancel'로, '추가'버튼은 'AddDone'으로 설정한다.




 코드를 아래와 같이 완성한다.


AddFoodViewController.swift

import UIKit

class AddFoodViewController : UIViewController, UIPickerViewDataSource, UIPickerViewDelegate {
    @IBOutlet var name: UITextField!
    @IBOutlet var expDate: UIDatePicker!
    @IBOutlet var category: UIPickerView!
    
    override func viewDidLoad() {
        
        // textField에 Custom디자인을 적용한 코드. 밑줄이 생성된다.
        let border = CALayer()
        let width = CGFloat(0.3)
        border.borderColor = UIColor.gray.cgColor
        border.frame = CGRect(x: 0, y: name.frame.size.height - width, width: name.frame.size.width, height: name.frame.size.height)
        
        border.borderWidth = width
        name.layer.addSublayer(border)
        name.layer.masksToBounds = true
    }
    
    // UIPickerView 설정 메서드
    func numberOfComponents(in pickerView: UIPickerView) -> Int {
        return 1
    }
    
    func pickerView(_ pickerView: UIPickerView, numberOfRowsInComponent component: Int) -> Int {
        return FoodCategory.count
    }
    
    func pickerView(_ pickerView: UIPickerView, titleForRow row: Int, forComponent component: Int) -> String? {
        return FoodCategory(rawValue: row)?.description
    }
    
    // 새 Food객체 생성 메서드
    func newFood() -> Food? {
        let food = Food(value: ["name":name.text!, "expDate":expDate.date])
        food.category = FoodCategory(rawValue: category.selectedRow(inComponent: 0))!
        return food
    }
    
    // unwind 하기 전 실행되는 메서드.
    override func prepare(for segue: UIStoryboardSegue, sender: Any?) {
        if segue.identifier == "AddDone" {
            guard let food = newFood(), let refrigeratorTableViewController = segue.destination as? RefrigeratorTableViewController else {
                return
            }
            
            let realm = refrigeratorTableViewController.realm!
            try! realm.write {
                realm.add(food)
            }
        }
    }
}


 '추가' 버튼을 누를 때 컴포넌트에 설정된 값들이 저장되어야 한다. 따라서 unwind 하기 전에 prepare 메서드에서 DB에 저장하고, RefrigeratorTableViewController에서 DB가 수정됨을 확인하면 자동으로 화면을 새로고침한다. 이제 RefrigeratorTableViewController를 완성시키자.


RefrigeratorTableViewController.swift

import UIKit
import RealmSwift

class RefrigeratorTableViewController : UITableViewController {
    var list: Results<Food>?
    var dateFormat = DateFormatter()
    var notificationToken: NotificationToken!
    var realm: Realm!
    
    override func viewDidLoad() {
        dateFormat.dateFormat = "yyyy-MM-dd"
        dateFormat.locale = Locale.init(identifier: "ko_KR")
        setupRealm()
    }
    
    func setupRealm() {
        try! realm = Realm()
        
        func updateList() {
            if list == nil {
                list = self.realm.objects(Food.self)
            }
            self.tableView.reloadData()
        }
        updateList()
        
        self.notificationToken = self.realm.addNotificationBlock { _ in
            updateList()
        }
    }
    
    deinit {
        notificationToken.stop()
    }
    
    override func tableView(_ tableView: UITableView, numberOfRowsInSection section: Int) -> Int {
        return list!.count
    }
    
    override func tableView(_ tableView: UITableView, cellForRowAt indexPath: IndexPath) -> UITableViewCell {
        let row = list![indexPath.row]
        let cell = tableView.dequeueReusableCell(withIdentifier: "SokoCell")!
        cell.textLabel?.text = row.name
        cell.detailTextLabel?.text = "유통기한: \(dateFormat.string(from: row.expDate))"
        
        return cell
    }
    
    override func tableView(_ tableView: UITableView, didSelectRowAt indexPath: IndexPath) {
        NSLog("Touch Table Row at %d", indexPath.row)
    }
    
    @IBAction func unwindToMainViewController(segue : UIStoryboardSegue) {
    }
}


 list타입을 원래의 Array<Food>타입이 아닌 Results<Food>타입으로 변경하였다. Results타입은 Realm 프레임워크에서 제공하는 타입으로 사용자가 Realm에서 가져온 데이터들의 배열로 Array와 유사합니다. 단 실제 DB데이터를 가지고 있는것과 같아서 이 배열에 값을 추가하므로써 DB에 값을 저장하는 것과 동일한 효과를 갖는다.

 setupRealm()에서 Realm 객체를 할당하고 Realm으로 부터 저장된 데이터들을 가져오는 updateList()메서드를 수행한다. 또한 notificationToken을 이용하여 Realm의 변화 여부를 감지한다.


 앱을 실행하여 Realm에 값이 저장되어 앱이 꺼지고 켜져도 값이 유지되는지 확인해보자.




 앱이 종료되었다가 다시 실행되어도 값이 유지되고 있기에 메모리에 유지된 것이 아닌 별도의 데이터베이스에 값이 저장되고 있는 것을 알 수 있다. Simulator의 앱 경로를 찾아 Realm Browser를 이용하여 Realm에 저장되고 있는지 확인 할 수 있다. (Realm Browser는 macOS에서만 제공된다.)


 Realm 파일의 경로는 아래와 같다. 아래의 파일을 Realm 브라우저로 실행하면 위와 같이 내용을 확인 할 수 있다.

/Users/<username>/Library/Developer/CoreSimulator/Devices/<simulator-uuid>/data/Containers/Data/Application/<application-uuid>/Documents/default.realm

 Xcode의 Debug 환경에서 아래의 LLDB 명령어를 입력하여 앱의 경로를 바로 찾을 수 있다.

(lldb) po Realm.Configuration.defaultConfiguration.fileURL

자세한 내용은 아래의 링크를 참고하자.

https://stackoverflow.com/questions/28465706/how-to-find-my-realm-file/28465803#28465803


 이 'soko' 앱의 핵심 기능은 "유통기한이 있는 음식물을 리스트로 만들어 관리하고, 필요시 알림을 해주는 것"이다. 그외의 기능은 결국 부가적인 기능이다. 따라서 핵심기능부터 완성해볼 것이다. 지난 탭 바로 나눠진 여러개의 View Controller 중에서 '내 냉장고'에 해당하는 탭의 기능을 구현해 본다.


 먼저 '내 냉장고'에 해당하는 View Controller를 클릭하고, 상단 메뉴의 [Editor] - [Embeded In] - [Navigation Controller]를 선택한다. 그럼 기존의 View Controller가 Navigation 형식으로 바뀌는 것을 볼 수 있다. 다른 View Controller에서도 Navigation Controller 형태로 만들 것이므로 모두 적용해 준다.




 Navigation Bar의 오른쪽에 생성된 ViewController를 선택하여 Delete키를 눌러 삭제하고, 오른쪽 하단의 Object library에서 Table View Controller를 끌어 화면에 놓고 Navigation Controller와 연결해주자.

 



 이제 Navigation Bar의 가운데 부분을 더블클릭 하면 제목을 입력할 수 있는 공간이 나타난다. 제목을 입력해 주자. 그리고 Xcode의 우측 하단의 [Show the Object library]에서 [Bar Button Item]을 찾아 Navigation Bar의 우측 상단에 놓아준다. 그리고 추가한 버튼을 클릭하여 Xcode 우측 상단의 [Show the Attribute Inspector]에서 System Item을 [Add]로 바꿔준다.

 






 

 이 상태에서 실행을 해 보면 다음과 같이 표시된다.


 목록이 존재하지 않는데도 여러개의 줄로 구분 되어있음을 알 수 있다. 목록이 없을 때에는 이러한 줄 구분이 안보이게 하기 위해 아무것도 존재하지 않는 View를 View Controller 안에 추가해 준다.


그럼 아래와 같이 내용이 없는 경우 줄이 표시되지 않는다.


 이제 테이블 뷰에 임의로 목록을 추가해 보자. 먼저 테이블 뷰의 Cell을 클릭한다. 화면 왼쪽의 Document Outline에서 직접 선택해 주어도 좋다. 그리고 우측의 [Attribute Inspector]에서 Identifier를 'SokoCell'로 바꾸고, Style을 'Subtitle'로 바꿔주었다.






 이렇게 설정한 셀은 실제로 화면에 표시되는게 아니라 서식을 만든 것 뿐이다. Custom형태로 서식을 만들 수 있으며 이는 기능이 완성된 후에 나중에 바꿀 것이다. 여러개의 셀을 Main.Storyboard에서 만드는게 아니라, 여기서 만든 서식을 코딩을 통해 여러개를 표시할 수 있도록 할 것이다. 왼쪽에서 'soko' 그룹에서 오른쪽 클릭하고 [New Group]을 누른 후, 생성된 그룹의 이름을 'refrigerator'로 만든다. 이 그룹에서는 '내 냉장고'에 해당하는 코드를 입력한 swift파일을 관리할 것이다.


 다시 refrigerator 그룹을 우클릭하고 [New File...]을 선택하고 Swift File을 선택한 후, 이름을 RefrigeratorTableViewController.swift로 만든다. 그리고 아래의 코드를 작성한다.


RefrigeratorTableViewController.swift

import UIKit

class RefrigeratorTableViewController : UITableViewController {

}

 위의 코드 안에서 이제 이 TableViewController를 조작하는 코드를 작성할 것이다.

 다시 Main.storyboard를 클릭하고, 우리가 생성한 TableViewController를 선택하고 우측 상단의 [Identity Inspector]에서 Class를 우리가 방금 만든 RefrigeratorTableViewController를 선택한다. 이렇게 Class를 선택하면 위에서 생성한 Swift파일과 Storyboard의 TableViewController가 연결 된 것이다.


 


 이제 직접 임의의 데이터를 넣어 화면에 출력시켜보자. 먼저 음식에 관한 데이터를 가지고 있는 ValueObject 클래스를 만든다.


FoodVO.swift

import Foundation

class FoodVO {
    init () {
    }

    var name : String?
    var sellByDate : Date?
    var category : FoodCategory?
}


FoodCategory라는 타입은 열거형 객체이다. 아래와 같이 선언하였다.


FoodCategory.swift

import Foundation

enum FoodCategory : Int {
    case Grain, Potato, Sugars, Pulses, SeedsAndNuts, Vegetables, Mushrooms, Fruits, Meat, Eggs, Seafoods, Seaweed, MilkProducts, FatAndOils, Drinks, Seasoning, Etc
}


 이제 TableViewController에 데이터를 추가해 보자. 먼저 구현한 코드를 보자.


RefrigeratorTableViewController.swift

import UIKit

class RefrigeratorTableViewController : UITableViewController {
    var list = Array<FoodVO>()
    var dateFormat = DateFormatter()
    
    override func viewDidLoad() {
        dateFormat.dateFormat = "yyyy-MM-dd"
        dateFormat.locale = Locale.init(identifier: "ko_KR")
        
        var fvo = FoodVO()
        fvo.name = "서울우유"
        fvo.category = FoodCategory.MilkProducts
        fvo.sellByDate = dateFormat.date(from: "2017-04-20")
        list.append(fvo)
        
        fvo = FoodVO()
        fvo.name = "3분짜장"
        fvo.category = FoodCategory.Etc
        fvo.sellByDate = dateFormat.date(from: "2017-07-31")
        list.append(fvo)
    }
    
    override func tableView(_ tableView: UITableView, numberOfRowsInSection section: Int) -> Int {
        return list.count
    }
    
    override func tableView(_ tableView: UITableView, cellForRowAt indexPath: IndexPath) -> UITableViewCell {
        let row = list[indexPath.row]
        let cell = tableView.dequeueReusableCell(withIdentifier: "SokoCell")!
        cell.textLabel?.text = row.name
        cell.detailTextLabel?.text = "유통기한: \(dateFormat.string(from: row.sellByDate!))"
        
        return cell
    }
    
    override func tableView(_ tableView: UITableView, didSelectRowAt indexPath: IndexPath) {
        NSLog("Touch Table Row at %d", indexPath.row)
    }
}


 viewDidLoad() 메서드는 해당 ViewController가 화면에 표시될 때 가장 먼저 실행되는 메서드다. 따라서 override하여 정의해야 내가 원하는 기능을 추가 할 수 있다. 위의 코드에서는 dateFormat을 초기화 하고, 임의의 데이터를 직접 list에 추가하는 코드를 작성하였다. 실제 앱을 작성할 때에는 여기에 직접 데이터를 입력하지 않고 iOS 내부의 데이터베이스에서 데이터를 가져오거나, 웹을 통해 호출해 저장해야 할 것이다.

 tableView(_ tableView:, numberOfRowsInSection section: Int) -> Int 메서드는 몇 개의 줄이 표시되어야 하는지 반환하는 함수이다. 앱이 이 메서드를 호출하여 몇 개의 줄이 필요한지 확인할 것이다. 현재 코드에서는 list라는 배열의 크기만큼 리스트를 표시할 것이다.

 tableView(_ tableView:, cellForRowAt indexPath:) -> UITableViewCell 메서드는 Cell을 반환한다. 즉 여기서 Cell을 생성하고, Cell안에 표시할 내용을 추가하고 앱에 반환하는 것이다. 여기서는 list에서 VO를 불러와 각 내용을 textLabel과 detailTextLabel에 추가하였다.

 tableView(_ tableView:, didSelecRowAt indexPath:) 메서드는 Cell을 클릭했을 때 어떠한 행동을 할 것인지 정의하는 메서드이다.


 이제 다시 실행 해보자.


 이제 '+'버튼을 누르면 '재료 추가' 뷰로 이동하도록 바꿔보자. 먼저 새로운 ViewController를 만들고 아래와 같이 구성한다.


 그리고 기존 테이블 뷰 컨트롤러의 +버튼을 ctrl 버튼을 누른채로 드래그한 후 새로 만든 ViewController에 드롭하면 아래와 같은 창이 뜬다. [Present Modally]를 선택한다. 그럼 두 ViewController가 연결되는 것을 볼 수 있다. 앱을 실행하면 +버튼을 누르면 새로 생성한 ViewController로 넘어가게 된다.




 앱을 실행하면 '+' 버튼을 눌렀을때 오른쪽 View Controller는 표시 되지만, 다시 돌아오는건 작동하지 않는다. unwind 기능을 추가하여야 한다. unwind 메서드는 돌아가고자 하는 컨트롤러에서 작성해야 한다.


RefrigeratorTableViewController.swift

import UIKit

class RefrigeratorTableViewController : UITableViewController {
    
    (... 생략 ...)
    
    @IBAction func unwindToMainViewController(segue : UIStoryboardSegue) {
        
    }
    
    @IBAction func unwindToMainViewControllerAndRefreshList(seque : UIStoryboardSegue) {
        
    }

}


 unwindToMainViewController는 '닫기' 버튼을 눌렀을때 실행될 메서드이고 unwindToMainViewControllerAndRefreshList는 '추가' 버튼을 눌렀을 때 리스트를 새로고침 하기 위한 메서드이다.

 이제 스토리보드에서 '닫기' 버튼을 ctrl을 누른채 드래그하여 ViewController 상단의 세번재 아이콘인 [Exit]에 드롭한다. 그리고 unwindToMainViewController에 연결한다. 마찬가지로 '추가' 버튼도 연결한다.

 


이제 앱을 실행하면 추가 페이지가 열리고 닫히는 모습을 볼 수 있다.



 다음에는 데이터베이스에 이 재료 object들을 저장할 것이다. SQLite를 사용하려 계획하였으나 최근 Realm이라는 데이터베이스가 각광받는다기에 학습하며 적용해 보려 한다. 현재 위의 코드에서 재료 추가 뷰에서 값을 입력받아 데이터베이스에 저장하고, 데이터베이스에서 다시 값을 읽어와 리스트에 출력할 것이다.

 왜 iOS 앱을 개발하려 하는지 특별한 이유는 없다. 그저 내가 아이폰을 쓰고 있기에, 이걸로 실제로 사용하는 앱을 만들어 보고자 할 뿐이다. Objective-C의 문법은 다른 객체지향 언어와 비교하여 생소한 문법을 많이 가지고 있었기에 접근하기 까다로웠지만, Swift는 좀더 세련되고 보편적인 형태의 문법을 가지고 있기에 배우기 쉽다 생각하여 선택하게 되었다.


책은 <꼼꼼한 재은 씨의 스위프트2 프로그래밍>을 도서관에서 대여하여 참고하였다. 현재는 Swift3 버전까지 공개되어 있지만 약간의 변경만 있을뿐 기초적인 부분에서는 큰 변화가 없기 때문에 이 책으로 개발하는데 큰 무리가 없을 것으로 보인다. 참고로 저 책도 현재 Swift3로 판올림 되어 판매되고 있다. 이 책은 굉장히 두껍지만(페이지만 1144쪽) 프로그래밍 초보도 이해할 수 있을 정도로 쉽게 설명되어있기 때문에 초보자에게 큰 도움이 될 것이라 생각하며, 나와 같이 약간의 프로그래밍 지식이 있는 사람은 Swift 문법 부분을 금방 훑고 지나갈 수 있으리라 생각한다.


 개발하려는 앱은 단순하게 말해서 '냉장고 앱'이다. 어머니가 워낙 손이 커서 매번 많은 양의 장을 보는데, 유통기한이 지나 버리게 되는 음식물들을 보면서 아깝다는 생각이 들어 이를 체계적으로 관리하는 앱이 있으면 어떨까 하는 생각에 개발을 생각하게 되었다. App Store에도 비슷한 앱이 몇 개 존재하긴 하나 현재 업데이트가 멈춰있고, 내가 필요로 하는 기능들이 부족한 듯 하여 부족한 부분이 개선된 앱을 만들어 볼 것이다. (계획은 꽤 오래전에 했는데 카카오 면접에 떨어지고, 하릴없이 놀고만 있을수 없어서 실천에 옮기게 되었다.)


 이러한 단순한 아이디어를 구현하는 앱에서 출발하여 끝에는 Ruby on Rails로 구현한 웹 서버와 연동되는 앱을 만들것이다. 아직 구체적 방향은 나오지 않았지만, 대략적으로 어떻게 개발했으면 좋을까 하는 감은 가지고 있다. 아래는 대강 이 앱의 구성을 낙서하듯 그려본 것이다.







 매일 조금씩이라도 개발하여 앱 스토어에 등록할 수 있도록 노력해 볼 것이다.



앱 이름은 '소코(Soko)'로 정했다. 일본어로 창고라는 뜻이라한다. 아래처럼 앱을 생성했다.



 간단한 레이아웃만 잡아준다. 아래처럼 기본 View Controller를 삭제하고 우측하단 'Show the Object library'에서 Tab Bar Controller를 화면에 끌어 놓는다. 



 Tab Bar Controller가 시작화면이 될 수 있게 우측 상단의 'Show the Attributes Inspector'에서 'Is Initial View Controller'에 체크표시한다.



탭 바에 화면이 4개가 필요하기 때문에 View Controller를 추가로 생성해서 끌어놓는다. 그리고 Tab Bar Controller의 회색면을 Ctrl을 누른채로 클릭하고 새로 추가한 View Controller에 놓는다. 그리고 'Relationship Segue' 밑의 'view controllers'를 클릭한다.



 각 View Controller에 이름을 설정해 주었다.






 각 View Controller 밑에 있는 Tab Bar Item을 클릭하고 Title을 설정한 뒤 Custom 아이콘 이미지를 넣어준다. 나는 아래의 사이트에서 다운받아 사용 하였다.

http://www.iconbeast.com/free/




 각 View Controller 상단에 구별할 수 있는 Label을 추가하여 집어넣고 실행하여 확인해 보았다.



 코드는 https://github.com/Stardust-kr/soko 에 지속접으로 업데이트 될 것이다.


 자, 이제 시작이다.

헌법재판소의 만장일치 인용 결정은 예상대로였다. 탄핵소추안의 많은 부분이 탄핵의 요건이 될 수 없다는 설명으로 시작했지만 가장 마지막, 국정농단에 의한 국민주권주의 위배에 대해 엄정한 판단을 내린 것이다. 뿐만 아니라 이후의 대통령의 대응이 거짓(정규재 TV 인터뷰 등)과 불통(압수수색과 검찰 및 특검 조사 거부)으로 일관하고 있어 헌법을 수호할 의지가 없음을 정확하게 지적한 것이다. 재판관의 보수, 진보 성향은 아무런 의미가 없었다. 보수와 진보는 모두 헌법적 가치 아래에서 의미 있는 것이다. 헌법을 유린하는 것은 그 둘의 아무것에도 속하지 않는다.

박근혜 정부는 시작부터 헌법을 유린해왔다. 대통령 선거부터 이른바 셀프 감금사건으로 불리는 국정원 여론조작 사건이 있었고, 당시 국정원장은 아직까지도 재판 중에 있다. 시작부터 헌법적 근본을 의심받은 것이다. 이후 서울시 공무원 간첩조작 사건으로 다시 한 번 국민을 유린했다. 세월호 참사와 메르스 사태에 대해서는 방관자적 태도를 보였다. 참사 당시 청와대는 컨트롤 타워가 아니다라는 유명한 말은 이 정부의 태도를 명확하게 보여준다. 헌재는 탄핵 심판에서 이 정부가 생명권 보호 의무를 져버리지 않았다고 판단한 것이 아니라, 성실성이라는 추상적 개념이 탄핵 요건에 해당하지 않는다고 판단한 것일 뿐이다(일부 재판관은 성실한 직책 수행 의무를 다하지 않았다고 판단 했으나 이는 대통령을 파면할 만큼 중대한 위법 행위는 아니라고 보충 의견을 제시했다). 이후에도 끊임없는 위헌 행위를 자행해왔다. 국정원은 해킹프로그램을 이용하여 내국인을 사찰했다는 의혹, 시대를 역행하는 국정 교과서 강행, 그리고 블랙리스트와 국정농단 까지.

위와 같은 사건은 박근혜 전 대통령이 헌법에 대해 어떤 시각을 가지고 있는지 명백하게 보여준다. 사실 이것은 4년전 우리가 예견했던 일이다. 그가 이미 독재자인 박정희의 딸이며, 그 이후에도 박정희를 위시하는 세력에 비호를 받으며 우리나라 제 1당의 지도자로 영도 되었던 것이다. 그의 능력이나 민주주의에 대한 철학으로 지지를 받은 것이 아니라 단지 박정희라는 그의 핏줄이 주는 후광으로 지지를 받은 것이다. 이게 진정한 패권주의. 단지 박정희라는 이름의 권력으로 모든 것을 정당화 한 것이다. 친박 패권주의의 행패는 지난 총선에서 극에 달했다. 새누리당의 공천과정에서 단지 친박이라는 이유 하나만으로 공천과정을 방해했고, 그 결과 다수의 친박 세력이 당을 장악했다. 그리고 국민은 엄정한 심판을 내렸다. 새누리당은 총선에서 원내 제 2당으로 밀려날 수준으로 참패한 것이다.

이러한 패권주의에 갇혀 박근혜 전 대통령은 유신적 사고(思考)에 머물러 있었던 것이다. 국민의 주권은 대통령의 권한 밑에 있다는 사고가 짙게 깔려있는 것이다. ‘박정희는 쿠데타로서 국민 주권과 상관 없이 권력을 장악했던 인물이기에 이러한 사고가 있었을 수도 있다. 허나 박근혜 전 대통령은 국민의 투표로 당선된 대통령이었다. 국민의 주권이 있었기에 당선 되었음에도 이러한 시각을 가지고 있다는 것은 그가 얼마나 시대착오적 인물인지 적나라하게 드러낸다. 유신적 사고에 머물러 있던 박근혜 전 대통령으로서는 모든 위헌적 행동이 자신에게는 선의였을 것이다. 애초에 사고 자체가 민주주의적이지 않은 생각에 기반한 선의였던 것이다. 안 지사의 말대로 이러한 탄핵 사태가 의도와 상관없이 결과가 문제였기 때문에라고 말할 수도 있지만, 애초에 박근혜 전 대통령은 사고 자체가 문제였다. 유신 독재자의 딸은 결국 민주적 절차에 의해서 역사적 심판을 받았다.

친박 패권주의에 경도된 사람들의 행동에도 이와 같은 시대착오적 사고가 나타난다. 태극기 집회의 정체성만 봐도 그러하다. 대통령을 지키는 것 만이 애국인 듯 착각하며 태극기를 흔드는 모습을 보며, 스스로 국민 주권을 인정하지 않는 모습에 한숨이 나올 뿐이다. 대통령은 잘못한 것이 없는데, 순수한 선의로 행동했을 뿐인데 하는 말은 진심이었을 것이다. 물론 위에서 말 한대로 유신적 사고 아래서 말이다. 사실을 왜곡하고, 폭력을 정당화하며, 스스로를 선동하는 모습이 유신적 사고, 그리고 지난 보수정권에서 창궐했던 일베적 사고이고 곧 친박 패권주의의 민낯이다.

헌법재판소의 판결로 드디어 친박정희 패권주의를 물리칠 시대가 왔다. 국민의 주권이 확고히 인정받는 진정한 민주주의 혁명이라 말할 수 있다. 민주화 이후에도 잔재하던 유신 잔재 세력을 말끔히 소탕할 기회가 온 것이다. 이제 대한민국의 역사적 흐름에 걸맞은 새로운 정권이 탄생해야 한다. 국민의 주권을 우선하고, 대한민국의 국익을 무엇보다 우선하는 제대로 된 정권을 간절히 바라는 바이다.

우연히 네이버 연예 기사를 통해 이와이 슌지 감독의 영화가 인터넷으로 개봉했다는 사실을 알게되었습니다. 촬영기간은 3일, 재밌게도 한국을 배경으로 배두나씨와 김주혁씨를 캐스팅 했더군요.


이와이 슌지 감독의 영화는 항상 챙겨보는 편입니다. 처음 그의 영화를 본 건 중학생때 일겁니다, 아마도. SBS에서 방영했었던 '러브레터'를 아주 푹 빠져 봤었던 기억이 납니다. 보통 영화관도 아니고 TV로 영화를 봤던 경험이 머릿속에 오래 기억되긴 쉽지 않은 일입니다. 하지만 그 '러브레터'를 아주 빠져들어서 봤다는 기억은 생생합니다. 가족들이 모두 거실에서 나란히 누워 자고 있고, 고요한 한 밤 중 그 옆에 저만 홀로 깨어 구식 브라운관 TV를 유심히 뚫어져라 보고 있는 장면이 사진처럼 머리에 남아있거든요. 가족들이 각자 방도 아니고 거실에 누워서 잤던걸 보니 이사온지 얼마 안된듯 합니다. 샷시도 없고, 새로산 침대도 아직 안들어와서 거실에 함께 누워 잤으니까요. 중학교 2학년때 이 집으로 이사왔으니 시기에 대한 기억은 확실할 겁니다, 아마도.

재밌는건 그때 '러브레터'를 본건 확실히 기억나는데 내용은 전혀 기억이 안난다는 겁니다. 확실히 전혀 졸지 않고 정말 재밌게 봤다는 기분은 나는데요. 이와이 슌지 특유의 아름다운 화면과 서정적인 음악이 계절적 분위기와 어울려 한 밤 중의 감성을 자극하지 않았나 생각해봅니다. 한창 사춘기였기에 그 감정은 더 풍부하게 다가왔을 지도요. 여튼 내용도 제대로 기억 안나는데도 아주 특별하고 긍정적인 기억으로 남아있습니다. 영화를 좋아하게 된 여러 계기중 하나의 사례로 꼽을수도 있겠네요.


본격적으로 그의 작품을 보게된 건 대학이후입니다. 그 때의 '러브레터'에 대한 내용이 무엇이었을까 하는 궁금증에 늦가을 즈음 날씨가 쌀쌀함을 넘어 추워질 무렵 대학 기숙사에서 혼자 봤었습니다. 아직 더위가 가시지도 않았는데 눈내리는 배경의 영화를 보기엔 뭔가 이상하니까요. 그리고 이후 그

의 주요 작품들은 거의 봤습니다. 하나와 앨리스, 4월 이야기, 스왈로우테일 버터플라이, 릴리슈슈의 모든것, 립반윙클의 신부까지.

그의 작품은 완전히 밝거나 혹은 어둡거나 둘 중 하나로 나뉘는 경우가 있는데 전 밝은쪽의 이야기를 더 좋아합니다. 밝은 영화에서 특히 이와이 슌지의 미적감각이 더 풍부하게 살아나는것 처럼 보이기 때문이죠. 특히 그의 영화에서 '따뜻한 빛'의 사용은 정말 포근하고 아늑한 느낌마저 주곤합니다.


4월 이야기



러브레터


소설을 보는 듯한 느낌도 좋습니다. 전형적인 기승전결의 영화지만 식상하지 않고, 자연스럽게 감정이 고조되는 그 부드러움 또한 좋습니다. 콕 집어 말하긴 어렵지만 그의 영화에선 일상의 복잡한 마음이 진정되고 감정이 해소되는 경험을 하게됩니다. 그래서 그의 영화는 챙겨보려 하는 편입니다.




'장옥의 편지'는 유투브의 '네슬레 시어터'라는 채널을 통해 개봉되었습니다. 아마도 커피를 만드는 네슬레 사에서 후원하는 채널이겠지요. 일본인을 주로 타겟으로 하는 채널로 보이는데 한국을 배경으로 한 영화를 만든것 부터 어떤 의미를 담고 있을지 사뭇 궁금해졌습니다.



영화는 15분에서 20분 가량의 4개의 이야기로 나눠져 있습니다. 내용은 한국의 며느리, 아내, 어머니로 살아가는 것에 대해 이야기를 하고자 하는 것 같습니다. 일본 또한 가부장적인 문화를 가진 사회임에도 한국을 배경으로 한 것은, 한국과 일본의 동질감과 국가적 경계를 넘어 해결해야 할 공동의 문제를 일본인들에게 이야기 하고자 하는게 아닐까 싶습니다. '장옥의 편지'는 극중에서도 등장하는 소재지만, 극 밖으로 나와 한국에서 일본으로 전하는 편지이기도 하지 않을까 생각해봅니다. 아마도 이러한 내용으로요.

"한국에서도 여성들은 힘든 삶을 살고 있습니다. 시어머니의 소유물이 되고, 남편의 소유물이 되는 것 말이지요. 커피 한 잔의 여유라도 갖는 꿈을 꾸었지만, 현실은 그러한 여성적 삶을 포기하고 며느리가 되고 아내가 되어라 합니다. 하지만 차츰 변하고 있어요. 가부장적인 사회는 점차 자기 반성을 통해 천천히 바뀌어 나가고 있습니다. 아직 직접적으로 사과의 말을 하지 못하고, 여성을 위한 도움이 아직 미숙하지만 그래도 차츰 더 바뀌어 나가겠지요. 일본은 어떠하신지요?"

사회적 이슈를 이야기하지만 그 것을 분노와 슬픔의 감정으로 연결시키기 보다는 희망과 즐거움으로 연결할 수 있음에 다시 한 번 고마움을 느낍니다. 비록 짧은 영화였지만 이와이 슌지만의 서정적인 메시지와 그만의 영상을 느낀 즐거운 한 시간이었습니다. 조만간 또 그의 영화를 볼 수 있길 간절히 바래봅니다.


장옥의 편지: https://www.youtube.com/watch?v=nzNl9MJjUMU&list=PLA_eLxzJ5UOnR8TtfkG82n39EtkRlvQSg&index=1

키를 비교하여 정렬하는 알고리즘

2차시간 정렬 알고리즘: 삽입정렬(Insertion Sort), 교환정렬(Exchange Sort), 선택정렬(Selection Sort)

Θ(n lg n) 정렬 알고리즘: 합병정렬(Merge Sort), 빠른정렬(Quick Sort), 힙정렬(Heap Sort)


키를 비교하지 않고 정렬하는 알고리즘: 기수정렬(Radix Sort)




기수정렬(radix sort)

순서를 매길 수 있다는 것 이외에 키에 대한 정보가 없는 경우, 앞서 알아본 키를 비교하는 방법 이외에 할수 있는 정렬방법은 없다.

기수 정렬은 키가 음이 아닌 10진수 정수라는 것을 알 때 사용할 수 있다. 자리수(digit)를 따라 분배하여 정렬하는 알고리즘이다.

정렬하려 하는 숫자가 3자리 숫자라 가정하면, 100의 자리에서 0..9까지 더미로 숫자를 분배할 수 있다. 이 안에서 다시 10의 자리에서 0..9까지 분배 하고 마지막으로 1의 자리에서 0..9까지 분배하면 자동적으로 정렬이 되게 된다.

따라서 이 알고리즘은 분배에 의한 정렬(sorting by distribution)이다.

숫자가 아니라 알파벳 또한 분배할 수 있다. 이 경우에는 0..9까지의 10개 더미가 아니라 a..z까지의 26개의 더미로 나눠서 분배해야 한다.


http://rightwayman2013.blogspot.kr/2010/09/algo-83-radix-sort.html



C++ 스타일 수도코드

// 아래는 연결된리스트의 구현에 필요한 노드의 선언이다.
struct nodetype
{
	keytype key;
	nodetype* link;
};

typedef nodetype* node_pointer;

// 아래는 알고리즘이다.
void radixsort ( node_pointer& marsterlist, int numdigits )
{
	index i;
	node_pointer list[0..9];

	for ( i = 1; i <= numdigits; i++ ) {
		distribute ( masterlist, list, i );
		coalesce( masterlist, list );
	}
}

void distribute ( node_pointer& masterlist, node list[], index i )
{
	index j;
	node_pointer p;

	for ( j = 0; j <= 9; j++ )
		list[j] = NULL;
	p = masterlist;
	whild ( p != NULL ) {
		j = p->key에서 i자리 값;
		p를 list[j]의 끝에 링크;
		p = p -> link;
	}
}

void coalesce ( node_pointer& masterlist, node list[] )
{
	index j;

	masterlist = NULL;
	for ( j = 0; j <= 9; j++ )
		list[j]에 있는 마디들을 masterlist의 끝에 링크;
}


Java 구현 코드

import main.Print;

public class Radix {

	public static node radixsort(node masterlist, int numdigits) {
		
		node[] list = new node[10];
		
		for (int i = 1; i <= numdigits; i++) {
			distribute(masterlist, list, i);
			
//			for(int j = 0; j < list.length; j++) {
//				node temp = list[j];
//				System.out.print(j + ":");
//				while (temp != null) {
//					System.out.print(" [" + temp.key + "]");
//					temp = temp.link;
//				}
//				System.out.println();
//			}
			
			masterlist = coalesce(masterlist, list);
//			int[] arr = masterlist.getResult();
//			Print.printArray(arr);
		}
		
		return masterlist;
	}
	
	private static void distribute(node masterlist, node[] list, int i) {
		
		int j;
		node p;
		
		for(j = 0; j <= 9; j++) {
			list[j] = null;
		}
		p = masterlist;
		while (p != null) {
			j = (int) ((p.key % Math.pow(10, i)) / Math.pow(10, (i-1)));
			node temp;
			
			if (list[j] == null) {
				temp = p;
				list[j] = temp;
			} else {
				temp = list[j];
				while(temp.link != null) {
					temp = temp.link;
				}
				temp.link = p;
				temp = temp.link;
				
			}
			
			p = p.link;
			temp.link = null;
		}
	}
	
	private static node coalesce(node masterlist, node[] list) {
		
		masterlist = null;
		node temp = null;
		for (int j = 0; j <= 9; j++) {
			if (list[j] != null) {
				if (masterlist == null) {
					masterlist = list[j];
					temp = masterlist;
				} else {
					temp.link = list[j];	
				}
				while (temp.link != null) {
					temp = temp.link;
				}
			}
		}
		
		return masterlist;
	}
	
	public static class node {
		public int key;
		public node link;
		
		public int[] getResult() {
			
			int[] result;
			int size = 1;
			
			node temp = link;
			while (temp != null) {
				temp = temp.link;
				size++;
			}
			
			result = new int[size];
			
			temp = link;
			for (int i = 0; i < size; i++) {
				if (temp != null) {
					if (i == 0) {
						result[i] = key;
					} else {
						result[i] = temp.key;
						temp = temp.link;
					}
				}
			}
			
			return result;
		}
	}
}

https://github.com/Stardust-kr/algorithm/blob/master/src/sort/Radix.java


중간에 주석은 테스트를 위한 출력 코드이다. 출력에 필요한 관련 클래스는 github에서 나머지 코드를 찾아보시라.


모든 경우 시간복잡도

단위연산: 비교연산이 없기 때문에 다른 연산을 찾아야 한다. coalesce에서 masterlist의 끝에 노드를 추가하는 연산, distribute에선s while루프의 일부 또는 전체를 단위연산으로 취급할 수 있다. 

입력크기: masterlist에서 정수의 개수 n, 각 정수에서 십진숫자의 최대 개수 numdigits

masterlist 전체를 처음부터 차례로 따라가려면 항상 distribute의 while루프를 n번 수행해야 한다. masterlist에 리스트를 모두 추가하려면 항상 coalesce의 for 루프를 10번 수행해야 한다. (여기서는 마지막 포인터도 두어, 위의 java 코드와는 달리 while루프 없이 한번에 저장할 수 있는 더 효율적인 알고리즘이라 하자)

이 프로시저는 radixsort에서 numdigits번 for문에 의해 호출된다.

따라서,

numdigitsn을 기준으로 한계값을 표현하기 때문에, 이 알고리즘은 Θ(n)이 아니다. numdigits값을 임의로 크게 하여 n을 기준으로, 임의로 큰 시간복잡도를 만들 수 있다. 10억 자리(numdigits)의 숫자 10개(n)을 정렬한다고 고려 하면 Θ(n^2) 시간이 걸린다. 보통은 numdigits이 훨씬 작다. 최선의 경우 시간 복잡도는 Θ(n lg n)이고, 보통은 최선의 경우에 수렴한다.


추가적인 저장장소 사용

masterlist와 더미를 나타내는 리스트에서 새로운 노드를 만들지 않는다. masterlist의 노드가 더미 리스트로 이동하고, 다시 masterlist로 정렬되는 방식이다. 다만 노드에서 key와 쌍이되는 link가 사용되기 때문에 Θ(n) 링크 만큼 추가 공간을 필요로 한다.




내용 출처

Foundations of Algorithms Using C++ Pseudocode 3rd Edition 알고리즘; Richard Neapolitan, Kumarss Naimipour; 도경구 역; 사이텍미디어



키를 비교하여 정렬하는 알고리즘

2차시간 정렬 알고리즘: 삽입정렬(Insertion Sort), 교환정렬(Exchange Sort), 선택정렬(Selection Sort)

Θ(n lg n) 정렬 알고리즘: 합병정렬(Merge Sort), 빠른정렬(Quick Sort), 힙정렬(Heap Sort)


키를 비교하지 않고 정렬하는 알고리즘: 기수정렬(Radix Sort)



합병정렬(merge sort)

정렬되지 않은 배열을 2개의 배열로 분할하고, 그 두 부분배열을 각각 정렬하고, 다시 합병하여 정렬된 배열로 만든다.

분할정복(divide-and-conquer) 절차

1. 분할: 배열을 n/2개 아이템을 가진 2개의 부분배열로 분할한다.

2. 정복: 정렬함으로써 각 부분배열을 정복한다(푼다). 배열이 충분히 작지 않으면 재귀 호출을 한다.

3. 통합: 부분배열에 대한 답들을 합병하여 하나의 정렬된 배열로 만든다.


C++ 스타일 수도코드

void mergesort ( int n, keytype S[] )
{
	if ( n > 1 ) {
		const int h = └h / 2┘, m = n - h;
		keytype U[1..h], V[1..m];
		copy S[1] through S[h] to U[1] through U[h];
		copy S[h+1] through S[n] to V[1] through V[m];
		mergesort(h ,U);
		mergesort(m, V);
		merge(h, m, U, V, S);
	}
}

void merge ( int h, int m , const keytype U[], const keytype V[], keytype S[] )
{
	index i, j, k;

	i = 1; j = 1; k = 1;
	while ( i <= h && j <= m ) {
		if ( U[i] < V[j] ) {
			S[k] = U[i];
			i++;
		}
		else {
			S[k] = V[j];
			j++;
		}
		k++;
	}
	if ( i > h )
		copy V[j] through V[m] to S[k] through S[h+m];
	else
		copy U[i] through U[h] to S[k] through S[h+m];
}


Java 구현 코드

public class Merge {
	
	public static void mergesort (int n, int[] S) {
		
		if(n > 1) {
			final int h = n / 2;
			final int m = n - h;
			int[] U = new int[h];
			int[] V = new int[m];
			
			for(int i = 0; i < h; i++) {
				U[i] = S[i];
			}
			
			for(int i = 0; i < m; i++) {
				V[i] = S[h+i];
			}
			
			mergesort(h, U);
			mergesort(m, V);
			merge(h, m, U, V, S);
		}
	}
	
	public static void merge(int h, int m, final int[] U, final int[] V, int[] S) {
		int i, j, k;	// index
		
		i = 0;
		j = 0;
		k = 0;
		
		while(i < h && j < m) {
			if(U[i] < V[j]) {	// 단위연산
				S[k] = U[i];
				i++;
			} else {
				S[k] = V[j];
				j++;
			}
			k++;
		}
		
		if(i >= h) {
			while(j < m) {
				S[k] = V[j];
				j++;
				k++;
			}
		} else {
			while(i < h) {
				S[k] = U[i];
				i++;
				k++;
			}
		}
	}
}

https://github.com/Stardust-kr/algorithm/blob/master/src/sort/Merge.java


키 비교횟수의 최악의 경우 시간복잡도(merge)

· 단위연산: U[i]와 V[j]의 비교

· 입력크기: 두 입력 배열 아이템의 개수, h와 m

최악의 경우는 i와 j가 while 루프 안에서 최대에 도달한 상태에서 빠져나올 때이다. 즉 i가 h에 도달하고, j가 (m-1)에 도달하거나, 반대로 j가 m에 도달하고 i가 (h-1)에 도달한 상태에서 while 루프를 빠져나오는 경우이다.


키 비교횟수의 최악의 경우 시간복잡도(mergesort)

· 단위연산: merge에서 일어나는 비교연산

· 입력크기: 배열 S의 아이템의 수, n

총 비교횟수는 mergesort(h, U)와 mergesort(m, V)를 재귀호출 하는데 수행되는 비교연산의 횟수와 merge를 호출하는데 수행되는 비교연산의 횟수의 합이다.


n이 2의 거듭제곱인 경우 다음과 같다.


입력크기 n이 1인 경우에는 if 문을 통과하지 못하고 merge는 행해지지 않으므로 W(1)은 0이다.


위 재현식의 해를 구하면 아래와 같다. 해법은 출처의 도서를 참고하자.



추가적인 저장장소 사용

mergesort에서 분할된 배열 U, V를 새롭게 선언하여 사용한다. 첫 mergesort에서 입력 크기 n의 절반인 n/2 크기의 배열 두개가 생성된다. 따라서 n 크기의 저장장소가 새로이 필요하다. 다음 mergesort가 호출된다(코드상에서는 U배열에 대한 mergesort가 수행된다). 이 경우에는 n/4크기의 배열 두개가 생성되므로 n/2 크기의 저장장소가 필요하며, 다음 재귀호출에서는 n/4 크기의 배열이 필요하다. 따라서 추가적인 저장장소의 크기는 다음과 같다.

따라서 2n이다.


위의 알고리즘보다 추가적인 저장장소를 덜 사용하는 개선된 합병정렬을 알아보자.


C++ 스타일 수도코드

void mergesort2 ( index low, index high )
{
	index mid;

	if ( low < high ) {
		mid = └(low + high) / 2┘;
		mergesort2(low, mid);
		mergesort2(mid + 1, high);
		merge2(low, high);
	}
}

void merge2 ( index low, index mid, index high )
{
	index i, j, k;
	keytype U[low..high];

	i = low; j = mid + 1; k = 0;
	while ( i <= mid && j <= high ) {
		if ( S[i] < S[j] ) {
			U[k] = S[i];
			i++;
		}
		else {
			U[k] = S[j];
			j++;
		}
		k++;
	}
	if ( i > mid )
		move S[j] through S[high] to U[k] through U[high];
	else
		move S[i] through s[mid] to U[k] through U[high];

	move U[low] through U[high] to S[low] through S[high];
}


Java 구현 코드

public class Merge2 {

	private int[] S;
	
	public Merge2(int[] S) {
		this.S = new int[S.length];
		
		for(int i = 0; i < S.length; i++) {
			this.S[i] = S[i];
		}
	}
	
	public void mergesort2(int low, int high) {
		int mid;
		
		if(low < high) {
			mid = (low + high) / 2;
			mergesort2(low, mid);
			mergesort2(mid+1, high);
			merge2(low, mid, high);
		}
	}
	
	private void merge2(int low, int mid, int high) {
		int i, j, k;
		int[] U = new int[high - low + 1];	// 추가적인 메모리를 사용하는 지역배열
		
		i = low;
		j = mid + 1;
		k = 0;
		
		while(i <= mid && j <= high) {
			if(S[i] < S[j]) {
				U[k] = S[i];
				i++;
			} else {
				U[k] = S[j];
				j++;
			}
			
			k++;
		}
		
		if(i > mid) {
			while(j <= high) {
				U[k] = S[j];
				j++;
				k++;
			}
		} else {
			while(i <= mid) {
				U[k] = S[i];
				i++;
				k++;
			}
		}
		
		for(int x = 0; x < U.length; x++) {
			S[low + x] = U[x];
		}
	}
}

https://github.com/Stardust-kr/algorithm/blob/master/src/sort/Merge2.java


위 코드는 S 배열이 전역변수로 선언되어 있다. 재귀호출을 하여도 동일한 배열을 사용하기 때문에 파라미터로 같은 값이 계속 넘어가기에 굳이 넘겨줄 필요가 없기 때문이다. 자바코드를 구현할 때에는 배열을 멤버변수로 설정하여 생성자 설정시 배열을 설정하고 메서드를 호출할 수 있도록 하였다. 아니면 이 전 mergesort 처럼 배열을 직접 넘겨줘도 무방하다.

위와 같이 구현하므로써 merge2가 호출될 때마다 배열이 생성되고 다시 삭제된다. 가장 아래에 1개씩으로 분할되었을 때는 크기가 2인 배열이 생성되고 다시 해제된다. 합병하는 과정이서 최상단에 도달했을때 입력크기인 n만큼의 배열이 생성된다. 따라서 추가적인 저장장소 사용은 n이다.


동적계획법을 사용한 합병정렬

재귀 구현시 필요한 스택연산의 비용부담을 피할 수 있는 방법이다. 앞서 알고리즘이 분할정복법에 기반한 하향식(top-down) 방식이라면 이 방식은 상향식(bottom-up) 합병정렬 알고리즘 구현이다.


C++ 스타일 수도코드

void mergesort3( int n, keytype S[] )
{
	int m;
	index low, mid, high, size;
	m = 2^┌lg n┐;
	size = 1;
	repeat ( lg m times ) {
		for ( low = 1; low <= m - 2*size + 1; low = low + 2*size ) {
			mid = low + size - 1;
			high = minimum(low + 2*size - 1, n);
			merge3(low, mid, high, S);
		}
		size = 2 * size;
	}
}

void merge3( int low, int mid, int high, int[] S )
{
	// merge2와 구현 동일
}


Java 구현 코드

public class Merge3 {
	
	public static void mergesort3(int n, int[] S) {
		int size = 1;
		int m = (int) Math.pow(2, Math.ceil(Math.log(n)/Math.log(2)));
		
		for(int i = 0; i < (Math.log(m)/Math.log(2)); i++) {
			for (int low = 0; low < m - (2*size) + 1; low = low + (2*size)) {
				int mid = low + size - 1;
				int high = ((low + (2*size) - 1) > n - 1 ? n - 1 : (low + (2*size) - 1));
				merge3(low, mid, high, S);
			}
			
			size = 2 * size;
		}
	}
	
	public static void merge3(int low, int mid, int high, int[] S) {
		
		if(low < high && mid < high) {
			
			int i, j, k;
			int[] U = new int[high - low + 1];	// 추가적인 메모리를 사용하는 지역배열
			
			i = low;
			j = mid + 1;
			k = 0;
			
			while(i <= mid && j <= high) {
				if(S[i] < S[j]) {
					U[k] = S[i];
					i++;
				} else {
					U[k] = S[j];
					j++;
				}
				
				k++;
			}
			
			if(i > mid) {
				while(j <= high) {
					U[k] = S[j];
					j++;
					k++;
				}
			} else {
				while(i <= mid) {
					U[k] = S[i];
					i++;
					k++;
				}
			}
			
			for(int x = 0; x < U.length; x++) {
				S[low + x] = U[x];
			}
		}
	}
}

https://github.com/Stardust-kr/algorithm/blob/master/src/sort/Merge3.java


연결된 리스트를 사용한 합병정렬

합병정렬에서 합병시 키를 교환하는 오버헤드를 줄이기 위해 연결된 리스트를 사용할 수도 있다. 특히 정렬하고자 하는 데이터가 많아질 수록 추가적인 저장장소 사용량을 줄일 수 있다. 실제 데이터를 교환하지 않고 연결된 리스트 노드의 링크만 바꿔서 표기하면 되기 때문이다.

아래 알고리즘은 배열에 기반한 연결된 리스트 구현이다. 노드의 링크는 배열의 인덱스를 저장하여 다른 노드를 가리키게 된다.


C++ 스타일 수도코드

void mergesort4( index low, index high, index& mergedlist)
{
	index mid, list1, list2;

	if (low == high) {
		mergedlist = low;
		S[mergedlist].link = 0;
	}
	else {
		mid = └(low + high) / 2┘;
		mergesort4(low, mid, list1);
		mergesort4(mid + 1, high, list2);
		merge4(list1, list2, mergedlist)'
	}
}

void merge4( index list1, index list2, index& mergedlist )
{
	index lastsorted;

	if ( S[list1].key < S[list2].key ) {
		mergedlist = list1;
		list1 = S[list1].link;
	}
	else {
		mergedlist = list1;
		list1 = S[list2].link;
	}
	lastsorted = mergedlist;
	while ( list1 != 0 && list2 != 0 )
		if ( S[list1].key < S[list2].key ) {
			S[lastsorted].link = list1;
			lastsorted = list1;
			list1 = S[list1].link;
		}
		else {
			S[lastsorted].link = list2;
			lastsorted = list2;
			list2 = S[list2].link
		}
	if ( list1 == 0 )
		S[lastsorted].link = list2;
	else
		S[lastsorted].link = list1;
}


Java 구현 코드

public class Merge4 {
	
	private node[] S;
	
	public Merge4(node[] S) {
		this.S = S;
	}

	public int mergesort4(int low, int high, int mergedlist) {
		
		if(low == high) {
			mergedlist = low;
			S[mergedlist].link = -1;
		} else {
			int mid = (low + high) / 2;
			int list1 = mergesort4(low, mid, low);
			int list2 = mergesort4(mid + 1, high, mid + 1);
			mergedlist = merge4(list1, list2, mergedlist);
		}
		
		return mergedlist;
	}
	
	private int merge4(int list1, int list2, int mergedlist) {
		
		int lastsorted;
		
		if (S[list1].key < S[list2].key) {
			mergedlist = list1;
			list1 = S[list1].link;
		} else {
			mergedlist = list2;
			list2 = S[list2].link;
		}
		lastsorted = mergedlist;
		
		while (list1 != -1 && list2 != -1) {
			if (S[list1].key < S[list2].key) {
				S[lastsorted].link = list1;
				lastsorted = list1;
				list1 = S[list1].link;
			} else {
				S[lastsorted].link = list2;
				lastsorted = list2;
				list2 = S[list2].link;
			}
		}
		if (list1 == -1) {
			S[lastsorted].link = list2;
		} else {
			S[lastsorted].link = list1;
		}
		
		return mergedlist;
	}
	
	public static class node {
		public int key;
		public int link;
	}
}

https://github.com/Stardust-kr/algorithm/blob/master/src/sort/Merge4.java


자바는 call by value이기 때문에 &와 같은 alias 타입으로 파라미터 전달하는 것을 지원하지 않으므로 C++스타일 수도코드와는 달리 리턴 타입의 메소드를 선언하여 작성하였다. 위의 알고리즘을 통과한 배열을 인덱스 순서대로 찍으면 당연히 그대로 출력되지만, mergesort4 메서드를 호출하여 반환된 인덱스를 시작노드로 하여 노드 안의 link를 따라 출력하면 정렬된 형태로 출력하게 된다.


위 알고리즘의 경우 추가적인 저장장소는 key가 아닌 link를 저장하기 위한 변수가 사용되므로 Θ(n)만큼 필요하다. 그 외에 node를 옮기기 위한 새로운 노드나 배열을 만들지 않는다.

또한 레코드 지정을 하지 않고 link의 값만 바꾸기 때문에 레코드 지정횟수의 시간복잡도는 0이다. 레코드를 서로 이웃한 배열 슬롯에 순서대로 놓을 필요가 있는 경우에도 Θ(n)으로 줄인다.



빠른정렬(quick sort)

임의의 아이템을 pivot으로 설정하고(보통 가장 앞에 있는 아이템), 이 pivot을 기준으로 작은 아이템은 앞으로, 큰 아이템은 뒤로 보내고 다시 분할된 아이템들을 기준으로 정렬하는 방법이다.


C++ 스타일 수도코드

void quicksort ( index low, index high )
{
	index pivotpoint;

	if ( high > low ) {
		partition( low, high, pivotpoint );
		quicksort( low, pivotpoint - 1 );
		quicksort( pivotpoint + 1, high );
	}
}

void partition ( index low, index high, index& pivotpoint )
{
	index i, j;
	keytype pivotitem;

	pivotitem = S[low];
	j = low;
	for ( i = low + 1; i <= high; i++ )
		if ( s[i] < pivotitem ) {
			j++;
			exchange S[i] and S[j];
		}
	pivotpoint = j;
	exchange S[low] and S[pivotpoint];
}


Java 구현 코드

public class Quick {

	private int[] S;
	
	public Quick(int[] S) {
		this.S = S;
	}
	
	public void quicksort(int low, int high) {
		int pivotpoint;
		if(high > low) {
			pivotpoint = partition(low, high);
			quicksort(low, pivotpoint - 1);
			quicksort(pivotpoint + 1, high);
		}
	}
	
	private int partition(int low, int high) {
		int i, j;
		int pivotitem;
		int pivotpoint;
		int temp;
		
		pivotitem = S[low];
		j = low;
		
		for(i = low + 1; i <= high; i++) {
			if(S[i] < pivotitem) {	// 단위연산
				j++;
				
				temp = S[i];
				S[i] = S[j];
				S[j] = temp;
			}
		}
		
		pivotpoint = j;
		temp = S[low];
		S[low] = S[pivotpoint];
		S[pivotpoint] = temp;
		
		return pivotpoint;
	}
}

https://github.com/Stardust-kr/algorithm/blob/master/src/sort/Quick.java


키 비교횟수의 모든 경우 시간복잡도(partition)

· 단위연산: S[i]와 pivotitem의 비교

· 입력크기: n = high - low + 1

첫 번째 아이템을 제외한 모든 아이템이 항상 비교된다.


키 비교횟수의 최악의 경우 시간복잡도(quicksort)

· 단위연산: partition에서 일어나느 비교연산

· 입력크기: 배열 S의 아이템의 수, n

최악의 경우는 내림차순 또는 오름차순 형태로 이미 정렬되어 있는 경우에 해당한다. 정렬된 경우 분할시 한쪽은 크기가 0이고 나머지 한쪽은 크기가 (n-1)인 배열로 쪼개지기 때문에 재귀호출횟수가 그만큼 늘어나게 된다.

따라서,

W(0) = 0 이므로 재현식은 아래와 같다.


위 재현식의 해를 구하면 아래와 같다. 해법은 출처의 도서를 참고하자.


키 비교횟수의 평균의 경우 시간복잡도(quicksort)

· 단위연산: partition에서 일어나느 비교연산

· 입력크기: 배열 S의 아이템의 수, n

배열에 있는 숫자들이 위치할 확률이 다르지 않으므로 모두 동등한 확률을 갖는다고 가정한다. 그러므로 partition이 넘겨주는 pivotpoint 값은 1부터 n까지의 어떤 수가 될 확률이 모두 같다. 분포가 다른 경우(예를 들어 사람의 이름을 정렬하는 경우, 희귀한 이름과 흔한 이름간의 분포가 다르기에 확률도 달라진다) 적용할 수 없다.

(1) - (2)를 하면 아래와 같다.

다음과 같이 놓으면

아래와 같은 재현식이 된다.

위 재현식의 해를 구하면 아래와 같다. 해법은 출처의 도서를 참고하자.

다신 원래의 A(n)으로 치환하면 평균의 경우 시간복잡도는 아래와 같다.


추가적인 저장장소 사용

합병정렬과는 달리 추가적인 배열이 필요가 없다. 하지만 첫 부분배열을 정렬하는 동안, 다른 부분배열의 처음과 마지막 인덱스는 활성 레코드 스택에 저장되어야 하기 때문에 제자리정렬이 아니다.

또한 합병정렬과 달리 정확히 반으로 분할된다는 보장이 없기 때문에 한쪽은 0의 크기로, 한쪽은 (n-1)크기로 분할된다면 최악의 경우 추가적인 저장장소 사용량은 Θ(n)이다.



힙정렬(heap sort)

힙(heap)이라는 자료구조를 이용하여 정렬하는 방법이다. 힙정렬에 앞어서 관련된 자료구조를 잠깐 짚고 넘어가자.


마디의 깊이: 뿌리마디(root)에서 그 마디(node)로 가는 유일한 경로상에 있는 이음선(edge)의 개수

트리의 깊이(depth): 트리에 속하는 모든 마디의 깊이 중 최대값

잎마디(leaf): 자식마디가 없는 마디

내부마디: 최소한 하나의 자식마디를 가진 마디. 즉, 잎마디가 아닌 모든 마디


완전한 이진 트리(complete binary tree)

· 내부마디는 모두 자식마디가 2개 있다.

· 잎마디는 모두 깊이가 d이다.

http://doctrina.org/maximum-height-of-red-black-tree.html



실질적으로 완전한 이진 트리(essentially complete binary tree)

· (d - 1)의 깊이까지는 완전한 이진 트리이다.

· 깊이가 d인 마디는 모두 왼쪽 끝으로 모여 있다.

http://apprize.info/science/algorithms/7.html


참고 도서에서의 표현과 달리 완전한 이진 트리포화 이진 트리(fully binary tree)로, 실질적으로 완전한 이진 트리완전한 이진 트리로 설명하는 경우가 더 많은듯 보인다. 책에서는 이렇게 설명하였으니 표현대로 써 놓았으나 이 표현을 알아두는 것도 좋을 듯 하다.


http://cs.stackexchange.com/questions/54171/is-a-balanced-binary-tree-a-complete-binary-tree

http://cs.stackexchange.com/questions/54171/is-a-balanced-binary-tree-a-complete-binary-tree


힙(heap)

· 마디에 저장된 값은 순서가능집합(ordered set: 순서를 매길 수 있는 원소로 구성된 집합)에서 온다.

· 각 마디에 저장된 값은 그의 자식마디에 저장된 값보다 크거나 같다. 이를 힙 성질(heap property)이라고 한다.


http://oniondev.egloos.com/288205


힙정렬은 뿌리노드에 있는 키를 제거하고, 바닥마디에 있는 키로 바꾼 뒤, 힙 성질을 유지하도록 트리의 변화를 주는 방식을 반복하므로써 수행할 수 있다.

즉, 힙정렬을 위해서는 힙이 힙 성질을 유지할 수 있도록 하는 메소드(siftdown), 뿌리마디에서 키를 제거하고 바닥마디의 값을 가져오는 메소드(root), 뿌리마디에서 제거한 키를 배열 S에 정렬하는 메소드(removekeys), 그리고 맨 처음 정렬되지 않은 값들을 heap으로 만드는 메소드(makeheap)이 필요하다.

아래에서는 힙 자료구조를 만들기 위해 배열을 사용할 것이다.


C++ 스타일 의사코드

// 아래는 heap 자료 구조이다.
struct heap{
	keytype S[1..n];
	int heapsize;
};

void siftdown( heap& H, index i )
{
	index parent, largerchild;
	keytype siftkey;
	bool spotfound;

	siftkey = H.S[i];
	parent = i;
	spotfound = false;
	while (2*parent <= H.heapsize && !spotfound ) {
		if (2*parent < H.heapsize && H.S[2*parent] < H.S[2*parent + 1])
			largerchild = 2*parent + 1;
		else
			largerchild = 2*parent;
		if ( siftkey < H.S[largerchild] ) {
			H.S[parent] = H.S[largerchild];
			parent = largerchild;
		}
		else
			spotfound = true;
	}
	H.S[parent] = siftkey;
}

keytype root ( heap& H )
{
	keytype keyout;

	keyout = H.S[1];
	H.S[1] = H.S[heapsize];
	H.heapsize = H.heapsize - 1;
	siftdown(H, 1);
	return keyout;
}

void remotekeys ( int n, heap& H, keytype S[] )
{
	index i;

	for ( i = n; i >= 1; i-- )
		S[i] = root(H);
}

void makeheap ( int n, heap& H )
{
	index i;

	H.heapsize = n;
	for ( i = └n/2┘; i >= 1; i-- )
		siftdown(H, i);
}

// 아래는 힙정렬 메소드
void heapsort ( int n, heap& H )
{
	makeheap (n, H);
	removekeys (n, H, H.S);
}


Java 구현 코드

public class Heap {

	private int[] S;
	private int heapsize;
	
	public Heap(int[] S) {
		
		heapsize = S.length;
		this.S = new int[heapsize + 1];
		for(int i = 0; i < heapsize + 1; i++) {
			if(i == 0) {
				this.S[0] = 0;
			} else {
				this.S[i] = S[i-1];
			}
		}
	}
	
	private void siftdown(int i) {
		
		int parent, largerchild;
		int siftkey;
		boolean spotfound;
		
		siftkey = S[i];
		parent = i;
		spotfound = false;
		while (2*parent <= heapsize && !spotfound) {
			if (2*parent < heapsize && S[2*parent] < S[2*parent+1]) {
				largerchild = 2*parent+1;
			} else {
				largerchild = 2*parent;
			}
			
			if (siftkey < S[largerchild]) {
				S[parent] = S[largerchild];
				parent = largerchild;
			} else {
				spotfound = true;
			}
			
		}
		
		S[parent] = siftkey;
	}
	
	private int root() {
		
		int keyout;
		
		keyout = S[1];
		S[1] = S[heapsize];
		heapsize = heapsize - 1;
		siftdown(1);
		
		return keyout;
	}
	
	private void removekeys() {
		
		for (int i = S.length-1; i >= 1; i--) {
			S[i] = root();
		}
	}
	
	private void makeheap() {
		
		for (int i = (S.length-1)/2; i >= 1; i--) {
			siftdown(i);
		}
	}
	
	public void heapsort() {
		
		makeheap();
		removekeys();
	}
	
	public int[] getResult() {
		
		int[] result = new int[S.length - 1];
		for (int i = 1; i < S.length; i++) {
			result[i-1] = S[i];
		}
		
		return result;
	}
}

https://github.com/Stardust-kr/algorithm/blob/master/src/sort/Heap.java


힙정렬 알고리즘 수도코드를 실 구현코드로 작성시 문제가 되는건, 알고리즘에서는 배열을 인덱스 1부터 시작하는 배열로 보는 반면에 구현 코드는 0부터 시작하기에 이를 맞춰주는데 어려움이 생긴다. 이전에 구현했던 다른 알고리즘은 그저 (-1) 해주므로써 문제가 해결되지만 힙정렬의 경우는 배열을 힙구조로 사용하기 위해 해당 인덱스의 *2를 왼쪽 자식노드, *2+1을 오른쪽 자식구조로 판단하는 계산을 하기 때문에 조금 더 머리를 써야 한다. 그렇게 복잡하게 구현할 경우 추후에 구현 코드를 이해하는데 어렵기 때문에, 차라리 아래와 같이 0번째 인덱스를 비운 배열을 사용하여 알고리즘을 구현하였다.

수도코드와는 달리 메소드들을 객체에 종속된 메소드로 구현하여 생성자에서 정렬하고자 하는 자료를 입력받은 후, 전역변수처럼 값을 사용하였다.


http://blog.naver.com/PostView.nhn?blogId=redwave102&logNo=80074139499


키 비교횟수의 최악의 경우 시간복잡도(heapsort)

· 단위연산: siftdown 프로시저에서 키의 비교

· 입력크기: 정렬할 키의 개수, n

프로시저 makeheap과 removekeys는 둘 다 siftdown을 호출한다. 따라서 이 두 프로시저를 따로 분석하여야 한다. 분석은 출처 도서를 참고해주시기 바란다.

n이 2의 거듭제곱일 때,

makeheap에 의해 행해지는 최대 비교횟수: 2(n - 1)

removekeys에 의해 행해지는 최대 비교횟수: 2nlgn - 4n + 4

힙정렬에서 키의 최대 비교횟수: 2(n - 1) + 2nlgn - 4n + 4 = (2nlgn - n + 1)  2nlgn


키 비교횟수의 평균의 경우 시간복잡도(heapsort)


레코드 지정횟수의 최악의 경우 시간복잡도(heapsort)



추가적인 저장장소 사용

힙정렬은 제자리정렬이다. 따라서 Θ(1)이다.



합병정렬, 빠른정렬, 힙정렬 비교

 알고리즘

키의 비교 

레코드의 배정 

추가적인 저장장소 사용 

 합병정렬2

 

 


 합병정렬4

 

 

 

 빠른정렬

(개량된 알고리즘)

 

 

 

 힙정렬

 

 

 제자리


빠른정렬과 힙정렬

- 키의 비교와 레코드 배정에서 평균적으로 빠른정렬보다 나쁘다.

- 빠른정렬의 추가적인 공간 사용량은 최소이므로 빠른정렬이 선호된다.


합병정렬와 빠른정렬

- 전체 입력 레코드 배열 크기 만큼의 배열을 추가적으로 사용하고, 또한 합병정렬은 빠른정렬이 평균적으로 하는 것보다 레코드 지정횟수가 항상 3배 가량 많기 때문에, 빠른정렬이 평균적으로 피의 비교횟수가 약간 많음에도 합병정렬보다 선호된다.

- 연결된리스트를 사용한 합병정렬(합병정렬4)은 이와 관련된 단점이 거의 모두 제거한다. 유일한 단점은 각 키에 대응되는 추가적인 링크를 사용하기 때문에 Θ(n)만큼의 공간을 사용한다는 것이다.




내용 출처

Foundations of Algorithms Using C++ Pseudocode 3rd Edition 알고리즘; Richard Neapolitan, Kumarss Naimipour; 도경구 역; 사이텍미디어

키를 비교하여 정렬하는 알고리즘

2차시간 정렬 알고리즘: 삽입정렬(Insertion Sort), 교환정렬(Exchange Sort), 선택정렬(Selection Sort)

Θ(n lg n) 정렬 알고리즘: 합병정렬(Merge Sort), 빠른정렬(Quick Sort), 힙정렬(Heap Sort)


키를 비교하지 않고 정렬하는 알고리즘: 기수정렬(Radix Sort)



삽입정렬(insertion sort)

이미 정렬된 배열에 레코드를 삽입하여 정렬하는 알고리즘

즉, 정렬되지 않은 배열에서 키를 순차적으로 선택하여 오름차순으로 정렬중인 앞쪽 부분의 배열에 삽입하는 알고리즘


C++ 스타일 수도코드

void insertionsort (int n, keytype S[])
{
	index i, j;
	keytype x;

	for ( i = 2; i <=; i++ ) {
		x = S[i];
		j = i - 1;
		while ( j > 0 && S[j] > x ) {
			S[j + 1] = S[j];
			j--;
		}
		S[j + 1] = x;
	}
}


Java 구현 코드

public class Insertion {

	public static void insertionsort(int n, int[] S) {
		
		for (int i = 1; i < n; i++) {
			int x = S[i];				// 레코드 지정횟수의 최악의 경우 시간복잡도의 단위연산
			int j = i - 1;
			
			while (j >= 0 && S[j] > x) {	// S[j] > x 가 키 비교횟수의 최악의 경우 시간복잡도의 단위연산
				S[j+1] = S[j];			// 레코드 지정횟수의 최악의 경우 시간복잡도의 단위연산
				j--;
			}
			
			S[j+1] = x;				// 레코드 지정횟수의 최악의 경우 시간복잡도의 단위연산
		}
	}
}

https://github.com/Stardust-kr/algorithm/blob/master/src/sort/Insertion.java


키 비교횟수의 최악의 경우 시간복잡도

· 단위연산: S[j]와 x의 비교

· 입력크기: 정렬할 키의 개수 n

while 루프를 j가 (-1)이 될 때까지 반복하고 빠져 나가는 경우가 최악.

&& 연산에서 앞의 조건이 false이면 뒤의 조건은 검사하지 않으므로 비교는 j번, 즉 (i-1)번 이루어진다.

i값은 배열의 첫 번째 인덱스를 제외하고 마지막 인덱스 까지 검사하므로 (n-1)개가 된다.

· 총 비교횟수:


레코드 지정횟수의 최악의 경우 시간복잡도

· 단위연산: x에 S[i]를 지정, S[j+1]에 S[j]를 지정, S[j+1]에 x를 지정

· 입력크기: 정렬할 키의 개수 n

while 루프를 j가 (-1)이 될 때까지 반복하고 빠져 나가는 경우가 최악. (i-1)번 이루어진다.

여기에 while 루프 전에 x에 S[i]를 지정하는 값이 고정적으로 1번, 루프를 벗어난 후에 S[j+1]에 x를 지정하는 값이 고정적으로 1번 추가되어 총 while 루프 한번에 (i-1)+2번 키 지정을 하게된다.

· 총 비교횟수:


추가적인 저장장소 사용

배열 내에서 정렬이 일어나므로 제자리 정렬에 해당한다.

따라서 추가적인 저장장소 사용량은  Θ(1)이다.




교환정렬(exchange sort)

정렬되지 않은 배열에서 선택된 인덱스의 키와 나머지 키를 비교하여 자신보다 낮은 경우 계속해서 교환하여 가장 작은 키를 인덱스 순차적으로 위치시키는 알고리즘.

예를 들어 1부터 9까지 아홉개의 숫자가 무작위로 섞여있는 배열이 있는 경우 0번째 인덱스에 있는 키를 선택한 후, 나머지 1부터 8까지 인덱스에 있는 키와 모두 비교하여 최소값인 1이 맨 앞에 오게 한다. 1번째 인덱스에도 마찬가지로 나머지 2부터 8까지 인덱스에 있는 키와 모두 비교하여 최소값 2가 오게 한다.


C++ 스타일 수도코드

void exchangesort (int n, keytype S[])
{
	index i, j;
	for ( i = 1; i <= n - 1; i++ )
		for ( j = i + 1; j <= n; j++ )
			if ( S[j] < S[i] )
				exchange S[i] and S[j];
}


Java 구현 코드

public class Exchange {

	public static void exchangesort(int n, int[] S) {
		
		for(int i = 0; i < n - 1; i++) {
			for(int j = i + 1; j < n; j++) {
				if(S[i] > S[j]) {			// 키 비교횟수의 모든 경우 시간복잡도의 단위연산
					int temp = S[i];		// 레코드 지정횟수의 최악의 경우 시간복잡도의 단위연산
					S[i] = S[j];		// 레코드 지정횟수의 최악의 경우 시간복잡도의 단위연산
					S[j] = temp;		// 레코드 지정횟수의 최악의 경우 시간복잡도의 단위연산
				}
			}
		}
	}
}

https://github.com/Stardust-kr/algorithm/blob/master/src/sort/Exchange.java


키 비교횟수의 모든 경우 시간복잡도

· 정렬되지 않은 배열이 어떻게 존재하여도 항상 모든 배열의 내용을 비교하므로 모든 경우 시간복잡도를 계산한다.

· 단위연산: S[i]와 S[j]의 비교

입력크기: 정렬할 키의 개수 n

변수 i에 대한 for 루프는 (n-1)만큼 반복한다.

i 루프가 첫 번째 수행될 때 j 루프는 (n-1)번, 두 번째에는 (n-2)번, ... , 마지막에는 1번 수행한다.


레코드 지정횟수의 최악의 경우 시간복잡도

· 단위연산: S[i]와 S[j], temp 상호간 지정

· 입력크기: 정렬할 키의 개수 n

비교할 때마다 항상 교환하는게 최악의 경우이므로 모든 경우 시간복잡도에 레코드 지정횟수을 곱한 것(x3)과 같다.


추가적인 저장장소 사용

배열 내에서 정렬이 일어나므로 제자리 정렬이고 추가적인 저장장소 사용량은 Θ(1)이다.




선택정렬(selection sort)

교환정렬을 약간 변형한 알고리즘으로 교환정렬의 단점을 제거하였다.

자신보다 작은 값을 찾으면 키값을 교환했던 교환정렬과는 달리, 키의 인덱스를 저장하는 변수를 이용하여 가장 가장 작은 키의 인덱스를 저장해 두었다가 반복이 끝나면 마지막에 가장 작은 키와 교환한다.

즉, 교환정렬에서 교환으로 인한 오버헤드를 줄인다.


순서대로 레코드를 선택하여 정렬하는 알고리즘을 모두 통칭하여 선택정렬이라 한다.

따라서 교환정렬이나 힙정렬도 선택정렬에 해당한다.


C++ 스타일 수도코드

void selectionsort ( int n, keytype S[] )
{
	index i, j, smallest;
	for ( i = 1; i <= n - 1; i++ ) {
		smallest = i;
		for ( j = i + 1; j <= n; j++ )
			if ( S[j] < S[smallest] )
				smallest = j;
		exchange S[i] and S[smallest];
	}
}


Java 구현 코드

public class Selection {

	public static void selectionsort(int n, int[] S) {
		
		for (int i = 0; i < n - 1; i++) {
			int smallest = i;
			
			for (int j = i + 1; j < n; j++) {
				if (S[j] < S[smallest]) {	// 키 비교횟수의 모든 경우 시간복잡도의 단위연산
					smallest = j;
				}
			}
			
			int temp = S[i];				//
			S[i] = S[smallest];			// 레코드 지정횟수의 모든 경우 시간복잡도의 단위연산
			S[smallest] = temp;			//
		}
	}
}

https://github.com/Stardust-kr/algorithm/blob/master/src/sort/Selection.java


키 비교횟수의 모든 경우 시간복잡도

· 정렬되지 않은 배열이 어떻게 존재하여도 항상 모든 배열의 내용을 비교하므로 모든 경우 시간복잡도를 계산한다.

· 단위연산: S[j]와 S[smallest]의 비교

입력크기: 정렬할 키의 개수 n

변수 i에 대한 for 루프는 (n-1)만큼 반복한다.

i 루프가 첫 번째 수행될 때 j 루프는 (n-1)번, 두 번째에는 (n-2)번, ... , 마지막에는 1번 수행한다.


레코드 지정횟수의 모든 경우 시간복잡도

· 단위연산: S[i]와 S[j], temp 상호간 지정

· 입력크기: 정렬할 키의 개수 n

비교횟수와 상관없이 (i-1)번 반복이 일어난다. 교환을 위한 상호 지정은 3번 일어난다.


추가적인 저장장소 사용

배열 내에서 정렬이 일어나므로 제자리 정렬이고 추가적인 저장장소 사용량은 Θ(1)이다.




삽입정렬, 교환정렬, 선택정렬 비교

알고리즘 

키의 비교 

레코드의 배정 

추가적인 저장장소 사용 

삽입정렬

 

 

 

제자리 정렬 

 교환정렬

 

 

제자리 정렬 

 선택정렬

 

 

제자리 정렬 


삽입정렬과 교환정렬

- 키의 비교를 기준으로 삽입정렬의 수행속도는 최소한 교환정렬만큼은 항상 빠르고, 평균적으로는 더 빠르다.

- 레코드 지정을 기준으로 하면 최악의 경우와 평균의 경우 모두 교환정렬보다 삽입정렬이 빠르다.

- 따라서 삽입정렬이 교환정렬보다 좋은 알고리즘이다.


교환정렬과 선택정렬

- 정렬된 경우를 제외하면 선택정렬이 교환정렬보다 좋은 알고리즘이다. 정렬된 경우에는 교환정렬에선 교환이 일어나지 않는다.


삽입정렬과 선택정렬

- 키의 비교를 기준으로 삽입정렬의 수행속도는 최소한 교환정렬만큼은 항상 빠르고, 평균적으로는 더 빠르다.

- 레코드 지정을 기준으로 하면 n과 레코드가 충분히 크면 선택정렬이 삽입정렬보다 확실히 좋다.




내용 출처

Foundations of Algorithms Using C++ Pseudocode 3rd Edition 알고리즘; Richard Neapolitan, Kumarss Naimipour; 도경구 역; 사이텍미디어


단위연산(basic operation): 알고리즘 내의 어떤 명령문이나 명령문 군을 선정하여, 알고리즘이 수행한 총 작업의 양을 이 명령문이나 명령문 군을 수행한 횟수에 대략적으로 비례하도록한다. 이 명령문 또는 명령문 군을 단위연산이라 한다.




시간복잡도 분석(time complexity analysis): 입력크기의 값에 대해서 단위연산을 몇 번 수행하는지를 구하는 것


입력 값에 상관 없이 입력크기에 따라 시간복잡도가 달라지는 경우

모든 경우 시간복잡도(every-case time complexity, T(n))


입력 값과 입력크기에 따라 시간복잡도가 달라지는 경우

최악의 경우 시간복잡도(worst-case time complexity, W(n)): 단위연산이 수행되는 최대 횟수 고려

평균의 경우 시간복잡도(average-case time complexity, A(n)): 알고리즘이 수행할 단위연산의 평균 횟수 고려, 입력 값에 대한 각각의 확률을 부여해야 함

최선의 경우 시간복잡도(best-case time complexity, B(n): 알고리즘이 수행할 단위연산의 최소 횟수 고려

* 모든 경우 시간복잡도를 구할 수 없는 알고리즘에 대하여, 최선의 경우 분석보다는 최악의 경우나 평균의 경우 분석을 훨씬 더 자주 실시함




큰 O(big O)

주어진 복잡도 함수 f(n)에 대해서, O(f(n))n ≥ N을 만족하는 모든 n에 대해 다음 부등식이 만족하는 양의 실수 c와 음이 아닌 정수 N이 존재하는 복잡도 함수 g(n)의 집합이다.

만약 g(n)  O(f(n))이면, "g(n)f(n)큰 O이다"라고 한다.



예) 

위의 경우 n ≥ 10에 대해서는 다음과 같이 된다.

따라서 큰 O의 정의에서 c = 2N = 10을 취할 수 있으므로 다음과 같이 결론 지을 수 있다.

큰 O는 함수의 점근적인 상한(asymptotic upper bound)을 준다.




오메가(omega)

주어진 복잡도 함수 f(n)에 대해서, (f(n))은 n ≥ N을 만족하는 모든 n에 대해 다음 부등식이 만족하는 양의 실수 c와 음이 아닌 정수 N이 존재하는 복잡도 함수 g(n)의 집합이다.

만약 g(n)  (f(n))이면, "g(n)은 f(n)의 오메가이다"라고 한다.


예) 

위의 경우 n ≥ 0에 대해서는 다음과 같이 된다.

따라서 오메가의 정의에서 c = 1과 N = 0을 취할 수 있으므로 다음과 같이 결론 지을 수 있다.

오메가는 함수의 점근적인 하한(asymptotic lower bound)를 나타낸다.




차수(order)

주어진 복잡도 함수 f(n)에 대해서, 다음과 같이 정의한다.

Θ(f(n))는 n ≥ N을 만족하는 모든 n에 대해서 다음 부등식이 만족하는 양의 실수 c, d와 음이 아닌 정수 N이 존재하는 복잡도 함수 g(n)의 집합이다.

만약 g(n) Θ(f(n))이면, "g(n)은 f(n)차수이다"라고 한다.





작은 o(small o)

주어진 복잡도 함수 f(n)에 대해서, o(f(n))은 모든 양의 실수 c에 대해 n ≥ N을 만족하는 모든 n에 대하여 다음 부등식을 만족하는 음이 아닌 정수 N이 존재하는 모든 복잡도 함수 g(n)의 집합이다.

만약 g(n) ∈ o(f(n))이면, "g(n)은 f(n)의 작은 o이다"라고 한다.

위의 정의는 모든 양의 실수 c에 대해서 그 범위가 성립해야 하므로 g(n)f(n)같은 함수보다는 궁극적으로 훨씬 좋다.




내용 출처

Foundations of Algorithms Using C++ Pseudocode 3rd Edition 알고리즘; Richard Neapolitan, Kumarss Naimipour; 도경구 역; 사이텍미디어

그림 출처

GeeksforGeeks, http://www.geeksforgeeks.org/analysis-of-algorithms-set-3asymptotic-notations/

Docker에 관해서는 아래의 읽을거리를 참고하세요.

ROR Lab <Docker를 이용한 손쉬운 레일스 배포> 세미나: https://www.facebook.com/naverd2/posts/505653179563380

<가장 빨리 만나는 Docker> : https://pyrasis.com/book/DockerForTheReallyImpatient/Chapter01


참고로 macOS Sierra 환경에서 작업하였다. 리눅스 환경에서는 docker 명령을 실행할때 항상 sudo를 추가해야 한다. 번거롭다면 관리자 그룹에 추가시켜주자.


배포하기위한 'rails-new-docker'라는 이름의 간단한 앱을 만든다. static page로 'hello docker'를 띄워보자.

$ rails new rails-new-docker

$ cd rails-new-docker

$ vi Gemfile

...

# Use high_voltage for static page

gem 'high_voltage', '~> 3.0'

...

$ bundle install

$ mkdir app/views/pages

$ vi app/views/pages/home.html.erb

<h1>hello docker!!</h1>


remote 저장소에 소스를 올린다. docker 컨테이너에 로컬의 소스를 복사해서 넣을 수도 있겠으나, 배포의 목적으로 만드는 것이기 때문에 다른 호스트에서 컨테이너를 실행할때 소스코드를 받아오기 위해 remote 저장소에 올린다.

$ git init

$ git add .

$ git commit -m 'first commit'

$ git remote add origin [리모드 저장소 주소]

$ git push origin master


Docker 이미지를 만들기 위한 Dockerfile을 생성한다.

Dockerfile

FROM ubuntu
MAINTAINER stardust(handhee7@gmail.com)

# 아래는 자신의 앱에 관한 필요한 설정을 만들면 된다.
# Run upgrades
RUN apt-get update

# Install basic packages
RUN apt-get -qq -y install git curl build-essential openssl libssl-dev python-software-properties python g++ make
RUN apt-get -qq -y install libsqlite3-dev
RUN apt-get -qq -y install nodejs

# Install Ruby
RUN apt-get -qq -y install ruby-full
RUN gem install bundler --no-ri --no-rdoc
RUN gem install foreman compass

# Install rails-new-docker
WORKDIR /app
RUN git clone https://github.com/Stardust-kr/rails-new-docker.git /app
RUN bundle install --without development test

# Run rails-new-docker
ENV SECRET_KEY_BASE dockerkeybase
ENV RAILS_ENV production
EXPOSE 5959
CMD foreman start -f Procfile

foreman을 활용하여 웹 서버시 수행될 명령을 Procfile에 미리 기록하여 사용할 수 있다. 대신 쉘 스크립트를 활용할 수 있다.


Procfile

web: bundle exec rails server -p 5959


rails_12factor 젬을 추가하여 로그를 표준출력으로 나오게 한다. docker logs [CONTAINER NAME OR ID]를 입력했을 때 앱에 관한 로그를 볼 수 있다.


Gemfile

# Use rails_12factor for stdout logs
gem 'rails_12factor'


다시 리모트 저장소에 푸시한다. Dockerfile은 코드에 포함될 필요는 없지만 동일한 앱을 구성하려는 사용자를 위해 코드의 버전과 똑같이 관리될 수 있도록 추가해주었다.


이제 이미지를 만들자. 네임스페이스/이름:태그 형태로 생성할 수 있다.  이미지가 생성되면 해당 이미지를 이용하여 컨테이너를 실행시켜보자. 그리고 실행된 이미지를 확인한다.

$ docker build -t stardustkr/rails-new-docker:0.1 .

$ docker run --name v0.1 -d -p 5959:5959 stardustkr/rails-new-docker:0.1

$ docker ps -l

$ docker logs v0.1


브라우저를 열고 localhost:5959/pages/home에 접속해보자.

실제 사용하는 앱은 데이터베이스를 필요로 할 것이다. 하지만 앱과 데이터베이스가 동시에 존재하는 컨테이너는 만들지 않을것이다. 왜냐하면 새로운 버전의 앱이 만들어져 다시 새로운 이미지를 만들어 배포 한다 가정 했을 때 기존 컨테이너 내부의 데이터베이스는 날아가기 때문이다.


필자는 아마존 RDS를 연결할 것이다. 로컬 호스트의 DB에 연결하든, 다른 외부의 DB의 연결하든 사용자의 마음일 것이다.

앱에 db를 필요로하는 scaffold를 생성하고, docker 이미지에 mysql관련 패키지를 추가로 설치한 다음 외부 db와 연결하여 띄워보자.


$ rails g scaffold post title content

$ rake db:migrate

$ vi Gemfile

...

# Use mysql2

gem 'mysql2'

...

$ vi Dockerfile

...

# Install Mysql

ENV DEBIAN_FRONTEND noninteractive

RUN echo "mysql-client mysql-client/root_password password" | debconf-set-selections

RUN echo "mysql-client mysql-client/root_password_again password" | debconf-set-selections

RUN apt-get install -qq -y mysql-client libmysqlclient-dev

...

$ docker build -t stardustkr/rails-new-docker:0.2 .

$ docker run -i -t -e DATABASE_URL="mysql2://[Mysql 계정명]:[Mysql 계정비밀번호]@[Mysql 서버 주소]/[DB명]" stardustkr/rails-new-docker:0.2 bundle exec rake db:reset

$ docker run --name v0.2 -d -p 5959:5959 -e DATABASE_URL="mysql2://[Mysql 계정명]:[Mysql 계정비밀번호]@[Mysql 서버 주소]/[DB명]" stardustkr/rails-new-docker

$ docker ps -l


만들어진 posts 페이지로 접속해보자.

localhost:5959/posts

rails 앱은 동작하는데 에러 페이지를 띄운다면 로그를 확인해보자.

$ docker logs v0.2


이제 동일한 앱을 서버에 배포해보자. 개인 서버여도 좋고 아마존 등 클라우드 서비스여도 좋다. 여기서는 아마존 ec2에 배포할 것이다.

서버를 설정하기 전에 이미지를 먼저 배포한다. Docker hub에 배포하여 사용하겠다. Docker hub: https://hub.docker.com

github처럼 repository를 만들자. 앱과 똑같은 이름으로 만들었다. 

로컬에서 로그인 하고 push를 하자.

$ docker login --username=[Docker hub 사용자 이름]

$ docker push stardustkr/rails-new-docker:0.2

푸시 끝


ec2는 우분투 이미지로 생성하였다. ec2에 ssh연결하여 docker를 설치하자.

# sudo apt-get update

# sudo apt-get install docker.io

# sudo ln -sf /usr/bin/docker.io /usr/local/bin/docker


이미지를 pull 하고 실행시켜주자. 이미 로컬에서 테스트하면서 db를 초기화 하였으므로 초기화 코드는 없이 진행한다.

# sudo docker pull stardustkr/rails-new-docker:0.2

# sudo docker run --name v0.2 -d -p 80:5959 -e DATABASE_URL="mysql2://[Mysql 계정명]:[Mysql 계정비밀번호]@[Mysql 서버 주소]/[DB명]" stardustkr/rails-new-docker


이제 인스턴스의 publid dns로 접속해보자.

http://[인스턴스 public dns]/hosts

아래와 같이 로컬에서 작업환 환경과 동일하게 표시됨을 알 수 있다. DB를 똑같은것을 적용하였으므로 로컬에서 생성했던 글이 동일하게 표시됨을 알 수 있다.

마지막으로 기존에 만들었던 미용실 프로젝트를 docker로 배포해 볼 것이다.

Gemfile에 rails_12factor를 추가하고 Dockerfile과 Procfile을 추가한다. 위 과정을 동일하게 수행하여 아마존 ec2 인스턴스에 올려보았다.

아래 인스턴스에서 그 결과를 확인 할 수 있다.


http://ec2-52-79-125-65.ap-northeast-2.compute.amazonaws.com


이미지는 docker pull stardustkr/charmbithair:0.1로 받을 수 있다.

github: https://github.com/Stardust-kr/charmbitHair.git

+ Recent posts