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

🫧 스택 : 데이터를 쌓아 올린다 : LIFO (Last In First Out) 에 따라 자료를 배열한다 : 가장 최근에 스택에 추가한 항목이 가장 먼저 제거될 항목 : 배열과 달리 스택은 상수 시간에 i 번째 항목에 접근할 수 없음 : 스택에서 데이터를 추가하거나 삭제하는 연산은 상수 시간에 가능하다 🫧 스택이 유용할 경우 : 재귀 알고리즘을 사용할 때 유용함 : 재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어 주고, 재귀 함수를 빠져 나와 퇴각 검색(backtrack) 할 때는 스택에 넣어 주었던 임시 데이터를 빼 줘야 한다 : 일련의 행위를 직관적으로 가능하게 해 준다 : 재귀 알고리즘을 반복적 형태 (iterative) 를 통해서 구현할 수 있게 함 🫧 스택 구현하기 funct..

🫧 연결 리스트 : 차례로 연결된 노드를 표현해주는 자료구조 : 단) 배열과 달리 특정 인덱스를 상수 시간에 접근할 수 없다 (k번째 원소를 찾고싶다면 처음부터 k번 루프 돌아야함) : 장) 리스트의 시작 지점에서 아이템을 추가하거나 삭제 연산을 상수 시간에 할 수 있다 단방향 각 노드는 다음 노드 가리킴 양방향 각 노드는 다음 노드와 이전 노드를 함께 가리킴 💖 (단방향) 연결 리스트 만들기 class Node { Node next = null; int data; public Node(int d) { data = d; } void appendToTail(int d) { Node end = new Node(d); Node n = this; while (n.next != null) { n = n.next;..

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

🫧 비유하기 파일 크기가 작다면 ? 온라인으로 전송 파일 크기가 무지막하게 크다면 ? 운전 or 비행기🚀 🫧 시간 복잡도 점근적 실행 시간 (asymptotic runtime), big-O 시간 개념 온라인 전송 : O(s), s는 파일의 크기 파일의 크기가 증가함에 따라 전송 시간이 선형적으로 증가 비행기 전송 : 파일의 크기 상관없이 O(1) 상수시간만큼 소요 ❤️ big-O : 시간의 상한 : 배열의 모든 값을 출력하는 알고리즘 : O(n) 뿐만 아니라, O(n^3) 혹은 O(n) 보다 큰 어떤 수행 시간으로 가능 ❤️ big-Ω (omega) : 등가 or 하한 : Ω(n) 뿐만 아니라, Ω(log N) 혹은 Ω(1) 로 표현 가능 ❤️ big-θ (theta) : O와 Ω 둘 다 의미 (딱 맞는..

=> 힙(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 위치로 이동 (우측 숫자들 탐색에서 제외) ..