목록CS/자료구조 & 알고리즘 (3)

귀염둥이의 메모

[알고리즘] 재귀(Recursion)와 수학적 귀납법(Mathematical Induction)

재귀(Recursion) void func1(int n) { if (n == 0) return; cout
CS/자료구조 & 알고리즘 2021. 2. 19. 00:25
[자료구조] 연결 리스트(Linked List)

연결 리스트(Linked List) 원소들을 저장할 때 그다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조이다. k번째 원소를 확인/변경하기 위해 O(k)가 필요하다. 임의의 위치에 원소를 추가, 제거는 O(1) 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉽다. 연결 리스트의 종류 단일 연결 리스트(Singly Linked List) : 각 원소가 자신의 다음 원소의 주소를 갖고 있다. 이중 연결 리스트(Doubly Linked List) : 각 원소가 자신의 이전 원소와 다음 원소의 주소 둘다를 갖고 있다. 원형 연결 리스트(Circular Linked List) : 끝이 처음과 연결되어있다. 배열 vs 연결 리스트 메모리 상의 배치는 배열은 연속..
CS/자료구조 & 알고리즘 2021. 2. 17. 00:59
[알고리즘] 슬라이딩 윈도우(Sliding Window) 알고리즘

슬라이딩 윈도우(Sliding Window) 알고리즘 일정한 범위(Window)를 가지면서 이동(Sliding)하는 알고리즘이다. 배열또는 리스트 요소의 일정 범위 값을 비교할 때 유용하다. ex) 양의 정수로 구성된 배열 [2, 4, 7, 10, 8, 4]에서 연속된 요소 3개의 합이 가장 큰 값은? 단순한 이중 for문을 사용한 방법은 아래와 같다. #include #define SIZE 6 using namespace std; int main(void) { int array[SIZE] = {2, 4, 7, 10, 8, 4}; const int windowSize = 3; int max_sum = 0; for (int i = 0; i < SIZE - windowSize + 1; i++) { int w..
CS/자료구조 & 알고리즘 2021. 2. 13. 01:43
Prev 1 Next