Intro.
안녕하세요 Pu드로이드 입니다^^
취업차.. 코딩테스트 준비를 위해 1일 1백준 알고리즘 풀이를 꾸준히 하고 있는데요!
더 나은 문제 접근을 위해 유튜브 바킹독님의 영상으로 알고리즘 기본기를 다질 계획이며,
동시에 블로그 포스팅을 통해 정보를 기록하고 공유하려 합니다!
궁금한 점 질문, (정중한)조언을 매우 매우 환영하니 부담 없이 댓글 부탁드려요!
배열

특징
- 추가적으로 소모되는 메모리 양이 거의 없음
- 메모리 상에 붙어있어서 Cache hit rate가 높음
- 메모리 연속한 구간을 잡아야해서 할당 제한
시간복잡도
- 인덱스 접근 및 변경 : O(1)
- 맨 처음 원소 제거 : O(1)
- 맨 끝 원소 추가 : O(1)
- 맨 끝 원소 제거 : O(1)
- 임의의 위치 원소 추가 : O(n)
- 임의의 위치 원소 제거 : O(n)
kotlin 배열 선언 Tip
fun main(){
val array = IntArray(100){it+1} // 1부터 100까지 배열이 들어감
val arr = Array(26){'a' + it} // a부터 z 까지 배열이 들어감
}
연결리스트

- 시간복잡도
- 인덱스 접근 : O(k)
- 원하는 위치의 주소를 알고있을경우 → 임의의 위치에 원소 추가, 제가 : O(1)
- 원하는 위치의 주소를 모를경우 → 임의의 위치에 원소 추가, 제가 : O(N)
(그곳까지 가야하기 때문에!!) - 메모리상 연속되어 있지 않아 Cache hit rate가 낮으나, 할당 쉬움
- 시간복잡도
- 인덱스 접근 : O(k)
- 원하는 위치의 주소를 알고있을경우 → 임의의 위치에 원소 추가, 제가 : O(1)
- 원하는 위치의 주소를 모를경우 → 임의의 위치에 원소 추가, 제가 : O(N)
- (그곳까지 가야하기 때문에)
- 메모리상 연속되어 있지 않아 Cache hit rate가 낮으나, 할당 쉬움
💡 Cache hit rate
CPU가 필요한 주소를 기억장치에 요청할 떄 순서는 다음과 같다.
CPU → Cache → 주기억장치(메모리) → 보조기억장치
Cache 자주 쓰이는 주소를 캐시에 담아두며, 연결리스트 특정상 메모리에 연속하지 않기 때문에 배열보다 Cache hit rate가 낮음
궁금한 점 질문, (정중한)조언을 매우 매우 환영하니 부담 없이 댓글 부탁드려요!
'알고리즘' 카테고리의 다른 글
| [알고리즘] DFS - 깊이 우선 탐색이란? (4) | 2023.12.21 |
|---|---|
| [알고리즘] BFS - 너비 우선 탐색이란? (0) | 2023.12.21 |
| [알고리즘] 자료구조 스택, 큐, 덱 (0) | 2023.12.13 |
| [알고리즘] 시간복잡도, Kotlin 자료형 (0) | 2023.12.11 |