고양이와 별무리 도서관 Post List

콜 스택(Call Stack)이란, 프로그램이 실행되는 동안 현재 실행중인 함수(혹은 Procedure)에 관한 정보를 관리하기 위한 자료 구조입니다. 그리고 스택 프레임(Stack Frame)은 콜 스택에 담기는 메모리 블록으로, 함수에서 사용되는 값이나 반환 주소 등을 담고 있는 데이터 블록입니다. 콜 스택(Call Stack) 콜 스택은 프...

뱀과 사다리 게임은 1번 칸에서 시작하여 주사위를 굴려 100번 칸까지 이동하는 게임입니다. 그런데 이때, 뱀 칸과 사다리 칸이 존재하고, 뱀 칸에 도착하면 낮은 칸으로 순간이동하고 사다리 칸에 도착하면 높은 칸으로 순간이동 하게 됩니다. 즉, 16928번: 뱀과 사다리 게임 (acmicpc.net) 문제는 100번 칸까지 이동하면서 최대한 사다리...

개요 헤더 파일: <queue> STL 컨테이너 어댑터(adapter container): 기본적으로 deque의 기능을 제한하여 만들어진 자료구조. 탐색 시간: $O(1)$ (Front 탐색) 요소 추가/삭제: $O(1)$ (Enqueue 및 Dequeue) 큐(Queue)는 선형 자료구조이면서 선입선출(First I...

2178번: 미로 탐색 (acmicpc.net) 문제는 시작 위치에서 도착 위치인 (N - 1, M - 1)까지 이동할 때 지나야 하는 최소의 칸 수를 찾는 문제입니다. 이때, 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타냅니다. 접근법 이 문제는 최단 경로를 찾는 문제이므로 너비 우선 탐색(BFS) 알고리즘을 사용해서 풀어...

개요 헤더 파일: <stack> STL 컨테이너 어댑터(adapter container): 기본적으로 deque의 기능을 제한하여 만들어진 자료구조. 탐색 시간: $O(1)$ (TOP 탐색) 요소 추가/삭제: $O(1)$ 스택(Stack)은 선형 자료구조이면서 후입선출(Last In First Out, LIFO) 특성을...

2606번: 바이러스 (acmicpc.net) 문제는 1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 찾는 것입니다. 즉, 1번 컴퓨터에서 뻗어갈 수 있는 모든 정점들을 찾는 문제입니다. 이 문제는 그래프 문제로 깊이 우선 탐색(DFS, Depth-first search)나 너비 우선 탐색(BFS...

개요 헤더 파일: <deque> STL 시퀀스 컨테이너 (sequence container): 시퀀스 블록 집합 컨테이너 탐색 시간: $O(1)$ 요소 추가/삭제 양쪽 끝에서의 추가/삭제: $O(1)$ 중간에서의 요소 추가/삭제: $O(N)$ 덱(Deque, Double-En...

vector를 사용하다 보면 다음과 같은 에러를 한 번씩은 봤을 수 있습니다. erase()를 쓰거나 insert()를 쓰다 보면 가끔 invalidated iterator라는 표현이 나옵니다. Expression: can’t increment invalidated vector iterator 만약, 본 적 없다면, 이미 알고 잘 쓰고 계시거나...

11286번: 절댓값 힙 (acmicpc.net) 문제는 힙을 절대값을 고려해서 만드는 문제입니다. 힙(heap)이란, 최대값이나 최소값을 빠르게 찾기 위한 완전 이진 트리를 기본으로 한 자료구조로, 매 삽입/삭제시 조건을 만족하는 정렬을 수행합니다. 이때 부모(P)와 자식(C) 사이의 정렬을 수행하지만, 자식간(LC, RC)의 정렬은 보장하지 않...

개요 헤더 파일 <list>: 이중 연결 리스트(doubly linked list) <forward_list>: 단일 연결 리스트(singly linked list) STL 시퀀스 컨테이너 (sequence container): 노드(Node)기반 연결형 선형 자료구조 탐...