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

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

=> 힙(heap) 자료구조 개념 이해하기 | 개발자 코딩테스트 & 면접 지식 🫧 힙(heap) 자료구조 : 최대값 및 최소값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리 (complete binary tree) 를 기본으로 한 자료구조 : A가 B의 부모 노드이면, A의 키 값과 B의 키 값 사이에는 대소 관계가 성립된다 - 최대 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙 가짐 left : i * 2 + 1 right : i * 2 + 2 parent : (i - 1) / 2 - 최소 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙 가짐 🫧 힙(heap) 주요 메서드 peek() : 최대/최소값 리턴 size() : 힙 사이즈 리턴 isEmpty() ..

=> 코딩테스트 & 기술면접 을 위한 트리(tree) 자료구조 🫧 트리(tree) 자료구조 : 노드의 앞 뒤 관계가 1:N or N:M : 비선형 계층적 구조 : 하나의 tree 에는 하나의 root 가 있음 : 각 node 는 하나의 객체로 표현됨 : node 에 데이터와 자식 노드 저장 가짐 : size 는 root 포함 모든 node 의 수 : depth 는 node 에서 root 까지의 거리 : height는 노드 깊이의 최대값 🐾binary tree (이진 트리) : 각 노드가 최대 두개의 자식 노드를 가지고 있는 tree : 각 노드가 0에서 최대 2개의 child 노드 갖는다 🐾 binary search tree (이진탐색트리) : 왼쪽 자식 노드 값 < 부모 노드 값 : 부모 노드 값 < ..

=> 이 방법으로 풀어보세요 (슬라이딩 윈도우 알고리즘) 🫧 슬라이딩 윈도우 알고리즘 : 부분 배열의 원소들을 어떠한 조건 하에 계산할 때 사용 : 하나의 특정 범위를 정해 놓고, 그 윈도우를 이동시키면서 범위 내에 있는 원소들을 계산해줌 : 윈도우 범위 내의 모든 숫자들은 합산하고, 범위 밖으로 벗어난 숫자들은 빼준다 🐾 사이즈가 k인, 부분 배열(subarrary) 의 최대 합 구하기 function maxSumOfSubArrary(arr: number[], k:numnber) { let windowSum = 0; let maxSum = -Infinity; for (let i = 0; i = k - 1) { ma..

=> 개발자 필수 알고리즘 #3. 이진탐색 쉽고 간단하게 🫧 이진탐색 : 분할 정복 패턴을 지향하는 탐색 알고리즘 : 인풋 배열/데이터가 정렬되어 있는 조건하에 적용됨 🫧 이진탐색 vs 선형탐색 이진탐색 선형탐색 worst : O(log n) 매회 자료를 반으로 나눠가며 탐색 (선형보다 빠름) worst : O(n) 순차적인 탐색 패턴 인풋 데이터 정렬 분할 정복 유형 작거나 중간 사이즈의 데이터셋에 적절 🫧 이진탐색 원리 1) L, M, (중간 지점), R 포인트 준비 2) 배열의 M 수가 찾는 숫자와 같다면 M 리턴 추측 숫자가 찾는 숫자보다 작다면 L을 M + 1 위치로 이동 (좌측 숫자들 탐색에서 제외) 추측 숫자가 찾는 숫자보다 크다면 R을 M - 1 위치로 이동 (우측 숫자들 탐색에서 제외) ..

=> 개발자 필수 알고리즘 #2. 선형탐색 알고리즘이란? 🫧 선형탐색 : 배열/리스트에서 주어진 원소를 찾을 때 사용됨 : 일렬로 된 자료를 차례대로 탐색 : 찾고자하는 원소를 찾을 때 까지 or 모든 원소의 순회가 끝날 때 까지 진 1) 배열 전체 왼쪽에서 오른쪽으로 순차적 순회 2) 각 단계마다 찾는 원소가 있는지 확인, 만약 찾게 된다면 순회 멈추기 3) 못 찾을 경우, 다음 원소로 넘어가며 반복함 const nums = [10, 5, 2, 20, 7, 12, 33, 52] function linearSearch(arr: number[], val:number): boolean { for (let index = 0; index < arr.length; index ++) { const element =..

=> 개발자 필수 알고리즘 #1. 재귀 사용 방법 (Recursion) 🫧 재귀 사용 방법 (Recursion) : 자기 자신을 호출하는 함수 🐾 10에서 countDown 하기 : 순회 할 때마다 -1 하기 : 0보다 작으면 중지하기 function cntDown(n: number): void { // 1. Base case (stop contidtion) if (n = 1; i--) { n = n * i; } return n; } // 재귀함수 function factorial(n: number): number { // 1. Base case (stop contidtion) if (n === 0 || n ===1) { return 1; } // 2. Resursive case return n * fa..

=> 코딩테스트 필수 테크닉, 투 포인터 기법 🫧 투 포인터 테크닉 : 1차원 배열에서 각자 다른 원소를 가리키는 2개의 포인터를 사용하여 목표값 구한다 : 완전 탐색 O(n) 솔루션 -> O(n) 으로 성능 향상 가능 : 연속된 구간의 원소들을 처리하기 원하거나, 정렬된 배열에서 무언가를 구할 때 투포인터 사용 🐾 배열에서, 원소들의 합이 x인 연속 부분 배열의 개수를 구하라 arr = [1, 3, 6, 5, 2, 7, 9], x = 9 result : {3, 6}, {2, 7}, {9} // 완전 탐색 O(n^2) function cntSubArrSumOfX(arr, x) { let cnt = 0; for (let i = 0; i < arr.length; i ++) { let sum = 0; for ..