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

2023. 10. 14. 23:32· 공부기록/Algorithm
목차
  1. pivot index를 구하라
  2. 이차원배열
  3. 비교 기능
  4. Immutable or Mutable
  5. Immutable String: 문제와 해결방안
  6. Two Pointer Technique
  7. 중간에서 만나요
  8. 다른 스텝으로 갑시다

학습 사이트

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 러프하게 공부.

'공부기록 > Algorithm' 카테고리의 다른 글

[TIL][TUE] 병합정렬/퀵정렬  (1) 2023.10.17
[TIL][Mon] 정렬  (2) 2023.10.16
[TIL][W2/Mon] 복잡도, Big O notation  (0) 2023.10.16
[TIL][W1/Sun] 소수찾기  (0) 2023.10.16
[TIL][W1/Sun] 반복  (0) 2023.10.15
  1. pivot index를 구하라
  2. 이차원배열
  3. 비교 기능
  4. Immutable or Mutable
  5. Immutable String: 문제와 해결방안
  6. Two Pointer Technique
  7. 중간에서 만나요
  8. 다른 스텝으로 갑시다
'공부기록/Algorithm' 카테고리의 다른 글
  • [TIL][Mon] 정렬
  • [TIL][W2/Mon] 복잡도, Big O notation
  • [TIL][W1/Sun] 소수찾기
  • [TIL][W1/Sun] 반복
J융
J융
Recording of development
J융
Develop day by day
J융
전체
오늘
어제
  • 분류 전체보기 (67)
    • 공부기록 (63)
      • CS (8)
      • OS (15)
      • Algorithm (19)
      • Web (3)
      • HTML&CSS (6)
      • Electron (1)
      • JavaScript (5)
      • Network (0)
      • C (2)
      • Python (3)
      • Git (1)
    • 개발일기 (3)
      • Alice기록 (0)
      • Krafton Jungle 기록 (3)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 수강후기
  • 개발일기
  • os
  • 앨리스트랙
  • 알고리즘
  • 크래프톤정글
  • cs지식
  • 정글공부키워드
  • #cs기초
  • 기술면접대비
  • pintos
  • CG
  • cs기초
  • vm
  • 비전공자개발자
  • 부트캠프
  • 엘리스AI트랙
  • JS기초
  • fe
  • Web

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
J융
[TIL][W1/Sat] 배열/문자열
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.