저는 뇌에 컴퓨터가 없는데여...그래도 코테 봐야돼서 어떻게든 알음알음 자료구조 공부 해야댐 기초부터 챠근차근
🐰 자료구조와 알고리즘, 그리고 성능
연산의 속도는 시간 관점이 아니라 단계 관점에서 생각해야 한다.
시간의 경우 연산을 수행하는 하드웨어에 따라 천차만별이기 때문에.
“연산에 얼마나 많은 단계가 필요한지”가 곧 효율성, 성능, 속도, 시간복잡도다.
-
코드의 성능 = 자료구조 + 알고리즘
-
어플리케이션의 요구사항에 알맞은 자료구조
ex 검색 기능이 중요한 어플리케이션의 경우 배열 < 정렬된 배열
삽입이 더 잦은 경우 배열 > 정렬된 배열 -
알고리즘은 단순히 어떤 과제를 완수하는 명령어 집합 일 뿐인데, 이제 얼마나 적은 단계의 명령어로 과제를 완수할 수 있는가~가 중요
🐰 연산의 종류
자료 구조에서 수행할 수 있는 연산은 대표적으로 이렇게 네 가지!
-
읽기
자료구조의 특정 위치를 찾아보는 것
-
검색
자료구조 내에서 특정 값을 찾아보는 것
-
삽입
-
삭제
🐰 배열
최악의 경우를 기준으로
-
읽기: 1단계
컴퓨터는 모든 메모리 주소에 한 번에 접근이 가능하다.
- 배열 할당 시 배열이 시작하는 메모리 주소를 기록해두기 때문에, 간단한 덧셈으로 배열 내에 어떤 인덱스든 빠르게 접근 가능하다.
-
검색: 선형검색의 경우 N단계(찾고자 하는 값이 배열 맨 끝에 위치한 경우)
-
삽입: N+1단계(0번째에 삽입)
-
삭제: N단계(0번째 원소 삭제)
🐰 집합
중복값을 허용하지 않는 배열(배열기반집합)
위 특성 때문에 배열에 비해 삽입의 효율성이 떨어진다.
삽입 시 검색을 통해 중복 여부를 확인한 다음, 삽입을 진행해야 함.
삽입: N+(N+1)
그럼에도 불구하고, 어플리케이션이 중복 방지 기능을 필요로 한다면 집합이 아닌 배열을 써야 한다. 그렇지 않다면 배열을 쓰는 게 맞음. 구현하고자 하는 어플리케이션의 요구사항을 잘 파악해야 함.
🐰 정렬된 배열
값이 항상 순서대로 있어야 하는 배열
이 특성을 지키기 위해 삽입 시에 올바른 위치를 찾아 삽입해야 함.
검색이 빠르다는 장점! 이진탐색을 사용할 수 있기 때문이죠
선형탐색을 사용하더라도 기본적으로 일반 배열보다는 빠릅니당.
찾고자 하는 값보다 큰 값이 나왔을 경우 바로 검색을 중단할 수 있기 때문에.
(찾고싶은 값이 배열에 없는 경우)
이진탐색은 한 단계를 거칠 때마다 원소의 개수를 1/2로 만들어버린다.
== 데이터의 개수가 두 배로 늘어나야지 한 단계가 추가된다.
== 매우 효율적.
원소의 개수가 많아질수록 선형탐색과 이진탐색의 성능 차이는 점점 커진다.
물론 삽입의 경우 여전히 배열이 효율적. (순서 지킬 필요 없이 맨 뒤에 삽입하면 되니까)
그렇지만 이진탐색을 활용하면 정렬된 배열의 삽입도 보다 효율적으로 수행할 수 있다.
이진탐색을 활용해 올바른 삽입 위치를 빠르게 파악 가능함.
배열을 쓸 것이냐, 정렬된 배열을 쓸 것이냐 또한 내가 어떤 기능을 구현하고 싶은가에 따라 골라 쓰면 된다.
