CS5 [DSA] Complexity 복잡도Time Complexity: This tells us how much time our code takes to run.Space Complexity: This tells us how much memory our code uses 시간 복잡도는 코드 실행시간을 알려주고, 공간 복잡도는 코드가 사용하는 메모리양을 알려준다. 자주 쓰이는 복잡도함수명칭예1상수형연결리스트 맨 앞 항목 추가하기logn로그형정렬된 배열에서 항목 찾기n선형정렬되지 않은 배열에서 항목 찾기nlogn선형로그형n개의 항목을 분할 정복 방식으로 병합 정렬하기n²2차형그래프에서 두 개의 정점 간의 최단 거리 구하기n³3차형행렬 계산하기2ⁿ지수형하노이 탑 문제 알고리즘 분석최악알고리즘이 오래 걸리는 경우알고리즘이 느리게 수행되는 것을 .. 2024. 11. 13. std::deque, std::stack, std::queue, std::priority_queue std::deque덱(deque)는 배열과 리스트 기반 컨테이너의 장점이 섞여 있는 형태이다.push_front(), pop_front(), push_back(), pop_back() 동작이 O(1) 시간 복잡도로 동작모든 원소에 대해 임의 접근 동작이 O(1) 시간 복잡도로 동작덱 중간에서 원소 삽입 또는 삭제는 O(n) 시간 복잡도로 동일, 최대 n/2 단계 (n은 deque의 크기)Deque의 사용 사례양방향 탐색이 필요한 경우: 덱을 활용한 너비 우선 탐색(BFS) 또는 양방향 BFS에서는 탐색의 방향을 유연하게 조절해야 할 때 덱을 활용하여 구현할 수 있습니다.슬라이딩 윈도우 문제: 주어진 배열에서 고정된 크기의 윈도우를 이동시키며 최댓값이나 최솟값을 찾는 문제에서 덱을 사용하면 각 윈도우에서 .. 2024. 10. 27. std:forward_list, std:list 배열 벡터 등 연속된 자료구조는 데이터 중간에 자료를 추가하거나 삭제하는 작업이 매우 비효율적이다.탭을 지원하는 브라우저에서 새로운 탭을 임의의 위치에 옮기는 경우음악 플레이어와 같이 재생목록 중간에 새로운 노래를 추가할 수 있는 프로그램의 경우연결 리스트 구현 개념1. 값+포인터2. new/delete를 활용한 메모리 할당 및 해제std:forward_list- 단방향 연결리스트- 메모리를 적게쓰고 빠른 성능을 유지하기 위해 사용- 리스트 끝에 원소 추가, 역방향 이동, 리스트 크기 반환 기능 Xstruct linked_list_node{ int data; doubly_linked_list_node* next;};std:forward_list에서 원소 삽입 삭제- forward_list는 마.. 2024. 10. 26. std::array, std::vector 기본 build & run 명령어g++ -o ex ex.cpp && ./exstd::array- std::array는 메모리를 자동으로 할당하고 해제한다.- C 스타일 배열과 같이 [ ] 연산자를 제공- at() : [ ] 연산자보다 느리지만 예외처리용으로 쓸 수 있다.#include #include using namespace std;std::array arr3 ={1, 2, 3, 4};int main(){ try{ cout 함수 인자 전달- 함수에 array 객체가 전달되면 새로운 배열에 모든 원소가 복사된다. (const를 사용하면 메모리와 시간이 절약)#include #include using namespace std;template void print(array arr){ for.. 2024. 10. 26. 선형 자료구조 - 연결 리스트 보호되어 있는 글 입니다. 2024. 8. 21. 이전 1 다음
