1. 배열(Array)
배열은 같은 자료형의 데이터를 메모리상에 연속적으로 저장하는 자료구조이다. 각 데이터는 인덱스를 통해 접근한다.
💡이렇게 생긴 구조가 배열이다.
서랍장에 각각 번호가 붙어 있고, 인덱스를 통해 원하는 서랍에서 물건(데이터)을 꺼내는 것과 유사하다.
arr[0] = 10,arr[1] = 20,arr[2] = 30이런식으로 인덱스를 통해 값에 접근 가능한 구조이다.
배열의 특징
- 빠른 인덱스 접근 : O(1)
→ 인덱스로 데이터를 바로 불러올 수 있다. - 삽입/삭제는 느림 : 중간 삽입/삭제 시 O(N)
→ 배열에서 중간에 데이터를 삭제/삽입 시, 그 뒤 요소들을 한칸씩 밀거나 당겨야 한다. “박스를 다 들어서 다시 정렬”한다고 생각하면 쉽다. 그래서 시간복잡도가 O(N)인 것이다. - 메모리상 연속적인 공간할당
→ 배열은 메모리에서 하나의 블록으로 할당된다. 이 덕분에 인덱스 계산도 단순하게시작 주소 + (인덱스 * 자료형 크기)로 바로 위치를 찾아갈 수 있다.
배열의 주요 연산 시간복잡도
| 연산 | 시간복잡도 |
|---|---|
| 인덱스 접근 | O(1) |
| 탐색 | O(N) |
| 삽입 (중간) | O(N) |
| 삭제 (중간) | O(N) |
2. 문자열 (String)
문자열은 문자(char)의 집합으로 이루어진 자료구조이다. 쉽게 말해, 문자 배열로 구성되어 있으며, 문자열은 문자들이 순서대로 저장된 데이터의 묶음이다.
문자열 구조 예시
💡이렇게 생긴 구조가 문자열이다.
문자 하나하나가 박스 안에 저장되어 있으며, 배열처럼 인덱스를 통해 각 문자에 접근할 수 있다.
예를 들어s = "hello"라면,s[0] = 'h',s[1] = 'e'이런 식으로 인덱스를 통해 개별 문자에 접근한다.
문자열의 특징
- 빠른 인덱스 접근: O(1)
→ 배열처럼 문자열도 인덱스를 통해 각 문자를 빠르게 가져올 수 있다.
- 수정이 어려움 (불변성)
→ Python과 Java 같은 언어에서는 문자열이 불변(immutable)이다. 즉, 문자열의 특정 인덱스를 직접 수정할 수 없고, 새로운 문자열을 만들어야 한다. 위에서 배운 배열과의 차이점이다.
- 메모리 상 연속적인 공간에 저장됨
→ 문자열도 내부적으로 문자 배열로 연속적인 메모리에 저장된다.
문자열의 주요 연산 시간복잡도
| 연산 | 시간복잡도 |
|---|---|
| 인덱스 접근 | O(1) |
탐색 (in, find) | O(N) |
| 문자열 결합 | O(N) |
| 슬라이싱 | O(N) |
문자열의 실생활 비유
- 문자열은 편지 봉투에 문자를 하나씩 순서대로 넣어둔 것과 비슷하다.
- 봉투에 담긴 각 문자는 순서대로 꺼낼 수 있지만, 편지 봉투 안에서 직접 문자를 바꿀 수는 없다 (불변성 비유).
이유민