자료구조란 무엇일까?
자료구조는 데이터를 저장하고 관리하는 방식 또는 방법을 말해요
프로그래밍 및 컴퓨터 과학에서는 데이터의 효율적인 접근, 수정, 삽입, 삭제 등을 위해 다양한 자료구조를 사용해요.
자료구조의 선택은 문제 해결의 효율성과 알고리즘의 성능에 큰 영향을 미쳐요.
배열 (Array)
배열은 여러 개의 같은 타입의 데이터를 순서대로 저장하는 구조에요.
서랍장을 생각하면 이해하기 편해요.
서랍장이 여러개의 서랍을 연속적으로 갖고 있고 각 서랍에는 번호(인덱스)를 붙여서 그 서랍에 쉽게 접근할 수 있어요
접근
서랍장에서 서랍에 접근하기 위해서는 O(1)의 시간 복잡도면 충분해요. 그저 인덱스가 붙여져 있는 서랍을 찾으면 되거든요.
만약 배열의 시작 주소가 0이고 데이터의 크기가 8이라면 3 인덱스( 4번 서랍)를 가진 데이터의 주소는 0+8*3=24로 한번에 계산하고 접근할 수 있어요.
수정
서랍 내용물을 수정하는 방법은 수정하고자 하는 인덱스를 가진 서랍을 찾고 그 안의 내용물을 수정하면 됩니다.
따라서 수정 역시 O(1) 의 시간복잡도를 갖고 있어요.
삽입
각 서랍(배열의 인덱스)은 바로 뒤의 서랍과 연결되어 있어서, 특정 위치에 새로운 내용물을 추가하려면 많은 작업이 필요해요.
만약 서랍장이 10개의 서랍으로 구성되어 있고, 새로운 내용물을 5번째 서랍에 추가하려고 한다면
서랍 5부터 8까지의 내용물을 모두 한 칸씩 뒤로 옮기고 5번째 서랍에 내용물을 추가하면 돼요.
이 작업은 4개의 내용물을 이동시켜야 하므로, O(n)의 시간 복잡도가 필요해요 (n은 이동해야 하는 서랍의 개수).
삭제
배열에서 특정 위치에 있는 원소를 제거할 때, 그 위치 뒤에 있는 모든 원소를 한 칸씩 앞으로 이동시켜야 합니다. 이렇게 해야 원소의 순서가 유지되요.
예를 들어, 서랍장에 10개의 서랍이 있고, 5번째 서랍에 있는 내용물을 제거한다고 가정해 볼게요. 그러면 6번째 서랍부터 10번째 서랍까지의 내용물들을 한 칸씩 앞으로 이동시켜야 해요. 결과적으로 6번째 서랍의 내용물이 5번째 서랍에 위치하게 되고, 10번째 서랍의 내용물이 비게 돼요
중간에서 내용물을 제거하는 작업은 5개의 내용물을 이동시켜야 하므로, O(n)의 시간 복잡도가 필요해요. (n은 이동해야 하는 서랍의 개수)
배열의 특성
- 장점: 인덱스를 통해 직접 접근이 가능하여 데이터 접근이 빨라요 (O(1)).
- 단점: 삽입이나 삭제 작업이 비효율적입니다. 특히 중간에 삽입할 경우, 삽입 위치 뒤에 있는 모든 요소를 이동해야 하므로 비용이 커요 (O(n)).
| 접근 | 수정 | 삽입 | 삭제 | |
| 시간 복잡도 | O(1) | O(1) | O(N) | O(N) |
배열의 종류
배열의 종류에는 정적 배열과 동적 배열이 존재해요.
-정적배열은 배열의 크기가 정해져 있는 것을 의미해요
-동적배열은 배열의 크기가 정해져 있지 않고 데이터의 개수에 따라 크기가 변해요.
두배열의 시간복잡도와 공간복잡도에 대한 설명은
다음 포스팅에서 설명할게요~~
'자료 구조( data structure)' 카테고리의 다른 글
| [자료 구조 / data structure] 그래프(graph)를 표현하는 방법 3가지. (0) | 2025.01.11 |
|---|