코딩테스트를 위한 Swift 필수 자료구조 구현하기

 

Photo by ThisisEngineering on Unsplash

 

 

코딩테스트는 취업에 있어 꼭 필요한 과정 중 하나입니다. 저도 익숙하게 사용했던 Python 언어를 활용하여 코딩 테스트를 준비했었는데요. 하지만 최근에 점차 많은 회사들이 포지션에 맞게 코딩테스트 언어 제한을 두었습니다.

 

 

2021 네이버웹툰 개발 챌린지 ( iOS 포지션은 Swift를 사용해야 한다 )

 

 

Swift는 Type-Safe 언어이고 문법도 간결해서 iOS 개발할 때에 무척 편리하게 사용하고 있습니다. 하지만 Python과 달리 별도의 Built-in 자료 구조가 없어서 코딩테스트에 필요한 부분은 직접 구현해야 합니다.

 

이번 게시글에서는 Swift를 통해 필요한 자료구조를 직접 구현하는 방법에 대해 기술하고자 합니다.

 

 

 

 

Queue

Queue 는 FIFO 방식으로 동작하는 자료구조입니다. 프린터, 작업 대기열 같은 문제에 활용되고 더 나아가 SPFA 같은 최단 거리 알고리즘에 사용합니다.

 

Double Array를 활용한 Queue

Swift Reversed 메서드의 시간 복잡도는 O(1) 이기 때문에 Double Array를 사용하면 쉽게 Queue를 구현할 수 있습니다. 일반적인 상황에서 주로 사용합니다.

 

Cursor를 활용한 Queue

Double Array를 활용한 Queue는 극단적인 테스트 케이스에서 시간초과가 발생하게 됩니다. ( 상당히 많은 1회 추가, 삭제를 반복하는 경우 Array 를 계속 재할당하는 오버헤드가 발생함 )

 

이런 경우에는 Cursor를 활용해서 Queue를 구현할 수 있습니다.

 

 

 

 

Heap ( Priority Queue )

힙(우선순위 큐)는 완전 이진트리를 기반으로 최소(혹은 최대) 값을 O(logN)으로 구할 수 있는 자료구조입니다. 최소, 최대 값을 지속적으로 추적해야 하는 문제나 최단거리를 구하는 다익스트라 알고리즘에 사용합니다.

 

구현 편의를 위해 트리가 아닌 배열을 사용하고 첫번째 index 는 사용하지 않습니다.

 

 

 

Heap 구현이 꼭 필요하지 않은 경우

Heap에 대한 원리는 파악하고 있어야 하지만 실제 코딩테스트 환경에서 구현하는데 큰 부담이 있습니다.

 

 

1. 최대, 최소 값을 계속 추척해야하는 문제

-> 테스트 케이스 범위와 실행 시간이 여유롭다면 min, max 메서드로 코드를 작성해봅니다. 시간 복잡도에 큰 손해가 있지만 우선 동작에 초점을 맞춥니다.

-> 시간 초과가 발생하거나 시험 여유 시간이 남는다면 다시 Heap으로 리팩토링합니다.

 

 

2. 최단거리를 구하는 문제

-> 다익스트라 알고리즘 대신 SPFA 알고리즘을 사용합니다. SPFA는 Queue를 사용하기 때문에 구현에 큰 어려움이 없고 일반적인 상황에서 O(V+E)으로 동작합니다.

-> 다만 테스트 케이스가 까다롭다면 O(V*E)으로 동작하기 때문에 Heap을 사용하는 다익스트라 알고리즘으로 구현해야 합니다.

 

 

 

 

 

 

 

* leetcode를 통해 동작을 확인했지만 틀린부분이 있을 수 있습니다. 잘못된 부분은 말씀해주시면 감사하겠습니다.