xxheexx

#include #define MAX 101 using namespace std; int cnt; vector graph[MAX]; void bfs(int v1, int v2){ queue q; vector visited(MAX); q.push(v1); visited[v1] = true; visited[v2] = true; while (!q.empty()) { int node = q.front(); q.pop(); for (int i=0; i

연결 리스트 원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조, 원소들은 이곳 저곳에 흩어져 있음 성질 k번째 원소를 확인/변경하기 위해 O(k) 필요 임의의 위치에 원소를 추가/제거는 O(1) 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당 다소 쉬움 연결 리스트의 종류 단일 - 각 원소가 자신의 다음 원소의 주소 이중 - 각 원소가 자신의 이전 원소와 다음 원소의 주소 list 원형 - 끝과 처음 연결 배열 vs 연결리스트 list #include using namespace std; int main(void) { list L = {1,2}; // 1 2 list::iterator t = L.begin(); // t는 1을 가리키는 중..

정의와 성질 배열 - 메모리 상에 원소를 연속하게 배치한 자료구조 성질 O(1)에 k번째 원소를 확인/변경 가능 추가적으로 소모되는 메모리의 양(=overhead)가 거의 없음 Cache hit rate가 높음 메모리 상에 연속한 구간을 잡아야해서 할당에 제약 임의의 위치에 원소 추가, 제거 - O(N) 사용팁 fill(arr, arr+arr.size(), 0); //0으로 채워줌 STL vector 배열과 거의 동일한 기능, 배열과 달리 크기를 자유자재로 늘이거나 줄일 수 있음 #include using namespace std; int main(void) { vector v1(3, 5); // {5,5,5}; cout