개요
이 글에서는 배열과 문자열에 관련된 알고리즘 문제에서 사용할 수 있는 몇 가지 추가적인 패턴과 일반적인 기법에 대해 알아볼 것이다.
$O(n)$ 문자열 구성
이전에 언급했듯이 대부분의 언어에서 문자열은 불변이다. 이는 문자열에 하나의 문자를 연결하는 것이 $O(n)$ 연산임을 의미한다. 만약 문자열이 백만개의 글자의 길이를 갖는다면, 여기에 하나의 문자를 추가하기 위해선 모든 백만개의 글자를 다른 문자열로 복사해야 한다.
많은 문제에서는 문자열을 반환하도록 요구하며, 대체로 이 문자열은 알고리즘이 실행되는 동안 생성된다. 만약 최종 문자열의 길이가 n이고 이를 연결을 통해 한 글자씩 생성한다고 가정해보자. 이 경우 시간 복잡도는 어떻게 될까? 각 단계에서 필요한 연산은 1 + 2 + 3 + ... + n이며, 이는 이 수열의 부분 합이다. 즉, 이 연산으로 인해 $O(n^2)$이 된다.
단순 연결은 문자열이 불변인 언어를 사용하는 경우 $O(n^2)$의 시간 복잡도를 초래한다.
$O(n)$ 시간에 문자열을 생성하는 더 효율적인 방법들이 있다. 이는 언어에 따라 다를 수 있다 - 여기서는 파이썬과 자바, 러스트에 대해 이야기할 것이다 - 만약 다른 언어를 사용하고 있다면, 해당 언어에서 문자열을 생성하는 최적의 방법을 찾아보는 것이 좋다.
Python
- 리스트 선언
- 문자열을 생성할 때, 문자들을 리스트에 추가한다. 이는 각 연산에 대해 $O(1)$이다.
n연산 동안 총 비용은 $O(n)$이다. - 위 작업이 완료된 후에,
"".join(list)를 사용하여 리스트를 문자열로 변환한다. 이는 $O(n)$이다. - 따라서 총 비용은 $O(n+n)=O(2n)=O(n)$이다.
1
2
3
4
5
6
def build_string(s):
arr = []
for c in s:
arr.append(c)
return "".join(arr)
Java
- StringBuilder 클래스 사용
- 문자열을 생성할 때, 문자들을 리스트(StringBuilder)에 추가한다. 이는 각 연산에 대해 $O(1)$이다.
n연산 동안 총 비용은 $O(n)$이다. - 위 작업이 완료된 후에,
StringBuilder.toString()을 사용하여 리스트를 문자열로 변환한다. 이는 $O(n)$이다. - 따라서 총 비용은 $O(n+n)=O(2n)=O(n)$이다.
1
2
3
4
5
6
7
8
public string buildString(String s) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
sb.append(s.charAt(i));
}
return sb.toString();
}
C++ 및 JavaScript
C++와 JavaScript에서는 문자열을 구성할 때 += 연산자만 사용해도 상관없다.
Rust
Rust에서 문자열을 효율적으로 구성하는 데에는 여러 방법이 있다.
+연산자 사용: Rust에서는+연산자를 사용하여 두 문자열을 연결할 수 있다. 예를 들어, 아래와 같이 두 문자열을 연결할 수 있다:1 2 3
let string1 = "Hello"; let string2 = "world"; let combined_string = string1 + " " + string2;
이렇게 하면
combined_string이라는 새 문자열이 생성되며,string1과string2가 공백으로 구분되어 연결된다.format!매크로 사용:format!매크로를 사용하여 여러 문자열과 다른 값들을 연결하여 형식화된 문자열을 생성할 수 있다. 예를 들어:1 2 3
let string1 = "Hello"; let string2 = "world"; let combined_string = format!("{} {}", string1, string2);
이렇게 하면
combined_string이라는 새 문자열이 생성되며,string1과string2가 공백으로 구분되어 연결된다.push_str메서드 사용:String타입과push_str메서드를 사용하여 기존String의 끝에 문자열을 추가할 수 있다. 이 방법은 많은 문자열을 함께 연결할 때+연산자나format!매크로를 사용하는 것보다 더 효율적일 수 있으며, 각 연결에 대해 새 문자열을 생성하는 오버헤드를 피할 수 있다:1 2 3 4 5 6
let mut s = String::new(); s.push_str("Hello"); s.push_str(" "); s.push_str("world"); println!("{}", s); // 출력: "Hello world"
String::concat메서드 사용:String타입의concat메서드를 사용하여 여러 문자열을 연결할 수 있다:1 2 3
let string1 = "Hello".to_string(); let string2 = "world".to_string(); let combined_string = String::concat(&[string1, string2]);
이렇게 하면
combined_string이라는 새 문자열이 생성되며,string1과string2가 연결된다.join메서드 사용:Join트레잇의join메서드를 사용하여 문자열 리스트를 구분 문자열과 함께 연결할 수 있다:1 2
let strings = vec!["Hello", "world"]; let combined_string = strings.join(" ");
이렇게 하면
combined_string이라는 새 문자열이 생성되며, 문자열 리스트의 문자열들이 공백으로 구분되어 연결된다.
각 방법에는 장단점이 있으며, 특정 상황에 따라 어떤 방법이 더 적합할 수 있다. 또한 Rust에서 문자열 연결을 위해 + 연산자, format! 매크로, push_str 메서드를 사용할 수 있으며, 이러한 방법들은 각각의 이점과 단점을 가지고 있다. Rust의 concat() 메서드는 리스트에 있는 문자열을 연결하는 데 사용할 수 있다.
부분 배열/부분 문자열, 부분 수열, 부분 집합
이 섹션에서는 이러한 유형 간의 차이점과 문제에서 이러한 유형을 만났을 때 주의해야 할 사항에 대해 간단히 알아보도록 하겠다.
부분 배열/부분 문자열
먼저, 부분 배열 또는 부분 문자열은 배열 또는 문자열의 연속적인 부분을 의미한다.
문제에서 다음과 같은 명시적인 제약 조건이 주어진다면:
- 합이
k보다 크거나 작은 경우 - 포함된 요소에 제한이 있는, 예를 들어 최대
k개의 고유한 요소 또는 중복이 허용되지 않는 경우
또는 다음과 같은 요구 사항이 있다면:
- 최소 또는 최대 길이
- 부분 배열/부분 문자열의 수
- 최대 또는 최소 합
슬라이딩 윈도우에 대해 생각해볼 필요가 있다. 단, 이러한 특성을 가진 모든 문제가 슬라이딩 윈도우로 해결될 필요는 없으며, 모든 슬라이딩 윈도우 문제가 이러한 특성을 가지고 있는 것도 아니다. 이러한 특성은 일반적인 지침으로만 사용되어야 한다.
문제의 입력이 정수 배열이며 여러 부분 배열의 합을 계산해야 하는 경우에는, 구간 합을 구성하는 것을 고려하도록 한다.
i와 j (포함) 사이의 부분 배열의 크기는 j - i + 1이다. 그리고 이것은, i나 그 이후에서 시작하여 j에서 끝나는 부분 배열의 수이기도 하다.
부분 수열
부분 수열은 배열/문자열의 요소 집합으로서, 동일한 상대적 순서를 유지하되 꼭 연속할 필요는 없다.
예를 들어,
[1, 2, 3, 4]의 부분 수열에는[1, 3],[4],[],[2, 3]이 포함되지만,[3, 2],[5],[4, 1]은 포함되지 않는다.
일반적으로 부분 수열 문제는 더 어렵다고 할 수 있다. 이는 첫 번째 장이므로 현재로서는 부분 수열 패턴에 대해 다루기진 않는다. 부분 수열은 이후 강의에서 다시 다루게 될 것이다. 특히 동적 프로그래밍은 많은 부분 수열 문제를 해결하는 데 사용된다.
지금까지 배운 패턴 중에서 부분 수열과 관련된 가장 일반적인 패턴은 두 입력 배열/문자열이 주어졌을 때의 투 포인터 기법이다(투 포인터 기법 관련 글에서 부분 수열과 관련된 문제를 하나 살펴봤다). 구간 합과 슬라이딩 윈도우는 부분 배열/부분 문자열을 나타내므로 부분 수열을 적용할 수 없다.
부분 집합
부분 집합은 원래 배열 또는 문자열의 어떤 요소들의 집합을 의미한다. 순서는 중요하지 않으며 요소들이 서로 인접해 있을 필요도 없다.
예를 들어,
[1, 2, 3, 4]가 주어진 경우,[3, 2],[4, 1, 2],[1]은 전부 부분 집합이다. 참고로, 동일한 요소를 포함하는 부분 집합은 동일하게 간주되므로,[1, 2, 4]는[4, 1, 2]와 동일한 부분 집합이다.
동일한 요소를 포함하는 부분 집합이 동일하게 간주된다면 부분 수열과 부분 집합의 차이점은 무엇인가 하는 의문이 들 수 있다. 부분 수열에서는 순서가 중요하다 - 예를 들어, 정수 배열이 있고 3개의 연속된 요소(예: 1, 2, 3)를 포함하는 부분 수열을 찾아야 하는 경우를 생각해 보자. 부분 집합에서 3개의 연속된 요소를 찾는 것보다 이것이 더 어렵다. 왜냐하면 부분 집합에서는 3개의 요소가 단순히 존재하기만 하면 되지만, 부분 수열에서는 요소들이 올바른 상대적 순서로 존재해야 하기 때문이다.
아직 첫 번째 장이기 때문에 부분 집합에 대해 자세히 이야기하기는 어렵다. 백트래킹 장에서 부분 집합이 사용되는 것을 볼 수 있을 것이다.
한 가지 주의할 점은 문제가 부분 수열을 다루지만 부분 수열의 순서가 실제로 중요하지 않다면(예: 부분 수열의 합이 필요하다면), 부분 집합과 동일하게 취급할 수 있다. 부분 집합을 다룰 때 부분 수열로는 할 수 없는 유용한 것은 입력을 정렬할 수 있다는 것이다. 순서가 중요하지 않기 때문이다.
출처: Leetcode