sia.log
로그인
sia.log
로그인
1장 자료구조가 중요한 까닭
sia
·
2022년 10월 18일
팔로우
0
1장
누구나 자료구조와 알고리즘
누자알
배열
자료구조
집합
0
누구나 자료구조와 알고리즘
목록 보기
1/3
1. 자료 구조
데이터: 모든 유형의 정보를 망라하는 용어
자료구조: 데이터를 조직하는 방법
2. 배열: 기초 자료 구조
배열: 데이터 원소들의 리스트
자료구조 연산
읽기: 특정 위치를 찾아보는 것
검색: 자료구조 내에서 특정 값을 찾는 것
삽입: 자료구조에 새로운 값을 추가하는 것
삭제: 자료구조에서 값을 제거하는 것
3. 속도 측정
연산이 얼마나 빠른가를 측정할 때는 시간 관점에서 측정하지 않고 얼마나 많은 단계가 필요한지를 논해야 한다.
연산의 속도 측정 → 시간 복잡도 측정
== 속도, 시간 복잡도, 효율성, 성능
4. 읽기
읽기: 배열 내 특정 인덱스에 어떤 값이 들어 있는지 찾아보는 것
컴퓨터의 특징
컴퓨터는 모든 메모리 주소에 한 번에 갈 수 있다.
컴퓨터는 배열을 할당할 때 어떤 메모리 주소에서 시작하는지도 기록해 둔다.
배열 읽기는 매우 효율적인 연산이다.
O(1)
5. 검색
검색: 배열에 특정 값이 있는지 알아본 후, 있다면 어떤 인덱스에 있는지 찾는 것
컴퓨터가 특정 값으로 바로 갈 수 없기 때문에 오래 걸린다.
컴퓨터의 특징: 컴퓨터는 모든 메모리 주소에 한 번에 접근하지만 각 메모리 주소에 어떤 값이 있는지 바로 알 수 없다.
O(N)
6. 삽입
배열에 새 데이터를 삽입하는 연산은 배열의 어디에 데이터를 삽입하는가에 따라 효율성이 다르다.
컴퓨터의 특징: 배열을 할당할 때 항상 배열의 크기를 기록한다
배열의 끝에 새 원소를 삽입하는 경우: 컴퓨터는 메모리 새롭게 추가되는 원소의 메모리 주소를 바로 알 수 있다.
배열의 처음이나 중간에 원소를 삽입하는 경우: 삽입할 공간을 만들기 위해 많은 데이터 조각을 이동시켜야 한다.
O(N)
7. 삭제
특정 인덱스의 값을 제거한다.
배열에 비어 있는 공간이 생기면 효율적이지 않으므로, 데이터를 옮겨 빈 공간을 메워야 한다.
O(N)
8. (배열기반)집합: 단 하나의 규칙으로 효율성이 달라진다
집합: 중복 값을 허용하지 않는 자료구조
배열 기반 집합: 값들의 단순 리스트, 배열과 거의 비슷하다. 그러나 집합은 중복 값의 삽입을 허용하지 않는다.
읽기, 검색의 시간 복잡도는 배열과 같다.
삽입
배열에서는 다른 값을 확인하지 않고 적절한 자리에 넣으면 끝이다.
집합에서는 새로운 값이 이미 집합에 들어 있는지 알아내야 한다.
중복 데이터를 허용하지 않기 때문이다.
따라서 삽입에는 검색이 우선이다.
최선의 시나리오: 집합의 끝에 삽입할 때 → O(N+1)
최악의 시나리오: 집합의 맨 앞에 삽입할 때 → O(2N+1)
sia
포스트 중 틀린 부분이 있다면 댓글로 지적해 주시면 감사하겠습니다.
팔로우
다음 포스트
2장 알고리즘이 중요한 까닭
0개의 댓글
댓글 작성