Data Structure & Algorithm/Algorithm

[Algorithm] Permutation & Combination(순열과 조합)

순열과 조합 코드를 작성해보자.Python에서 직접 코드를 작성할 필요가 없다.from itertools import permutationsfrom itertools import combinationsdata = [1, 2, 3]list(permutations(data, 2)) # (1, 2), (1, 3), (2, 1), ...list(combinations(data, 2)) # (1, 2), (1, 3), (2, 3)이렇게 제공되는 함수가 있기 때문에 원하는 개수에 맞는 순열, 조합 요소를 뽑아준다. 하지만 Swift에서는 직접 구현해야하니...한번 작성해보자.순열원하는 함수 형태는 다음과 같다.func permutations(data: [T], count: Int) -> [[T]]?제네릭을 사용..

[Algotithm] Sliding Window

오늘은 Sliding Window 에 대해 알아보도록 하겠습니다.배열이나 문자열 같은 선형 데이터 구조에서 고정되거나 변화하는 크기의 윈도우를 이동시키며 데이터를 처리하는 기법입니다.여기서 윈도우란 연속된 요소의 SubArray라고 할 수 있습니다.해결해야 하는 문제에 따라 고정 슬라이딩 윈도우, 가변 슬라이딩 윈도우로 나뉠 수 있습니다.고정 슬라이딩 윈도우문제예시https://www.acmicpc.net/problem/12891평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA”는 DNA 문자열이 아니지만 “ACCA”는 DNA 문자열이다. 이런 신비..

[Algotithm] Longest increasing subsequence

오늘은 Longest Increasing Subsequence(LIS)에 대해 알아보도록 하겠습니다.주어진 수열(배열)에서 가장 긴 증가하는 부분 수열을 찾는 문제입니다.문제 예시길이가 n이며 배열의 원소는 정수 범위의 값을 갖는 배열 A가 있다고 가정합니다.0 ≤ i  j ≤ n - 1 인 i와 j 가 있을 때, 항상 A[i] [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]이와 같은 수열이 있을 때, LIS는 아래와 같습니다.[0, 2, 6, 9, 11, 15][0, 4, 6, 9, 11, 15][0, 2, 6, 9, 13, 15][0, 4, 6, 9, 13, 15]이처럼 LIS는 여러 개가 될 수 있습니다.접근법문제를 해결하기위해 동적계획법과 이분 탐..

[Algorithm] Depth-First Search(DFS)

이전에 BFS(Breadth-First Search)에 대해 공부했었습니다.오늘은 그 친구격인 Depth-First Search(깊이우선탐색)에 대해서 알아보도록하겠습니다.마찬가지로 DFS라는 더 많이 불립니다. 특징BFS와 마찬가지로 기본개념은 Tree 구조에서 파생되었습니다.BFS에 대해 잠깐 복습해보면, BFS의 순회 기준은 노드의 Depth입니다.순회 기준과 이름이 헷갈릴 수 있지만, BFS는 낮은 Depth를 우선적으로 탐색하기 때문에 기준이 Depth가 됩니다.Depth: 0 = [2] Depth: 1 = [7, 5] Depth: 2 = [2, 10, 6, 9] Depth: 3 = [5, 11, 4]2 -> 7 -> 5 -> 2 -> 10 -> 6 -> 9 -> 5 -> 11 -> 4D:0 ..

[Algotithm] Kadane’s Algorithm

오늘은 Kadane’s Algorithm에 대해 공부해봅시다.Kadane’s Algorithm은 Maximum Sum Subarray Problem(최대 부분합 문제)을 해결하는 기법으로 유명하며,Dynamic Programming(DP)의 여러 기법 중 하나입니다.또한 배열의 요소가 정수 범위라고 가정합니다.핵심배열을 순차적으로 순회하면서, 현재까지의 부분합과 최대 부분합을 유지하는 것이 핵심입니다.처음에는 의미를 한 번에 이해하지 못했는데요.아래 그림을 봅시다.위 그림은 [2, 3, -1, -20, 5, 10]의 최대 부분합을 구하는 과정을 시각화한 그림입니다.x축은 Index를, y축은 요소들의 합을 나타냅니다. 배열의 길이만큼의 그래프가 그려집니다. 그래프를 좀 더 자세히 그려봅시다.두 개의 그래..