😎 공부하는 징징알파카는 처음이지?

⭐ 오토마타 : 계산 능력이 있는 추상 기계와 그 기계를 이용해서 풀 수 있는 문제들을 연구하는 컴퓨터 과학의 분야 : 추상 기계를 오토마타(automata, 복수형) 또는 오토마톤(automaton, 단수형), 즉 자동 기계 : 오토마타는 적어도 유한한 상태를 갖고, 입력을 받아 입력에 따라 일정하게 상태를 전이하며, 출력을 내놓는다 : 알고리즘이 요구하는 것, 즉 계산 문제를 해결할 능력과 같다

🌝 힙(heap) 자료구조 : 최대값 및 최소값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리 (complete binary tree) 를 기본으로 한 자료구조 : A가 B의 부모 노드이면, A의 키 값과 B의 키 값 사이에는 대소 관계가 성립된다 : 완전 이진 트리 : 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 작아야 하는 자료구조 최대 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙 가짐 left : i * 2 + 1 right : i * 2 + 2 parent : (i - 1) / 2 최소 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙 가짐 🌝 힙(heap) 주요 메서드 peek() : 최대/최소값 리턴 size() : 힙 사이즈 리턴 ..

🫧 이진탐색트리 : “모든 왼쪽 자식들 ≤ n < 모든 오른쪽 자식들” 속성은 모든 노드 n에 대해서 반드시 참이어야 함 : 모든 노드에 대해서 왼쪽 자식들의 값이 현재 노드 값보다 작거나 같도록 하고, 오른쪽 자식들 값은 현재 노드의 값보다 반드시 커야함 🫧 균형 vs 비균형 균형 레드 블랙 트리 AVL 트리 🫧 완전이진트리 : 트리의 모든 높이에서 노드가 꽉 차 있는 이진 트리 : 마지막 단계는 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 함 🫧 전이진트리 : 모든 노드의 자식이 없거나 정확히 두 개 있는 경우 : 자식이 하나만 있는 노드가 존재해서는 안됨 🫧 포화이진트리 : 전 이진 트리이면서 완전 이진 트리인 경우 : 모든 말단 노드는 같은 높이에 있어야 하며, 마지막 단계에서 ..

🫧 트리 : 하나의 루트 코드를 가진다 : 루트 노드는 0개 이상의 자식 노드를 갖고 있다 : 트리에는 사이클 존재할 수 없다 : 노드들은 특정 순서로 나열될 수도 있고 그럴 수 없을 수도 있다 : 각 노드는 어떤 자료형으로도 표현이 가능하다 노드(node) 트리의 구성요소에 해당하는 A, B, C, D, E, F와 같은 요소 간선(edge) 노드와 노드를 연결하는 연결선 루트 노드(root node) 트리 구조에서 최상위에 존재하는 A와 같은 노드 단말 노드(terminal node, leaf node) 아래로 또 다른 노드가 연결되어 있지 않은 E, F, C, D와 같은 노드 내부 노드(internal node),비 단말 노드(non-terminal node) 단말 노드를 제외한 모든 노드로 A, B..

🫧 비트 조작 : 0s 는 모든 비트가 0 인 값 : 1s 는 모든 비트가 1 인 값 : 연산들이 비트 단위로 이루어 진다! : 한 비트에서 일어나는 일이 다른 비트에 어떤 영향도 미치지 않는다 🫧 2의 보수와 음수 : 컴퓨터는 일반적으로 정수를 저장할 때 2의 보수 형태로 저장 : 양수를 표현할 땐 문제 없음 : 음수를 표현할 땐 그 수의 절댓값에 부호비트를 1로 세팅한 뒤 2의 보수를 취한 형태로 표현함 : N비트 숫자에 대한 2의 보수는 2^N 에 대한 보수값과 같음 (N은 부호비트를 뺀 나머지 값을 표현할 때 사용되는 비트의 개수) : 2의 보수를 표현하는 다른 방법은 양수로 표현된 2진수를 뒤집은 뒤 1을 더해 주는 것 🫧 산술 우측 시프트 VS 논리 우측 시프트 산술 우측 시프트 기본적으로 2..

🫧 트리 : 하나의 루트 코드를 가진다 : 루트 노드는 0개 이상의 자식 노드를 갖고 있다 : 트리에는 사이클 존재할 수 없다 : 노드들은 특정 순서로 나열될 수도 있고 그럴 수 없을 수도 있다 : 각 노드는 어떤 자료형으로도 표현이 가능하다 🫧 이진트리 : 각 노드가 최대 두 개의 자식을 갖는 트리 🫧 이진탐색트리 : “모든 왼쪽 자식들 ≤ n < 모든 오른쪽 자식들” 속성은 모든 노드 n에 대해서 반드시 참이어야 함 : 모든 노드에 대해서 왼쪽 자식들의 값이 현재 노드 값보다 작거나 같도록 하고, 오른쪽 자식들 값은 현재 노드의 값보다 반드시 커야함 🫧 균형 vs 비균형 균형 레드 블랙 트리 AVL 트리 🫧 완전이진트리 : 트리의 모든 높이에서 노드가 꽉 차 있는 이진 트리 : 마지막 단계는 꽉 차 ..

🫧 해시테이블 (hash table) : 효율적인 탐색을 위한 자료구조로서, key를 value 에 대응시킴 : 최악의 경우 O(n) // n은 키의 개수 : 최선의 경우 O(1) 🫧 연결리스트와 해시 코드 함수로 구현 1) 키의 해시 코드 계산 키의 자료형은 보통 int or long 키의 개수 무한 (int 는 유한) 2) hash(key) % array_length 방식으로 해시 코드 이용해 배열의 인덱스 구함 서로 다른 두 개의 해시 코드가 같은 인덱스 가리킬 수 있음 3) 배열의 각 인덱스에는 키와 값으로 이루어진 연결리스트 존재 키와 값을 해당 인덱스에 저장 (반드시 연결리스트 이용!) 💥 충돌 : 서로 다른 두 개의 키가 같은 코드를 가리키거나, 서로 다른 두 개의 해시 코드가 같은 인덱스를..

🫧 큐 : FIFO (First In First Out) 순서 : 큐에 저장되는 항목들은 큐에 추가되는 순서대로 제거된다 너비 우선 탐색 (bfs) 처리해야 할 노드의 리스트를 저장하는 용도로 큐 사용 노드를 하나 처리할 때마다 해당 노드와 인접한 노드들을 큐에 다시 저장 노드를 접근한 순서대로 처리 가능 캐시 구현 🫧 큐 구현하기 💖 tail 포인터가 있는 연결 리스트를 사용하여 구현하기 ➡️ enqueue(value) - tail이 가리키는 곳에 value를 추가한다 int main() { int keys[] = { 1, 2, 3, 4, 5 }; Queue q; // 위의 키 삽입 for (int key: keys) { q.enqueue(key); } return 0; } ➡️ dequeue() - ..