Swift 알고리즘 클럽에 오신 것을 환영합니다!

이곳에서 새롭게 주목받는 프로그래밍 언어 Swift로 구현한 널리 알려진 알고리즘과 자료구조를 만나볼 수 있습니다. 각 구현에는 작동 원리에 대한 상세한 설명이 함께 제공됩니다.

시험 준비를 위해 이론을 공부하는 컴퓨터 공학 전공자나, 실무에서 사용하는 기술의 이론적 배경을 다지고 싶은 독학 프로그래머 모두에게 이 공간이 도움이 될 것입니다!

이 프로젝트의 핵심 목표는 알고리즘의 작동 원리를 명확하게 설명하는 것입니다. 실제 프로젝트에 바로 가져다 쓸 수 있는 라이브러리를 만드는 것보다는, 코드의 명확성과 가독성에 중점을 두었습니다. 다만, 대부분의 코드는 실제 개발 환경에서도 사용할 수 있는 수준으로 작성되었으며, 필요한 경우 약간의 수정을 통해 여러분의 코드베이스에 맞게 조정할 수 있습니다.

모든 코드는 Xcode 10과 Swift 4.2 버전과 호환됩니다. Swift의 최신 버전에 맞춰 계속해서 업데이트할 예정입니다. GitHub 페이지 버전의 저장소를 찾는다면 여기를 확인하면 됩니다.

😍 여러분의 제안과 기여를 환영합니다! 😍

주요 링크

알고리즘과 자료구조란 무엇인가? 알고리즘의 기본 개념을 알아보자.

왜 알고리즘을 배워야 할까? 알고리즘이 자신에게 맞지 않다고 생각한다면 이 글을 읽어보자.

빅오 표기법. "이 알고리즘은 **O(n)**이다"와 같은 표현을 자주 사용한다. 이게 무슨 뜻인지 모른다면 먼저 이 글을 읽어보자.

알고리즘 설계 기법. 직접 알고리즘을 만드는 방법을 배워보자.

기여 방법. 피드백을 남기려면 이슈를 보고하거나, 풀 리퀘스트를 제출하자.

시작하기

알고리즘과 자료구조를 처음 접한다면, 다음 주제부터 시작하는 것이 좋다:

• 스택
• 큐
• 삽입 정렬
• 이진 탐색과 이진 탐색 트리
• 병합 정렬
• 보이어-무어 문자열 탐색

알고리즘

검색

• 선형 검색(Linear Search). 배열에서 특정 요소를 찾는다.
• 이진 검색(Binary Search). 정렬된 배열에서 빠르게 요소를 찾는다.
• 횟수 세기(Count Occurrences). 배열에서 특정 값이 몇 번 나타나는지 센다.
• 최솟값/최댓값 선택(Select Minimum / Maximum). 배열에서 최솟값 또는 최댓값을 찾는다.
• k번째 큰 요소(K-th Largest Element). 배열에서 k번째로 큰 요소를 찾는다. 예를 들어 중앙값을 구할 때 사용한다.
• 선택 샘플링(Selection Sampling). 컬렉션에서 무작위로 여러 항목을 선택한다.
• 유니온-파인드(Union-Find). 서로소 집합을 관리하고 빠르게 병합할 수 있게 한다.

문자열 검색

• Brute-Force String Search. 가장 단순한 방법.
• Boyer-Moore. 빠른 부분 문자열 검색 방법. 텍스트의 모든 문자를 확인하지 않고 룩업 테이블을 기반으로 건너뛴다.
• Knuth-Morris-Pratt. 주어진 패턴의 모든 발생 위치를 반환하는 선형 시간 문자열 알고리즘.
• Rabin-Karp. 해싱을 사용해 더 빠르게 검색.
• Longest Common Subsequence. 두 문자열에서 동일한 순서로 나타나는 가장 긴 문자 시퀀스를 찾는다.
• Z-Algorithm. 문자열 내에서 패턴의 모든 인스턴스를 찾고, 패턴이 시작하는 위치의 인덱스를 반환한다.

정렬 알고리즘

정렬 알고리즘이 어떻게 동작하는지 보는 것은 재미있지만, 실제로는 직접 정렬 루틴을 구현할 일은 거의 없다. Swift의 기본 sort() 함수가 충분히 강력하다. 하지만 궁금하다면 계속 읽어보자.

기본 정렬 알고리즘:

• 삽입 정렬
• 선택 정렬
• 셸 정렬

빠른 정렬 알고리즘:

• 퀵 정렬
• 병합 정렬
• 힙 정렬

하이브리드 정렬 알고리즘:

• 인트로 정렬

특수 목적 정렬 알고리즘:

• 계수 정렬
• 기수 정렬
• 위상 정렬

비효율적인 정렬 알고리즘 (사용하지 말 것!):

• 버블 정렬
• 슬로우 정렬

압축 기법

• 런 렝스 인코딩(Run-Length Encoding, RLE). 반복되는 값을 단일 바이트와 반복 횟수로 저장한다.
• 허프만 코딩(Huffman Coding). 더 자주 나타나는 요소를 더 적은 비트 수로 저장한다.

기타 알고리즘

• Shuffle. 배열의 내용을 무작위로 재배열한다.
• Comb Sort. 버블 정렬 알고리즘을 개선한 방식이다.
• Convex Hull. 볼록 껍질 알고리즘을 다룬다.
• Miller-Rabin Primality Test. 주어진 숫자가 소수인지 판별한다.
• MinimumCoinChange. 동적 프로그래밍을 활용한 최소 동전 교환 문제를 다룬다.
• Genetic. 생물학적 진화를 모델링하며, 값을 점진적으로 이상적인 형태로 변형하는 간단한 예제를 제공한다.
• Myers Difference Algorithm. 두 시퀀스 간의 가장 긴 공통 부분 시퀀스를 찾는 알고리즘이다.

수학

• 최대공약수(GCD). 추가 보너스: 최소공배수도 함께 다룬다.
• 순열과 조합. 조합론의 세계로 빠져보자!
• Shunting Yard 알고리즘. 중위 표기법을 후위 표기법으로 변환한다.
• 카라추바 곱셈. 기본 곱셈을 다른 방식으로 접근한다.
• Haversine 거리. 구면 위의 두 점 사이의 거리를 계산한다.
• 슈트라센 행렬 곱셈. 행렬 곱셈을 효율적으로 처리하는 방법.
• 반시계 방향. 단순 다각형의 면적을 구한다.

머신러닝

• k-평균 군집화(K-Means Clustering). 데이터를 k개의 클러스터로 분할하는 비지도 학습 분류기.
• k-최근접 이웃(k-Nearest Neighbors)
• 선형 회귀(Linear Regression). 두 개 이상의 변수 간 관계를 모델링하는 기법.
• 로지스틱 회귀(Logistic Regression)
• 신경망(Neural Networks)
• 페이지랭크(PageRank)
• 나이브 베이즈 분류기(Naive Bayes Classifier)
• 시뮬레이티드 어닐링(Simulated annealing). (주로 이산적인) 큰 탐색 공간에서 전역 최대값을 근사하는 확률적 기법.

데이터 구조

특정 작업에 적합한 데이터 구조를 선택할 때는 몇 가지 요소를 고려해야 한다.

첫째, 데이터의 형태와 수행해야 할 작업의 종류가 중요하다. 키를 통해 객체를 조회하려면 사전(dictionary) 구조가 필요하다. 데이터가 계층적 구조를 가진다면 트리 구조가 적합하다. 데이터가 순차적이라면 스택이나 큐를 사용한다.

둘째, 가장 자주 수행할 작업의 종류도 고려해야 한다. 특정 데이터 구조는 특정 작업에 최적화되어 있다. 예를 들어, 컬렉션에서 가장 중요한 객체를 자주 찾아야 한다면 일반 배열보다 힙(heap)이나 우선순위 큐가 더 적합하다.

대부분의 경우 내장된 Array, Dictionary, Set 타입만으로 충분하지만, 때로는 더 정교한 구조가 필요할 수 있다...

배열의 다양한 변형

• 2차원 배열(Array2D). 고정된 크기의 2차원 배열. 보드 게임에 유용하다.
• 비트 집합(Bit Set). n개의 비트로 이루어진 고정 크기의 시퀀스.
• 고정 크기 배열(Fixed Size Array). 데이터 크기를 미리 알고 있다면, 고정 크기의 전통적인 배열을 사용하는 것이 더 효율적일 수 있다.
• 정렬된 배열(Ordered Array). 항상 정렬 상태를 유지하는 배열.
• 루티시 배열 스택(Rootish Array Stack). Swift 배열의 공간 및 시간 효율성을 높인 변형.

큐(Queues)

• 스택(Stack). 후입선출(Last-in, first-out) 방식!
• 큐(Queue). 선입선출(First-in, first-out) 방식!
• 덱(Deque). 양쪽 끝에서 데이터를 추가하거나 제거할 수 있는 큐.
• 우선순위 큐(Priority Queue). 가장 중요한 요소가 항상 앞에 위치하는 큐.
• 링 버퍼(Ring Buffer). 원형 버퍼라고도 불리며, 특정 크기의 배열이 끝에 도달하면 다시 처음으로 돌아가는 개념의 자료구조.

리스트

• 연결 리스트(Linked List). 데이터 항목들이 링크로 연결된 시퀀스. 단일 연결 리스트와 이중 연결 리스트를 모두 다룬다.
• 스킵 리스트(Skip-List). 스킵 리스트는 AVL 트리나 레드-블랙 트리와 동일한 로그 시간 복잡도를 가지는 확률적 자료구조다. 검색과 업데이트 연산을 효율적으로 지원하는 똑똑한 절충안을 제공한다.

트리 구조

• 트리. 일반적인 용도의 트리 구조.
• 이진 트리. 각 노드가 최대 두 개의 자식을 가지는 트리.
• 이진 탐색 트리 (BST). 빠른 쿼리를 위해 노드를 정렬된 방식으로 구성한 이진 트리.
• 레드-블랙 트리. 자동으로 균형을 맞추는 이진 탐색 트리.
• 스플레이 트리. 최근에 업데이트된 요소를 빠르게 검색할 수 있는 자동 균형 이진 탐색 트리.
• 스레드 이진 트리. 추가 변수를 사용해 저렴하고 빠른 중위 순회를 지원하는 이진 트리.
• 세그먼트 트리. 배열의 일부분에 대한 함수를 빠르게 계산할 수 있는 트리.
  • 지연 전파
• kd-트리
• 스파스 테이블. 배열의 일부분에 대한 함수를 더 빠르게 계산하는 또 다른 방법.
• 힙. 포인터를 사용하지 않고 배열에 저장된 이진 트리. 우선순위 큐로 유용함.
• 피보나치 힙
• 트라이. 연관 데이터 구조를 저장하는 데 사용되는 특수한 트리.
• B-트리. 노드가 두 개 이상의 자식을 가질 수 있는 자동 균형 탐색 트리.
• 쿼드트리. 4개의 자식을 가지는 트리.
• 옥트리. 8개의 자식을 가지는 트리.

해싱

• 해시 테이블. 키를 통해 객체를 저장하고 검색할 수 있다. 딕셔너리 타입이 일반적으로 이 방식으로 구현된다.
• 해시 함수

집합(Set)

• 블룸 필터(Bloom Filter). 원소가 집합에 속하는지 확률적으로 테스트할 수 있는 상수 메모리 데이터 구조.
• 해시 집합(Hash Set). 해시 테이블을 사용해 구현한 집합.
• 멀티셋(Multiset). 원소가 추가된 횟수가 중요한 집합. (가방(Bag)이라고도 함.)
• 순서 집합(Ordered Set). 원소의 순서가 중요한 집합.

그래프

• 그래프
• 너비 우선 탐색 (BFS)
• 깊이 우선 탐색 (DFS)
• 가중치 없는 트리에서의 최단 경로
• 단일 출발지 최단 경로
• 가중치 없는 트리에서의 최소 신장 트리
• 최소 신장 트리
• 모든 쌍 최단 경로
• 다익스트라 최단 경로 알고리즘
• A-Star 알고리즘

퍼즐

소프트웨어 개발자 면접 질문 중 상당수는 알고리즘 퍼즐로 구성된다. 여기 몇 가지 재미있는 퍼즐을 소개한다. 더 많은 퍼즐과 해답은 여기와 여기에서 확인할 수 있다.

• 두 수의 합 문제
• 세 수의 합/네 수의 합 문제
• Fizz Buzz
• 몬티 홀 문제
• 회문 찾기
• 식사하는 철학자 문제
• 계란 떨어뜨리기 문제
• 이진 트리 인코딩 및 디코딩
• 가장 가까운 쌍 찾기

더 알아보기

마음에 드셨나요? Swift로 배우는 자료구조와 알고리즘을 확인해 보세요. Swift 알고리즘 클럽 팀이 직접 집필한 공식 서적입니다!

이 책에서는 연결 리스트, 큐, 스택과 같은 기본 자료구조부터 시작해 Swift 스타일로 구현하는 방법을 배웁니다. 이후 일반 트리, 이진 트리, AVL 트리, 이진 탐색 트리, 트라이 등 다양한 트리 구조를 다룹니다.

버블 정렬과 삽입 정렬을 넘어 더 나은 성능의 알고리즘인 병합 정렬, 기수 정렬, 힙 정렬, 퀵 정렬을 배웁니다. 또한 방향성 그래프, 무방향 그래프, 가중치 그래프를 활용해 현실 세계의 다양한 모델을 표현하는 방법을 익히고, 너비 우선 탐색, 깊이 우선 탐색, 다익스트라 알고리즘, 프림 알고리즘을 사용해 그래프와 트리를 효율적으로 탐색합니다. 이를 통해 최단 경로 찾기나 네트워크에서 최소 비용 계산과 같은 문제를 해결할 수 있습니다.

이 책을 마치면 자료구조와 알고리즘을 활용해 일반적인 문제를 해결하는 실질적인 경험을 쌓게 됩니다. 또한 자신만의 효율적이고 유용한 구현을 개발하는 데 큰 도움이 될 것입니다.

책은 raywenderlich.com 스토어에서 구매할 수 있습니다.

크레딧

Swift Algorithm Club은 원래 Matthijs Hollemans가 만들었다.

현재는 Vincent Ngo, Kelvin Lau, 그리고 Richard Ash가 관리하고 있다.

Swift Algorithm Club은 raywenderlich.com 커뮤니티의 가장 알고리즘에 능한 멤버들이 함께 만든 프로젝트다. 우리는 항상 도움을 찾고 있다. 클럽에 참여해 보는 건 어떨까? :]

라이선스

모든 콘텐츠는 MIT 오픈소스 라이선스의 조건에 따라 사용할 수 있다.

여기에 게시하거나 이 포럼을 통해 풀 리퀘스트를 제출함으로써, 여러분은 제출하거나 생성한 모든 콘텐츠(코드와 텍스트 모두)가 이 라이선스의 적용을 받는 데 동의하는 것이다. Razeware, LLC 및 기타 관련자들은 이 콘텐츠에 대해 라이선스에 명시된 모든 권리를 갖는다. 이 라이선스의 정확한 조건은 여기에서 확인할 수 있다.