[TIL][W1/Sat] 배열/문자열

학습 사이트

https://leetcode.com/explore/learn/card/array-and-string/

https://www.algolist.net/Data_structures/Array

두 사이트 모두 c++과 java 위주로, 두 언어를 비교하며 설명하였다. 

 

주요 키워드

• 배열 vs 동적배열 (dynamic array)
• 배열과 동적배열의 기본 연산자(basic operation)
• 다차원배열(multidimensional arrays) 이해와 이차원배열 이해
• 문자열string의 이해와 문자가 가진 다른 특징들?
• 투 포인터 기술 two-pointer technique

배열

순차적으로 요소들의 집합을 보관하기 위한 데이터 구조. (An array is a basic data structure to store a collection of elements sequentially) 요소들은 임의로 접근 가능하다. 왜? 배열의 index가 있기 때문에 가능하다.

배열은 초기화/생성할 때 배열의 크기를 특정하기 때문에, 용량이 정해져 있다. (an array has a fixed capacity) 그런데 이게 나중엔 불편하고 낭비가 많다. 따라서 일부 프로그래밍 언어는 여전히 임의 접근이 가능하나 가변적인 크기의 내장(built-in) 동적 배열을 제공한다.(C++의 vector와 java의 ArrayList)

pivot index를 구하라

pivot index란? : 배열의 특정 인덱스 왼쪽 원소들의 합과 오른쪽 원소들의 합이 정확히 일치할 때의 index

이차원배열

1차원배열과 마찬가지로 요소들의 시퀀스로 이루어져있지만, 선이 아니라 직사각형 격자로 배열될 수 있다. 일부 언어는 2차원배열을 내부적으로는 1차원배열로 구현한다.

c++는 1차원 배열로 2차원 배열을 저장한다.

다른 일부 언어는 실은 1차원배열이다. (java)

https://leetcode.com/explore/learn/card/array-and-string/202/introduction-to-2d-array/1166/

• 차이가 무엇일까?

2차원배열도 동적 배열이 가능하다. 중첩된 동적 배열이 될 수도 있다.

문자열

문자열은 실제로는 유니코드 문자의 배열이다.

비교 기능

문자열에서 ‘==’를 사용할 수 있을까? (=Does the language support operator overloading?)

c++: ==로 두 문자를 비교할 수 없다.

Java:==로 두 문자를 비교할 수 없다. 왜냐하면 java는 ==를 두 객체가 같은 객체인지 비교할 때 사용하기 때문이다.

 

그렇다면 파이썬은?

https://www.geeksforgeeks.org/operator-overloading-in-python/

==로 두 문자를 비교할 수 있다. 파이썬은 두 객체의 값이 같은지 비교하는 등가성(equality) 비교에 ==를 사용하고, 두 객체의 값과 식별 번호(메로리상의 고유주소)까지 같은지 비교하는 동일성(identity) 비교에는 is를 사용한다.

Immutable or Mutable

문자열이 Immutable 하다란 뜻은 문자열이 한번 선언되면 그 값(내용)을 바꿀 수 없다는 뜻이다.

c++는 배열에서 한 것처럼 값 변경이 가능하지만, java나 파이썬에서는 문자열과 int는 값을 변경할 수 없다.

x="Hello World"
x[5]=','
print(x)

Traceback (most recent call last):
  File "test.py", line 2, in <module>
    x[5]=','
    ~^^^
TypeError: 'str' object does not support item assignment

`the time complexity of these built-in operations` 를 유의하라

문자열의 길이가 N이라면, 문자열 찾기와 추출 작업의 시간복잡도는 O(N)이고, 문자열이 immutable한 언어에서는 연결을 할 때 주의해야한다.

Immutable String: 문제와 해결방안

수정작업

• 수정은 할 수 없으므로 새 문자열을 만들어야 한다.

문자열 연결

• 새 문자열에 공간을 할당하고 이전 문자열의 내용을 복사하고 새 문자열에 추가하여 연결되는 식이라 시간이 많이 소모된다. 즉…
• Therefore, the time complexity in total will be: 

``` 5 + 5 × 2 + 5 × 3 + … + 5 × n

= 5 × (1 + 2 + 3 + … + n)

= 5 × n × (n + 1) / 2, which is O(n2).```

문자열을 mutable하게 쓰고 싶다면?

1. char array 로 변환한다. 
2. 문자의 연결이 잦다면, 다른 데이터 구조를 사용하라.

Two Pointer Technique

전형적으로, 반복할 때 맨 처음 원소에서 시작해서 맨 마지막 원소에서 끝나는 하나의 포인터를 사용하지만 가끔 2개의 포인터를 반복 중에 사용해야 할 때가 있다.

중간에서 만나요

포인터 하나는 처음→ 끝, 다른 포인터 하나는 끝→처음.

어떨 때 이런 포인터 기술을 사용할까? 어떤 배열의 양 끝에서 시작하여 중간에서 만날 때까지 반복하기를 원할 때 이런 전략을 사용한다. sorted 배열에서 주로 사용되는 기술이다.

다른 스텝으로 갑시다

23.10.14 러프하게 공부.