티스토리

나만의 저장소

검색하기

블로그 홈

나만의 저장소

backend-repository.tistory.com/m

do_hyuk 님의 블로그입니다.

구독자: 0

방명록 방문하기

주요 글 목록

[실전 알고리즘] 큐 정의와 성질 저번에 정리한 스택이랑 이번에 배울 큐랑 비슷한게 많다. 큐는 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조이다. 스택에서는 먼저 들어간 원소가 나중에 나왔는데 큐에서는 먼저 들어간 원소가 먼저 나오게 된다. 스택을 FILO(First In Last Out)이라고 한 것과 비슷하게 큐를 FIFO(First In First Out)이라고 하기도 한다. 큐의 성질 원소의 추가가 O(1) 원소의 제거가 O(1) 제일 앞/뒤의 원소 확인이 O(1) 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 스택에서는 보통 원소가 추가되고 제거되는 곳을 top이라고 부르고, 원소가 위 아래로 배치된 것으로 생각을 많이 하는데 큐에서 추가되는 곳을 rear, 즉 뒤 쪽이라고.. 공감수 0 댓글수 0 2024. 1. 12.
[실전 알고리즘] 스택 1. 정의와 성질 자료구조에서의 스택은 한쪽 끝에서 원소를 넣거나 뺄 수 있는 자료 구조이다. 스택은 구조적으로 먼저 들어간 원소가 제일 마지막에 나오는데, 이런 의미로 FILO(First In Last Out) 자료구조라고 부르기도 한다. 참고로 큐나 덱도 스택처럼 특정 위치에서만 원소를 넣거나 뺄 수 있는 제한이 걸려있다. 스택의 성질 원소의 추가가 O(1) 원소의 제거가 O(1) 제일 상단의 원소 확인 O(1) 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 스택에서는 제일 상단이 아닌 나머지 원소들의 확인/변경 기능이 제공되지 않는다. STL stack에서도 이 기능은 없다. 2. 기능과 구현 const int MX = 1000005; int dat[MX]; int pos = 0;.. 공감수 0 댓글수 0 2024. 1. 10.
[실전 알고리즘] 연결 리스트 연결 리스트가 무엇인지 알아보고, 구현도 해볼 것이다. 1. 정의와 성질 연결 리스트 정의 연결 리스트란 원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조이다. 원소들은 배열과는 다르게 이곳 저곳 흩어져있다. 연결 리스트 성질 1. k번째 원소를 확인/변경하기 위해 O(k)가 필요 - 배열과 다르게 공간에 원소들이 연속해서 위치하고 있지 않기 때문 2. 임의의 위치에 원소를 추가/임의 위치의 원소 제거는 O(1) - 배열과 비교앴을 때 큰 차이가 있는 성질이고, 연결 리스트의 큰 장점이다. 3. 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움 - 메모리 상에 데이터들이 연속해있지 않으니까 Cache hit rate가 낮지만 할.. 공감수 0 댓글수 0 2024. 1. 8.
[실전 알고리즘] 배열 지금까지 프로그래밍 언어의 관점에서 배열을 다뤘었기 때문에 자료구조로써의 배열을 익힐 필요가 있어 공부하였다. 1. 정의와 성질 배열의 정의 배열이란 메모리 상에 원소를 연속하게 배치한 자료구조를 말한다. C++에서는 이미 선언된 배열의 길이를 변경하는게 불가능하지만, 자료구조로써의 배열에서는 길이를 마음대로 늘리거나 줄일 수 있다고 생각하겠다. 배열의 성질 1. O(1)에 K번째 원소를 확인/변경 가능 - 시작 주소에서 k칸 만큼 오른쪽으로 가면 되기 때문 2. 추가적으로 소모되는 메모리의 양(=overhead)가 거의 없음 - 다른 자료구조와는 다르게 추가적으로 소모되는 메모리 양이 거의 없슴 3. Cache hit rate가 높음 - 메모리 상에 데이터들이 붙어있으니까 Cache hit rate가 .. 공감수 0 댓글수 1 2024. 1. 3.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.