본문 바로가기

Swift/Algorithms And Data Structures

 (3)
큐 Queue 큐 Queue 큐는 오로지 뒤에서만 새로운 아이템을 삽입할 수 있으며 앞에서 아이템을 제거할 수 있는 리스트입니다. 이러한 규칙은 큐에 삽입한 제일 첫 아이템이 가장 먼저 꺼낼 수 있도록 합니다. 가장 먼저 들어간 것이 가장 먼저 나오는 것이죠! 왜 우리들은 큐가 필요로 할까요? 많은 알고리즘에서 여러분은 객체를 임시 리스트에 넣고 나중에 꺼내는 경우가 많을 것입니다. 또한 여러분이 객체를 추가하고 꺼내고 순서가 중요할 때 그렇습니다. 큐는 FIFO(first-in, first-out) 순서입니다. 여러분이 제일 처음에 삽입한 아이템이 가장 먼저 나오게 된다는 의미입니다. 여기에 숫자를 삽입(enqueue) 하는 예제가 있습니다. queue.enqueue(10) 큐는 이제 [10]이 됩니다. 다음 숫자를..
이진 탐색 Binary Search 이진 탐색 Binary Search 목표: 배열의 원소를 빠르게 찾기 언제: 어떤 숫자들의 배열을 가졌다고 가정했을 때, 특정한 숫자가 해당 배열에 존재하는지를 알고 싶을 때 대부분의 경우, 스위프트의 Collection.index(of:) 함수가 탐색에서 사용됩니다. let numbers = [11, 59, 3, 2, 53, 17, 31, 7, 19, 67, 47, 13, 37, 61, 29, 43, 5, 41 ,23] numbers.index(of: 43) // 15 반환 하지만 내장 함수 Collection.index(of:)는 선형 탐색입니다. 코드의 내부는 아래와 같습니다. func linearSearch(_ a: [T], _ key: T) -> Int? { for i in 0..< a.coun..
빅-오 표기법 Big-O Notation 빅-오 표기법 알고리즘이 얼마나 빠른지를 아는 것과 그 알고리즘이 얼만큼의 공간을 사용해야하는지를 아는 것은 유용합니다. 또한, 이 표기법은 올바른 알고리즘을 선택하는 것에 도움을 줍니다. 빅-오 표기법은 알고리즘이 진행하는 시간에 대한 대략적인 지표를 알려줍니다. 알고리즘의 메모리 사용량 또한 그렇습니다. 누군가 다음과 같이 말한다면, “이 알고리즘은 최악의 경우 O(n^2)이며 O(n) 공간을 사용한다.” 이 말의 의미는 조금 느리지만 추가적인 메모리가 많이 필요하진 않다는 것입니다. 알고리즘의 빅오를 파악하는 것은 수학적인 분석법을 통해 이루어집니다. 여기서는 수학을 이용하는 것을 피하겠지만 다른 값들이 무엇을 의미하는지 아는 것은 중요합니다. n은 여러분이 처리해야할 데이터 아이템의 개수를 말합니..

티스토리툴바