본문 바로가기

✨ Algorithm/🐕‍🦺 바킹독 개념10

[0x06] 큐 정의와 성질 정의 한쪽 끝에서 원소를 넣고 뺄 수 있는 자료구조 성질 원소의 추가와 제거 : O(1) 제일 앞/뒤의 원소 확인 : O(1) 제일 앞/뒤이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 기능과 구현 const int MAX = 1e7; int data[MAX]; int head = 0, tail = 0; void push(int x) data[tail++] = x; void pop() head++; int front() return data[head]; int back() return data[tail--]; STL queue #include 2023. 6. 20.

[0x05] 스택 정의와 성질 정의 한쪽 끝에서만 원소를 넣거나 뺼 수 있는 자료 구조 (restricted structure) 성질 원소의 추가와 제거 : O(1) 제일 상단의 원소 확인 : O(1) 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 기능과 구현 구현 const int MAX = 1000005; int data[MAX]; int pos = 0; // 다음에 원소가 추가될 때 삽입해야 하는 곳 (스택 내 원소의 수) void push(int x) data[pos++] = x; void pop() pos--; int top() return data[pos-1]; STL stack #include 2023. 6. 20.

[0x04] 연결리스트 정의와 성질 성질 임의의 위치에 있는 원소를 확인/변경 : O(N) (불연속이기 때문에 그 원소까지 찾아가야 함) 임의의 위치에 원소를 추가/제거 : O(1) 원소들이 메모리 상에 연결되어 있지 않아 cache hit rate가 낮지만 할당이 다소 쉬움 종류 단일 연결 리스트 single linked list 이중 연결 리스트 doubly linked list 원형 연결 리스트 circular linked list 배열 vs 연결 리스트 overhead : 앞, 뒤 원소의 주소값을 가지고 있어야 한다 (2^n byte이면 n만큼 추가로 필요) 구현 struct Node { struct Node *prev, *next; int data; } 야매 연결리스트 const int MAX = 1000005; in.. 2023. 6. 20.

[0x03] 배열 배열 정의 메모리 상에 원소를 연속하게 배치한 자료구조 성질 O(1)에 k번째 원소를 확인/변경 가능 추가적으로 소모되는 메모리의 양 overhead가 거의 없음 메모리가 붙어있으므로 cache hit rate가 높음 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림 연산 임의의 위치 원소 확인/변경 : O(1) 원소를 끝에 추가 / 마지막 원소 변경 : O(1) 임의의 위치에 원소 추가/제거 : O(N) → 뒤에 원소들 한 칸 뒤로 밀어야 함 초기화 전역변수로 선언할 경우 int는 0으로 초기화 지역변수는 쓰레기값 들어가기 때문에 { } 등으로 초기화해야 함 int a[21]; int b[21][21]; memset (비추천) memset(a, 0, sizeof a); memset(b, 0, .. 2023. 6. 20.

이전 1 2 3 다음

티스토리툴바