Computer Science11 [Swift] Quick Sort 구현해보기 [Swift] Quick Sort 구현해보기 퀵 정렬은 분할 정복 기법중에 하나다. 분할 정복이란 문제를 작은 두개의 문제로 분리하고, 각각 해결한 다음 결과를 모아서 문제를 해결하는 전략이다! 먼저 프로세스를 살펴보면 1. 배열 에서 이 될 하나의 원소를 고른다. 2. 피벗 앞에는 피벗보다 작은 값들이 오고, 피벗 뒤에는 큰 값이 오도록 배열을 두개로 나눈다. --> 이렇게 배열을 두개로 나누는 걸 분할이라고 한다. 3. 분할된 두개의 작은 배열에 대해 재귀적으로 과정을 반복한다. func quickSort(_ array: [Int]) -> [Int] { guard let first = array.first, array.count > 1 else { return array } let pivot = fi.. 2023. 4. 28. [Swift] Queue 구현해보기 [Swift] Queue 구현해보기 Swift에서는 Queue 자료구조를 기본적으로 지원하지 않는다. Array의 배열의 맨 앞 원소를 지워주는 removeFirst()를 지원하긴 하지만 O(N) 시간복잡도를 갖는다. 제네릭 타입을 가지고, 시간 복잡도가 O(1)인 Queue를 구현해보자. struct Queue { private var inputStack = [T]() private var outputStack = [T]() mutating public func append(_ x: T) { inputStack.append(x) } mutating public func pop() -> T? { var top: T? while !(inputStack.isEmpty) { let x = inputStack... 2023. 4. 28. [Swift] 양방향 Linked List 구현해보기 [Swift] 양방향 Linked List 구현해보기 정의 단일 연결 리스트와 다른 점 이전 노드를 나타내는 포인터(prev)가 추가되었고, 리스트 자체의 tail도 있어 역방향 탐색이 절반정도 좋아짐 시간 복잡도 구현 class Node { var data: T var prev: Node? var next: Node? init(data: T, prev: Node? = nil, next: Node? = nil) { self.data = data self.prev = prev self.next = next } } class DoublyLinkedList { private var head: Node? private var tail: Node? init(head: Node? = nil, tail: Node? .. 2023. 4. 14. [Swift] 단방향 Linked List 구현해보기 [Swift] 단방향 Linked List 단방향 링크드 리스트는 데이터를 갖고 있는 노드들을 포인터로 선형적으로 연결해 사용하는 자료구조 삭제와 삽입에 O(1)의 시간 복잡도가 걸리기 때문에 빈번하게 삽입/삭제가 필요한 상황에 유용 하지만 원하는 노드까지의 '탐색'은 O(N)이 걸림 따라서 배열처럼 동시에 인덱스를 통한 Random Access는 불가능하고, 처음부터 원하는 데이터가 나올 때까지 탐색을 진행해야 하기 때문에 O(N)의 시간 복잡도가 요구된다는 단점이 있음 /// /// data: 실제로 저장할 데이터 /// next: 현재 노드의 다음 노드를 저장할 데이터 /// class Node { let data: T var next: Node? init(data: T, next: Node? = .. 2023. 4. 13. [Swift] 이진 탐색 구현 [Swift] 이진 탐색 구현 조건 1. 배열 내부의 데이터가 정렬되어 있어야 함 2. 탐색 범위를 절반씩 좁혀가며 데이터를 탐색 3. 이진 탐색은 위치를 나타내는 변수를 세 개 사용 -> 시작점, 끝점, 중간점 -> 중간점으로 찾으려난 데이터와 비교하여 다시 시작점 / 중간점 / 끝점 설정 언제 쓰면 좋을까? - 처리해야 할 데이터의 개수나 값이 1000만 단위 이상으로 넘어갈 때 사용 구현 - 재귀 혹은 단순 반복문으로 구현이 가함 - 시간 복잡도: O(logN) - 아래는 재귀 함수를 호출하는 방식으로 구현 func binarySearch(_ array: [Int], _ target: Int, _ count: Int) -> Int { if array.count == 1 && array[0] == .. 2023. 4. 11. Makefile 생성하기 Makefile 생성하기 배경 글로벌 앱 작업 중 PM분께서 번역파일을 구글 드라이버에 올려주셨다. 실시간으로 수정되거나 추가되는 key/value 값이 있기에 매번 파일을 다운받아서 변환하는 작업은 매우 번거롭다. 귀찮다! 그래서 python으로 스크립트를 작성한 뒤 터미널로 자동으로 실행되게끔 만들었다. 오늘은 Makefile을 만들어서 미리 지정한 명령어로 스크립트가 실행되게끔 만들어보자. 설정 방법 프로젝트 메인 폴더에서 터미널을 열고 Makefile 파일을 생성해주자. # touch 명령어로 Makefile 생성 touch Makefile 맥인 경우 기본으로 파일을 열면 텍스트 편집기로 열린다. (vim이든 상관없음) 번역파일을 생성하는 python 파일은 localize 폴더 내부에 local.. 2023. 3. 28. 이전 1 2 다음
