개요
알고리즘 문제와 관련하여 배열(1차원)과 문자열은 매우 유사하다: 둘 다 요소의 정렬된 그룹을 나타낸다. 대부분의 알고리즘 문제는 입력의 일부로 배열 또는 문자열이 포함되므로, 기본 연산에 익숙해지고 가장 일반적인 패턴을 학습하는 것이 중요하다.
“배열”이라는 용어는 언어에 따라 다른 의미를 가질 수 있다. 예를 들어, 파이썬은 배열 대신 “리스트”를 주로 사용하며 이는 매우 유연하다. 초기화는 arr = []로 쉽게 할 수 있으며, 리스트에 저장하는 데이터의 유형이나 리스트의 크기에 대해 걱정할 필요가 없다. C++과 같은 다른 언어는 초기화할 때 배열의 크기와 데이터 유형을 지정해야 하지만, 리스트에 대한 지원도 있다(C++의 std::vector와 같은).
기술적으로, 배열의 크기를 조정할 수는 없다. 크기 조정이 가능한 것은 동적 배열이나 리스트이다. 알고리즘 문제의 맥락에서 사람들이 배열에 대해 이야기할 때, 대체로 동적 배열을 의미한다. 앞으로 우리는 동적 배열/리스트에 대해 계속 이야기할 것이지만, 그냥 통틀어서 “배열”이라는 단어를 사용할 것이다.
마찬가지로, 문자열은 언어에 따라 다르게 구현된다. 파이썬과 자바에서는 문자열을 변경할 수 없다(불변). C++에서는 문자열을 변경할 수 있다(가변). 인터뷰에서 사용할 언어에 대한 배열과 문자열의 구현 사항(인터페이스 등)을 알아두어야 한다. 각 언어별로 다른 구현에 대해 모두 살펴볼 시간이 없으므로, 아직 익숙하지 않다면 선택한 언어에 대해 직접 조사해보자.
가변: 변경할 수 있는 데이터 유형
불변: 변경할 수 없는 데이터 유형
불변인 것을 변경하고자 한다면, 전체를 새로 만들어야 한다.
왜 가변 또는 불변인지에 대해 신경을 써야 할까? 가변 배열 arr = ["a", "b", "c"]와 불변 문자열 s = "abc"가 있다고 해보자. 여기서 "abd"로 값을 바꾸고 싶다고 할 때, arr[2] = "d"를 쉽게 수행할 수 있지만, s[2] = "d"는 수행할 수 없다. 따라서 문자열 s = "abd"로 바꾸길 원한다면, 처음부터 전체를 새로 만들어야 한다.
이처럼 작은 문자열의 경우 큰 문제가 되지 않지만, 가끔 100,000자에 달하는 문자열을 다루게 되는 경우도 있으며, 단 하나의 문자를 수정하기 위해 문자열의 새 버전을 만드는 것은 매우 비용이 많이 드는 작업이다($n$의 크기에 따라 $O(n)$ 비용이 든다).
이전에 언급한 바와 같이, 알고리즘 문제의 대다수는 배열 또는 문자열을 포함하고 있다. 이들은 굉장히 다양한 자료 구조이며 한 편의 글로는 관련된 모든 문제 해결 기법을 나열하는 것이 불가능하다.
진도 나가기에 앞서, 배열과 문자열 작업의 복잡도를 간단히 살펴보자.
| 연산 (Operation) | 배열/리스트 | 문자열(불변) |
|---|---|---|
| 끝에 추가 (Appending) | $O(1)$ | $O(n)$ |
| 끝에서 빼기 (Popping) | $O(1)$ | $O(n)$ |
| 끝이 아닌 곳에 삽입 (Insertion) | $O(n)$ | $O(n)$ |
| 끝이 아닌 곳에서 삭제 (Deletion) | $O(n)$ | $O(n)$ |
| 요소 수정 (Modifying) | $O(1)$ | $O(n)$ |
| 임의의 위치 접근 | $O(1)$ | $O(1)$ |
| 요소 존재 여부 확인 (exists) | $O(n)$ | $O(n)$ |
리스트의 끝에 추가하는 작업은 상환 시간 복잡도(amortized time complexity)가 $O(1)$이다.
출처: Leetcode