→ 알고리즘 관련

Segment Tree 란?세그먼트 트리는 범위 데이터의 조회, 업데이트에 효과적인 자료구조이다. 이진트리의 형태로 바로 O(logN)의 시간복잡도를 가지게 된다. 가장 많이 쓰이는 것은 특정 범위 내의 요소들에 대한 합계, 최솟값, 최댓값을 검색하고 처리할 수 있다. Segment Tree 만들기만약 [1, 2, 3, 4, 5] 와 같은 배열이 있다고 해보자. 이것을 Segment Tree 자료에 넣어 합계를 쉽게 검색하고 싶다. 어떻게 해야 할까? 이진트리의 기본 개념처럼 계속 반으로 쪼개서 저장해 주면 된다. 하지만 우리가 원하는 것은 합계 뿐... 아래처럼 저장해 주면 Segment Tree 끝!이다. 참 쉽죠? 이것을 코드로 구현해 보자. Segment Tree를 만들기 위한 고민Tree의 크기..

Bitmask란?Bitmask는 단어 그대로 비트에 마스킹을 한다라는 뜻인데, 비트 연산을 활용하여 데이터를 효율적으로 저장하고 조작하는 방법이다. 비트(Bit)는 컴퓨터 과학에서 정보의 가장 작은 단위이다. 비트는 이진법(Binary System)을 기반으로 하며, 두 가지 값(0, 1) 중 하나를 가질 수 있다. 비트연산Bitmask를 하기 전에 비트 연산에 대해서 알아야 한다. 비트 연산에는 AND, OR, XOR, NOT, Shift연산이 있다. 아래와 같은 게이트들을 접해봤을 것이다. (직접 그려봤는데 생각보다 그리기 힘들다 😅)처음에는 OR과 XOR이 약간 헷갈렸는데 아래의 개념으로 생각한다면 아주 이해가 쏙쏙 된다.AND 연산 ( & )1101 & 1011 을 하게 되면 두 비트가 모두 1..

알고리즘뿐만 아니라 유용하게 쓰일만한 고차함수들을 여러 개 정리해 보았다. map컬렉션의 각 요소에 동일한 변환을 적용하고, 변환된 요소들로 새로운 배열을 생성한다. 아래와 같이 사용이 가능하다. name in을 $0로 바꿔서 대신할 수 있다.let names = ["Kim", "Lee", "Park", "Choi"]let lowercaseNames = names.map { name in name.lowercased()}let lowercaseNames = names.map { $0.lowercased() }let letterCounts = names.map { $0.count }print(lowercaseNames) // ["kim", "lee", "park", "choi"]print(letter..

Union-Find 알고리즘 이란?서로소 집합(Disjoint Set)을 효율적으로 관리하는 알고리즘이다. 아래의 두 그래프는 서로소인 집합이라고 볼 수 있다. 아래의 그래프가 주어진다면 1과 6은 같은 그룹에 속해있는지 판별할 수 있는지, 어떻게 주어진 자료로 아래의 그룹을 만들지 결정하는 알고리즘이다.알고리즘 구현하기Find재귀함수를 활용하여 부모를 찾는다. 4의 경우에는 2를 타고 가서 1이 root 로 나오게 된다. func find(_ n: Int) -> Int { if roots[n] == n { return n } return find(roots[n])} Union아래의 노드들을 그래프로 묶는 roots 배열을 만드는 것이 union 이다.func union(_ a: Int, _ ..

Swift에서 스택과 큐Swift로 프로그래밍을 하다 보면 자료구조를 구현해줘야 하는 것들이 있다. 그중 하나가 큐이다. 스택의 경우 removeLast() 와 append(_:) 의 경우 complexity 가 O(1) 이기 때문에 배열에서 위와 같은 함수를 사용하여 그대로 구현할 수 있다.따라서 스택은 구현이랄 것도 없다. 원래 있는 메서드를 개념에 맞게 사용하면 그것이 스택 자료구조이다.var stack: [Int] = [1, 2, 3, 4, 5]stack.append(6)print(stack.removeLast()) // 6print(stack) // [1, 2, 3, 4, 5] 하지만 큐의 경우 FIFO 이기 때문에 removeFirst() 메소드를 사용해야 하는데 문제는 complexity 가..

알고리즘의 기본이라고 할 수 있는 정렬. 개념은 알고 있었으나 한 번씩 구현해보고 싶었다. 우선 가장 쉬운 정렬 알고리즘부터 시작해 보려 한다. 버블 정렬 물론 시간복잡도가 O(n^2)으로 정렬 중에 가장 정직하고 비효율적인 알고리즘이다. 계속 바로뒤의 값과 비교하면서 크기를 비교하면서 위치를 바꿔주면 된다. 아래의 gif가 가장 쉽게 표현한 것 같아서 가져왔다. 버블 정렬 구현하기 맨 마지막으로 가는 숫자는 가장 큰 숫자가 되므로 제외하고 다음 정렬을 수행한다. func bubbleSort(_ array: [Int]) -> [Int] { var array = array for i in 0.. [Int] { var array = array for i in 0.. [Int] { var array = arr..

이진탐색 알고리즘을 풀다보면 특정 조건을 만족하는 해를 찾아야 하는 경우가 있는데 이 경우 유용한 알고리즘이 이진탐색이다. 물론 데이터가 오름차순, 내림차순으로 정렬되어있는 경우, 어떠한 기준에 의하여 순서가 정해져 있는 경우에만 사용이 가능하다. 원리를 아주 간단하게 요약하자면 계속 반토막 내면서 탐색범위를 줄여나가는 것이라고 생각하면 쉽다. 그리고 확인하는 것은 탐색범위의 중간값이다. 따라서 시간복잡도는 아래의 식에 의해서 O(logN)이다. (log2 상수는 무시된다) 이진탐색 과정 이진탐색은 다음과 같은 과정을 거친다. 인덱스를 기준으로 low를 왼쪽의 맨 끝, high를 오른쪽의 맨 끝으로 정하고 시작한다. 그 low, high의 중간을 mid로 둔 뒤, mid에 있는 값을 검색한다. 임의로 여..

알고리즘을 공부하다 보니 자료구조에 대한 기본기를 다져야겠다고 생각했다. 앱을 개발하면서도 데이터를 구성할 때 막연하게 구성한 느낌이 난다. 항상 데이터를 구성하면서 느낀 점은 나중에 구조를 바꿀 때 정말 골치가 아프다는 점인데, 이렇게 하나하나 자료구조에 대한 공부를 통해 처음 앱을 구성할 때 이유 있는 데이터 구성을 하고자 자료구조에 대한 공부를 시작하게 되었다. 자료구조란? 자료구조(data structure)란 컴퓨터 과학에서 효율적인 접근 및 수정을 가능하게 하는 자료의 조직, 관리, 저장을 의미한다. 데이터 값의 모임, 관계, 데이터에 적용할 수 있는 함수나 명령을 의미한다. 실행시간, 메모리 용량을 최소화시켜 정확하게 원하는 데이터에 접근할 수 있게 적절한 자료구조의 선택을 해야 한다. 자료..