Stack의 활용
Stack의 활용 수식의 괄호 쌍 FIFO 여는 괄호가 나오면 스택에 추가 닫는 괄호가 나왔을 경우 스택이 비어있으면 올바르지 않은 괄호 쌍 스택의 top이 짝이 맞지 않는 괄호일 경우 올바르지 않은 괄호 쌍 스택의 top이 짝...
최근 포스트
Stack
Stack 정의와 성질 FILO(Fisrt In Last Out) 자료구조 원소의 추가: O(1) 원소의 제거: O(1) 제일 상단의 원소 확인: O(1) 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 구현 배열 혹은 연결리스트...
Queue
Queue 정의와 성질 FIFO(First In First Out) 원소 추가: O(1) 원소 제거: O(1); 제일 앞/뒤의 원소 확인: O(1) 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 추가되는 곳을 rear, 제거되는 곳을 fr...
Deque
Deque 정의와 성질 양쪽 끝에서 삽입과 삭제가 가능 원소 추가: O(1) 원소 제거: O(1); 제일 앞/뒤의 원소 확인: O(1) 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 STL Deque에서는 인덱스로 원소 접근 가능 ...
Linked List
Linked List 정의와 성질 원소들을 저장할 때 그 다음 원소가 있는 위치를 포함 k번째 원소를 확인/변경하기 위해 O(k)가 필요함 임의의 위치에 원소를 추가/제거는 O(1) 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 쉬...
Array
Array 배열의 성질 O(1)에 k번째 원소를 확인/변경 가능 추가적으로 소모되는 메모리의 양이 거의 없음 cache hit rate가 높음(메모리상 데이터들이 붙어있음) 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림 임의의 위치에 원소를 추가: ...
C++ 주의해야할 점
C++ 주의해야할 점