Computer Algorithms14 [바킹독 실전 알고리즘 0x04] 연결 리스트 연결 리스트의 성질 k번째 원소를 확인/변경하기 위해 O(k)가 필요하다. 임의의 위치에 원소를 추가/제거는 O(1)의 시간복잡도를 가진다. 원소들이 메모리 상에 연속해있지 않아 cache hit rate가 낮지만 할당이 다소 쉽다.(코테에서는 몰라도 됨) 연결 리스트의 종류 단일 연결 리스트 이중 연결 리스트(이전+이후 원소의 주소 저장. 단일 연결 리스트보다 메모리를 많이 씀.) 원형 연결 리스트 배열과 연결 리스트는 둘 다 선형 구조라서 둘의 차이를 비교하는 문제가 면접 등에서 빈출된다. 배열 연결 리스트 k번째 원소의 접근 O(1) O(k) 임의 위치에 원소 추가/제거 O(N) O(1) 메모리 상의 배치 연속 불연속 추가적으로 필요한 공간(Overhead) - O(N) 연결리스트는 다음 원소 혹은.. 2023. 1. 31. [바킹독 실전 알고리즘 0x03] 배열 배열 정의: 메모리 상에 원소를 연속하게 배치한 자료구조. 성질: 1. O(1)의 시간복잡도만을 사용해 k번째 원소를 확인/변경이 가능하다. 메모리 상에 연속하게 배치되어있기 때문에 가능하다. 2. 추가적으로 소모되는 메모리의 양(=overhead)가 거의 없다. 3. cache hit rate가 높다. 4. 메모리 상에 연속한 구간을 잡아야해서 할당에 제약이 걸린다. 배열의 임의의 위치에 원소를 추가하는 데 걸리는 시간복잡도는 O(N)이다. 하나의 원소를 추가하기 위해 뒤에 남은 원소들을 모두 한 칸씩 밀어야하기 때문이다. 마찬가지로 임의의 원소를 제거하는 연산도 O(N)의 시간복잡도를 요구한다. 배열에 원소를 추가하거나 삭제하는 것은 다음과 같이 구현할 수 있다: //idx번째 위치에 num을 넣는 .. 2023. 1. 28. [C++] 백준 10871 #include int main(void) { std::ios::sync_with_stdio(0); std::cin.tie(0); int n, x, a[10000]; std::cin >> n >> x; for (int i=0;i > a[i]; for (int j = 0;j < n;j++) { if (a[j] < x) { std::cout 2023. 1. 28. [바킹독 실전 알고리즘 0x02] 기초 코드 작성 요령 II STL과 함수 인자 void func(int a){ a=5; } int main(void){ int t=0; func(t); cout 2023. 1. 28. [바킹독 실전 알고리즘 0x01] 기초 코드 작성 요령 I 시간, 공간복잡도를 고려하라 대략적인 N의 크기에 따른 허용 시간복잡도 N의 크기 허용 시간복잡도 N 2023. 1. 26. 이전 1 2 다음
