got beer?

✅ 벨먼-포드 알고리즘 (Bellman-Ford Algorithm) ❕ 기본 개념 - 그래프의 최단 경로 문제를 해결하기 위한 알고리즘 - 최단 경로 문제에서는 간선에 가중치가 부여된 가중 그래프가 주어지며, 시작점부터 종점까지의 경로 중 간선의 가중치 최소합을 구하면 됨 - 가중치가 음수라도 제대로 동작함 - 방향성/비방향성 그래프 모두 적용 가능 - 정점 수를 n, 간선 수를 m이라고 할 때, 가중치 변경 작업을 n회 순회하고, 각 변경 작업에서 각 간선을 1회씩 조사하므로 전체 계산 시간은 O(nm) ❕ 작동 방식 ✔ 구현 방법 (JS) function BellmanFord(graph, V, E, src) { // Initialize distance of all vertices as infinite..

✅ 이진 탐색 (Binary Search) ❕ 기본 개념 - 배열에서 데이터를 탐색하는 알고리즘 - 선형 탐색과 달리, 데이터가 정렬된 경우에만 적용할 수 있음 - 배열의 가운데에 있는 데이터와 대상 데이터를 비교해서 대상 데이터가 정중앙보다 오른쪽에 있는지, 왼쪽에 있는지 확인 - 비교 작업을 대상 데이터를 찾거나 존재하지 않는다는 것을 확인할 때까지 반복 - 탐색 범위를 매번 반씩 줄여나갈 수 있는 탐색 알고리즘 - n개의 데이터를 반으로 나누는 작업을 log2n회 반복 = 계산 시간은 O(log n) ❕ 작동 방식 ✔ 구현 방법 (JS) function binarySearch(sortedArray, key) { let start = 0; let end = sortedArray.length - 1; ..

✅ 욕심쟁이 알고리즘 (Greedy Algorithm) ❕ 기본 개념 - 매 선택마다 현재 시점에서 최적의 답을 선택하여 적합한 결과를 도출하는 알고리즘 설계 기법 - 하지만 그 최적의 답이 최종적인 결과 도출에 대한 최적해를 보장해주지는 않음 - 동적 프로그래밍을 간단한 문제 해결에 사용하면 지나치게 많은 일을 한다는 점을 착안하여 고안됨 해당 알고리즘이 필요한 문제의 조건은 아래와 같다. 1. 최적 부분 구조 : 부분 문제들의 최적의 답을 이용해서 전체 문제의 최적해를 구할 수 있다. 2. 탐욕적 선택 속성 : 각 단계에서 탐욕스러운 선택을 하는게 전체 문제를 푸는 데 있어서 최선의 선택을 하는 것이라면, 그 문제는 탐욕적 선택 속성을 가지고 있는 것이다. ❕ 작동 방식 ✔ 활용 예시 - AI 결정 ..

✅ 동적계획법 (Dynamic Programming) ❕ 기본 개념 - 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 - 일반적인 재귀 방식과 매우 유사하지만, 작은 문제들이 여러번 반복되는 비효율적인 계산을 피할 수 있음 해당 알고리즘이 필요한 문제의 조건은 아래와 같다. 1. 겹치는 부분 문제 (Overlapping Subproblems) : DP는 문제를 작은 문제들로 나누고 그 결과값들을 재활용해서 전체 답을 구한다. 따라서 동일한 부분 문제들이 반복하여 나타나고, 부분 문제가 중복되는 경우에 사용 가능하다. 2. 최적 부분 구조 (Optimal Substructure) : 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적해를 낼 수 있는 경우를 의미한다. ❕ 작동 방식 DP를 통해..

✅ 계수 정렬 (Counting Sort) ❕ 기본 개념 - 말 그대로 각 요소의 갯수를 세어서 저장해두고, 그에 따라 적절한 위치에 정렬하는 알고리즘 - 값의 범위가 너무 크면 안 되고, 각 항목의 갯수를 기록하기 위해 정수로 인덱스 되는 카운트 리스트를 사용하기 때문에 정수나 정수로 표현할 수 있는 자료에만 적용할 수 있다는 한계가 존재함 - 비교 정렬 알고리즘의 최소 시간복잡도가 O(n logn)인데에 비해 계수 정렬은 평균 O(n)의 시간복잡도를 가짐 - 다만 공간복잡도가 O(size)이기 때문에 메모리 낭비가 심함 ❕ 작동 방식 ✔ 구현 방법 (JS) const arr = [4, 3, 1, 2, 3]; const findMaximum = (arr) => arr.reduce((acc, val) =..

✅ 퀵 정렬 (Quick Sort) ❕ 기본 개념 - 분할 정복(divide and conquer) 방법을 통해 정렬 - 수열 안에서 기준이 되는 수인 피봇(pivot)을 임의로 하나 선택한 후, 나머지 수를 '피봇보다 작은 수'와 '피봇보다 큰 수'의 두 그룹으로 나눈다. 피봇을 기준으로 왼쪽과 오른쪽의 리스트들을 각각 정렬하면 전체 정렬이 완료됨 - 분할된 두 개의 리스트에 대해 재귀적으로 앞의 과정을 반복한다. (재귀는 리스트의 크기가 0 또는 1이 될 때까지 반복) - n의 리스트를 정렬하는데 걸리는 시간을 T(n), c는 임의의 상수라 하고, 리스트가 피봇 기준으로 두개의 비슷한 크기의 부분집합으로 나뉜다는 가정 하에 얻는 평균 시간복잡도는 O(n logn)이다. - 반면, 운이 나빠 매번 최솟..

✅ 삽입 정렬 (Insertion Sort) ❕ 기본 개념 - 자료 배열의 모든 요소를 차례대로 정렬 완료된 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘 - 배열이 길어질수록 효율이 떨어지지만 구현이 간단함 - 숫자 비교 횟수는 최악의 경우에 1 + 2 + 3 + ... + (n - 1) ≈ n2 / 2 번 비교 - 따라서 시간복잡도는 O(n2), 공간복잡도는 O(1) ☜ 추가적인 메모리 필요 X ❕ 작동 방식 ✔ 구현 방법 (JS) function insertionSort(inputArr) { let n = inputArr.length; for (let i = 1; i < n; i++) { // Choosing the first element in our unsorted s..

✅ 선택 정렬 (Selection Sort) ❕ 기본 개념 - 수열 중에서 최솟값을 검색한 후 왼쪽 끝 숫자와 교체하는 작업을 반복하며 정렬 - 최솟값을 찾을 때는 선형 탐색을 사용 - 숫자 비교 횟수는 (n - 1) + (n - 2) + ... + 1 ≈ n2 / 2, 숫자 교체는 각 라운드 당 최대 1회 - 따라서 선택 정렬 시간 복잡도는 O(n2) ❕ 작동 방식 ✔ 구현 방법 (JS) function selectionSort(inputArr) { let n = inputArr.length; for (let i = 0; i < n; i++) { // Finding the smallest number in the subarray let min = i; for (let j = i + 1; j < n; j..

✅ 너비 우선 탐색 (BFS, Breadth-First Search) ❕ 기본 개념 - 그래프의 시작점에서 간선(edge)을 따라가며 정점(node)을 탐색하고 지정한 목표 정점에 도달하는 것 - BFS는 그래프의 시작점부터 가까운 순으로 너비를 넓혀 가며 탐색하는 알고리즘 - 따라서 목표가 시작점에 가까이 있으면 탐색이 빨리 종료됨 - 후보 노드를 선입선출(FIFO) 구조로 관리하므로 queue 데이터 구조를 사용 - 따라서 queue와 while loop을 이용하여 BFS를 구현함 ❕ 작동 방식 ✔ 활용 예시 queue의 특징이 필요한 부분이나 너비를 우선으로 탐색하는 것이 효율적인 곳에 사용됨 ex. 최단거리를 구하는 문제 ☞ BFS로 가까운 노드부터 탐색하기 때문에, 가장 먼저 찾아지는 해답이 곧..

✅ 완전탐색 알고리즘 (Brute Force Algorithm) ❕ 기본 개념 - 가능한 모든 경우를 모두 확인하여 정답을 찾아내는 방식 - 운이 좋다면 빠르게 답을 도출할 수 있지만, 운이 나쁘면 가장 마지막으로 확인하는 경우가 답이 될 수도 있음 - 따라서 효율적인 문제 해결에는 적합하지 않은 탐색 알고리즘임 ❕ 완전탐색 기법 Brute Force 기법 : 반복 / 조건문을 활용하여 모든 가능한 경우를 전부 다 확인 Permutation (순열) : 서로 다른 n개의 원소 중 r개를 선택하여 나열 (순서 상관 O, 중복 허용 X) Recursive (재귀 호출) Bitmasking (비트마스크) : 2진수 표현 기법 활용 BFS, DFS ❓ Brute Force 기법 - 반복 / 조건문을 통해 가능한..

✅ 힙 (Heap) ❕ 기본 개념 - 그래프의 이진 트리 구조 중 하나 - 힙을 표현하는 트리 구조의 각 정점을 노드(node)라고 부르며, 각 노드에는 데이터가 저장됨 - 중복된 값을 허용함 - 두 가지의 힙 타입이 존재: Max-Heap / Min-Heap Min-Heap의 경우... - 항상 최상위 노드에 최솟값이 존재하므로, 데이터 수와 상관없이 항상 O(1) 시간에 최솟값을 추출할 수 있음 - 최솟값 추출한 후에는 힙을 재구축하게 되는데, 이때 가장 후미에 있는 데이터를 가장 위로 끌어올린 후에 그 자식과 비교해가며 아래 방향으로 재구축을 진행함 - 데이터 수를 n이라 할 때, 트리의 높이는 log2n이 되고 재구축하는데 걸리는 시간은 O(log n)이 됨 - 데이터를 추가할 때는 가장 후미에 ..

✅ 해시 테이블 (Hash Table) ❕ 기본 개념 - 키(Key)와 값(Value) 한 쌍의 형태로 데이터를 저장하는 자료구조 - 해시함수를 사용하여 키를 해시값으로 매핑한 후, 이 해시값을 인덱스 혹은 주소로 삼아 데이터 값을 키와 함께 저장함 - 해시값이 충돌할 때는 연결리스트를 사용하여 유연하게 데이터를 저장할 수 있음 - 검색을 빠르게 할 수 있기에 배열 내의 특정 데이터에 빠르게 접근할 수 있음 - 데이터 검색 시 시간복잡도: 평균 O(1), 최악의 경우 O(n) - 해시 테이블에 사용하는 배열의 크기를 적절히 설정하는 것이 중요함 - 배열의 크기가 너무 작으면 충돌이 많아지고 선형 탐색의 빈도가 높아짐 - 반대로 배열의 크기가 너무 크면 데이터가 빈 곳이 많아져서 메모리를 낭비하게 됨 ❕ ..

✅ 큐 (Queue) ❕ 기본 개념 - 데이터를 1열로 나열하는 데이터 구조 - 스택과 비슷하지만, 큐는 데이터를 추가하는 쪽과 삭제하는 쪽이 서로 반대쪽에 위치함 - "대기 행렬"이라고 생각하면 됨. 데이터가 줄 서 있는 행렬 ☜ 게임할 때 "큐가 왜이리 안 잡혀"할 때 쓰는 그 큐 - 먼저 넣은 것을 먼저 꺼내는 First In First Out (FIFO) 구조 - 스택과 마찬가지로 데이터를 조작할 수 있는 위치가 정해져 있음 - 중간에 있는 데이터에 indexing으로 접근할 수 없으며, 필요한 데이터가 나올 때까지 dequeue를 해야함 ❕ 작동 방식 - 큐에 데이터를 추가하는 작업을 enqueue, 데이터를 꺼내는 작업은 dequeue라고 함 - 큐의 가장 앞에서부터 차례대로 데이터가 추가됨 ..

✅ 스택 (Stack) ❕ 기본 개념 - 데이터를 1열로 나열하는 데이터 구조 - 나중에 넣은 것을 먼저 꺼내는 Last In First Out (LIFO) 구조 - 즉, 새롭게 추가한 데이터에만 접근할 수 있음 ❓ 리스트나 배열도 마찬가지로 1열로 나열한 데이터 구조인데? - 리스트/배열과 다르게 스택은 데이터 추가나 삭제가 단방향으로만 가능함 - 데이터 접근도 스택의 가장 위에 있는 데이터만 가능함 (indexing 불가) - 그래서 중간에 있는 데이터가 필요하다면 해당 데이터가 제일 위로 올 때까지 데이터를 pop 해야함 ✔ 활용 예시 단방향 조작만 가능하기 때문에 불편하다고 생각할 수 있지만, 항상 최신 데이터만 접근해야 하는 상황에서는 편리하게 사용된다. - 웹 브라우저 뒤로가기, 문서 작업 C..