1. 정의와 성질 연결 리스트 - 원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조 연결 리스트의 성질 1. k번째 원소를 찾기 위해 O(k)의 시간이 필요 2. 임의의 위치에 원소 추가/제거 O(1) 3. 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움 연결 리스트의 종류 1. 단일 연결 리스트(Singly Linked List) 2. 이중 연결 리스트(Doubly Linked List) 3. 원형 연결 리스트(Circular Linked List) 배열 vs 연결 리스트 배열 연결 리스트 k번째 원소의 접근 O(1) O(k) 임의 위치에 원소 추가/제거 O(N) O(1) 메모리 상의 배치 연속 불연속 추가적으로 필요한 공간..

1. 정의와 성질 배열 - 메모리 상에 원소를 연속하게 배치한 자료구조 배열의 성질 1. O(1)에 k번째 원소를 확인/변경 가능 2. 추가적으로 소모되는 메모리의 양(=overhead)가 거의 없음 3. Cache hit rate가 높음 4. 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림 2. 기능과 구현 기능 1. 임의의 위치에 있는 원소를 확인/변경 = O(1) 2. 원소를 끝에 추가 = O(1) 3. 마지막 원소를 제거 = O(1) 4. 임의의 위치에 원소 추가/제거 = O(N) 구현 - insert, erase 함수 수정 전 코드 #include using namespace std; void insert(int idx, int num, int arr[], int &len) { len..

1. STL과 함수 인자 함수 인자 위의 세 코드는 원본의 값을 바꾸는지 복사본의 값을 바꾸는지에 대해 묻는 것으로 출력 결과는 다음과 같다. 1. 0 함수 인자로 그냥 int 만 전달하게 되면 함수에서 아무리 값을 바꿔도 원본에 영향을 주지 않는다. 2. 10 함수 인자로 배열을 넘겨주게 되면 인자로 배열의 주소가 전달되기 때문에 함수에서 바꾼 것에 따라 원본 값에도 영향이 있다. 3. 0 구조체도 함수 인자로 전달하게 될 때, int 와 같이 값만 복사되는 것이기 때문에 원본에 영향을 주지 않는다. void swap1(int a, int b) { int tmp = a; a = b; b = tmp; } 위 코드는 원본에 영향을 주지 않아 원하는대로 동작하지 않는 swap 코드이다. void swap2(..

1. 시간, 공간복잡도 시간복잡도 - 입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계를 의미한다. 빅오표기법 - 주어진 식을 값이 가장 큰 대표항만 남겨서 나타내는 방법을 의미한다. ex) O(N) : 5N + 3 int func1(int N) { int sum = 0; for (int i = 2; i O(N^2) for문 2번을 돌아 O(N^2) int func3(int N) { for (int i = 1; i < N / 2; i++) { // i * i O(N) 의 시간복잡도를 가지지만 i * i