PS/알고리즘3 스택 1. 스택의 성질- 원소의 추가가 O(1)- 원소의 제거가 O(1)- 제일 상단의 원소 확인이 O(1)- 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 2025. 1. 26. 연결리스트 1. 연결리스트의 성질- k번째 원소를 확인/변경하기 위해 O(k)가 필요함- 임의의 위치에 원소를 추가/임의 위치의 원소 제거는 O(1)- 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움 2. 연결리스트의 종류 3. 배열 vs 연결 리스트 (선형리스트의 비교)-> 연결리스트는 각각의 원소가 다음 위치 값을 지니고 있기 때문에 추가적으로 O(N)의 공간이 필요함 4. 연결리스트의 연산 2025. 1. 26. 배열 배열:메모리 상에 원소를 연속하게 배치한 자료구조배열의 성질:1. O(1)에 k번째 원소를 확인/변경 가능2. 추가적으로 소모되는 메모리의 양(=overhead)가 거의 없음3. Cache hit rate가 높음(메모리가 붙어 있기 때문에)- 캐시(Cache): 시스템의 성능을 향상시키기 위해 자주 사용하는 데이터를 임시로 저장하는 고속 메모리입니다.- 히트(Hit): 프로그램이 필요한 데이터를 캐시에서 성공적으로 찾는 경우입니다.- 미스(Miss): 프로그램이 필요한 데이터를 캐시에서 찾지 못하고, 메인 메모리나 더 느린 저장장치에서 데이터를 가져오는 경우입니다.- 캐시 히트율(Cache Hit Rate): 전체 메모리 접근 중에서 캐시가 성공적으로 데이터를 제공한 비율입니다. 쉽게 말해, 캐시 접근 .. 2025. 1. 13. 이전 1 다음
