자료구조(3)
-
스택 두개로 큐 구현하기(Swift)
큐의 문제점 일반적으로 배열을 사용하여 큐를 구현할 경우 배열 앞에 있는 요소가 삭제되므로, 뒤에 있는 요소들이 한칸씩 이동해야한다. 이로 인해 배열의 removeFirst()메서드는 O(n)의 시간복잡도를 가진다. 이것을 해결하기 위해서 여러가지 방법이 존재한다. LinkedLIst로 구현 nil로 변환 후 nil이 배열의 일정부분을 차지할 경우 삭제 스택 두개로 큐 구현 이 중에서 가장 구현이 빠르고 직관적으로 이해하기 쉬운 스택 두개로 구현을 해보려고한다. 기본 큐 struct DoubleStackQueue { private var enqueueArr: [T] = [] private var dequeueArr: [T] = [] mutating func enqueue(_ data: T) { enque..
2023.07.14 -
Swift - LinkedList(연결리스트)
링크드리스트란? 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조 종류로는 단일 연결리스트와 이중 연결리스트, 원형 연결리스트 등등이 존재한다. 장점 자료의 추가와 삭제가 O(1)의 시간복잡도를 가진다. => 배열과 비교하였을 때 배열은 중간지점의 데이터를 삭제한다고 가정할 경우 그 이후의 노드들이 한칸씩 이동해야한다. 그러나, 링크드리스트의 경우 가지고 있는 포인터만을 바꿔주면 해결이 가능하다. 단점 배열과 트리에 비해 특정 위치의 데이터를 검색할 때 O(n)이 걸린다. => 단일 연결리스트로 볼 경우 Head를 통해 포인터가 존재하지 않을 때까지 해당 값을 순회하면서 찾아야하기 떄문이다. 단일 연결 리스트 노드가 데이터와 다음 노드를 가리키는 포인터 두가지..
2023.07.12 -
재귀함수에 관한 고찰(Tail Recursion, Trampoline, reduce)
해당 내용은 애플 공식문서에서도 찾지 못하였고 stackoverflow와 여러 블로그 등 구글링 내용과 실험을 토대로 작성한 내용입니다 혹시 틀린부분이 있을 수 있으니 말씀해주시면 수정하도록 하겠습니다 재귀 꼬리 재귀와 트램펄린을 들어가기 전에 재귀에 대하여 간단하게 이야기 해보아야한다. 재귀란? 함수가 직접 혹은 간접적으로 함수 본인을 다시 호출하는 것을 재귀라고 표현한다. func power(number: Int, n: Int) -> Int { if n < 1 { return 1 } return n * power(number: number, n: n-1) } number의 n제곱을 구하는 함수로 지속적으로 n-1의 본인 함수를 호출하여 결과를 리턴하는 함수이다. 해당 함수는 위와 같이 메모리 스택에 ..
2023.01.18