[알고리즘] 배열, 연결리스트 with Kotlin

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가 낮음

 

 

 

 

 

궁금한 점 질문, (정중한)조언을 매우 매우 환영하니 부담 없이 댓글 부탁드려요!