바킹독님의 강의를 참고하였습니다. https://blog.encrypted.gg/category/강좌/실전%20알고리즘 '강좌/실전 알고리즘' 카테고리의 글 목록 blog.encrypted.gg + 해당 카테고리엔 알고리즘 문제풀이와 관련된 내용을 업로드. + 기록해두고 싶은 부분만 정리해 둠. 정의&성질 덱 양쪽 끝에서 삽입과 삭제가 전부 가능하다. => 스택과 큐를 덱의 특수한 예시라고 생각해도 괜찮다. 자명함. STL deque STL deque은 독특하게도, vector랑 비슷한데, front에서도 O(1)에 추가와 제거가 가능한 느낌이 강하다. insert, erase도 있고, 인덱스로 원소에 접근도 할 수 있다. 이와 같이, STL vector에서 제공되는 기능을 STL deque에서도 다 제..
바킹독님의 강의를 참고하였습니다. https://blog.encrypted.gg/category/강좌/실전%20알고리즘 '강좌/실전 알고리즘' 카테고리의 글 목록 blog.encrypted.gg + 해당 카테고리엔 알고리즘 문제풀이와 관련된 내용을 업로드. + 기록해두고 싶은 부분만 정리해 둠. 정의&성질 큐 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조이다. 스택에서는 먼저 들어간 원소가 나중에 나왔지만, 큐에선 먼저 들어간 원소가 먼저 나오게 된다. 상상해 보면 자명하다. 4번 성질의 이야기는 스택에서 다루었으니 생략. STL queue STL queue를 제공한다. 큐는 보통 BFS와 Flood Fill을 할 때 쓰게 된다. #include using namespace std;..
바킹독님의 강의를 참고하였습니다. https://blog.encrypted.gg/category/강좌/실전%20알고리즘 '강좌/실전 알고리즘' 카테고리의 글 목록 blog.encrypted.gg + 해당 카테고리엔 알고리즘 문제풀이와 관련된 내용을 업로드. + 기록해두고 싶은 부분만 정리해 둠. 정의&성질 스택 한쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조. 프링글스 통을 생각하면 된다. 생각을 해보면, 자명하게 위의 모든 경우들이 이해가 된다. 성질 4번(제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능) 의 뜻을 잘 이해할 필요가 있는데, 원래 스택이라는 자료구조는 원소의 추가/제거/제일 상단의 원소 확인의 기능만 제공하는 자료구조이다. 따라서, 위 성질은 스택에서 제공하는 기능이 ..
바킹독님의 강의를 참고하였습니다. https://blog.encrypted.gg/category/강좌/실전%20 알고리즘 '강좌/실전 알고리즘' 카테고리의 글 목록 blog.encrypted.gg + 해당 카테고리엔 알고리즘 문제풀이와 관련된 내용을 업로드. + 기록해두고 싶은 부분만 정리해 둠. 정의&성질 음 그러하다. 배열은 메모리 상에 원소를 연속하게 배치한 자료구조라서, k번째 원소의 위치를 바로 계산할 수 있다. 시작 주소에서 k칸만큼 오른쪽으로 가면 되기 때문. => 그러기에 k번째 원소를 O(1)에 확인하거나 변경할 수 있다. 배열은 다른 자료구조와 다르게 추가적으로 소모되는 메모리의 양이 거의 없다. 메모리 상에 데이터들이 붙어있으므로 Cache hit rate 가 높다. 메모리 상에 연속..
