게으른개발너D

1. 루프 돌리기 1. 최대공약수 최대공약수는 두 수 A, B의 공통 약수들 중 가장 큰 정수이다. 가장 직관적인 방법은 min(A, B)부터 1까지 루프를 돌려 각 수를 나누어보는 방법이다. const getGCD = (a, b) => { const max = Math.min(a, b); let gcd = max; for(let i = max; i >= 1; i--){ if(a % i === 0 && b % i === 0){ gcd = i; break; } } return gcd; } 2. 최소공배수 최소공배수는 A, B의 공통인 배수들 중 가장 작은 정수이다. 가장 직관적인 방법은 max(A, B)부터 시작하는 루프를 돌려 각 수들로 나누어보는 방법이다. const getLCM = (a, b) =>{..

✨ 비트 연산자 (Bit Operator) 비트를 직접 조작하는 연산자 // 비트 연산자 const x = 10; // 1010 const y = 12; // 1100 x & y; // AND - 8 x | y; // OR - 14 x ^ y; // XOR - 6 // 000000000000000000000000000001010 // 111111111111111111111111111110101 // 2의 보수 ~x; // NOT - -11 x > 1; // Right Shift - 101 - 5 ✨ 비트 마스크 (BitMask) 이진법 성질을 이용하여 문제를 해결하는 방법 특정 알고리즘은 아니고 비트 연산을 이용한 일종의 코딩 기법 이진수가 자료 구조로 사용된다. ex) [true, true, false..

✨ 동적 계획법 해결한 작은 문제로 큰 문제를 해결하는 문제 풀이 방식 Greedy나 Back tracking처럼 특정 알고리즘이 아닌 문제 해결 방식을 의미한다. Dynamic Programming(DP)라고도 부른다. 동적 계획법이 어렵게 느껴지는 원인 중 하나 Dynamic하지 않고 Programming과도 관련이 없다. 메모리를 많이 사용하는 대신 빠른 성능을 자랑한다. 두 가지 방법론이 있다. 메모이제이션 (Memoization) 타뷸레이션 (Tabulation) ✨ 메모이제이션 (Menoization) 하향식 접근법 (작은 문제들의 결과를 저장해 뒀다가 필요할 때 꺼내 쓰는 방법) 동적 계획법에서 작은 문제들의 결과는 항상 같다. 따라서 이 결과들을 메모리에 저장해 필요할 때 꺼내 쓰는 것이 ..

✨ 백트래킹 모든 경우의 수를 탐색하는 알고리즘 DFS나 BFS를 이용할 수 있다. 효율을 위해 탐색하지 않아도 되는 곳을 미리 막는 것을 가지치기 (Pruning)이라고 한다. 자바스크립트는 재귀 효율이 나쁘기 때문에 DFS를 구현할 경우 스택을 이용하는 것이 좋다. 코딩 테스트에선 이를 고려하여 재귀로 작성해도 풀 수 있도록 문제를 제출하는 경우도 있다. 탐색해서 순환 (Cycle)이 발생할 수 있다면 BFS를 이용하는 것이 편하다. BFS, DFS 모든 경우의 수를 찾을 때도 사용한다. 백트래킹의 핵심은 가지치기! 가지치기를 얼마나 잘하느냐가 효율성을 결정한다. ✨ 백트래킹 로직 작성하는 방법 모든 경우의 수를 찾을 수 있도록 코딩 이후 문제에서 특정한 조건을 만족하는 것만 탐색하고 나머지는 탐색하..

✨ 투포인터 알고리즘 일차원 배열에 인덱스를 가리키는 두 개의 포인터(변수)를 두고 조작하는 알고리즘 (이 인덱스를 가리키는 변수를 포인터라고 부름) 보통 연속적인 구간에 대한 계산을 할 때 많이 사용한다. 예시) 다음 배열에서 합이 10인 수열의 수는? 처음에는 포인터 두개가 전부 첫 인덱스를 가리킨다. 이때는 아직 구간에 대한 합(partialSum)이 7이고 구간 합이 10인 경우는 하나도 찾지 못한 상태이다. count = 0 partialSum = 7 p1 = 0 p2 = 0 아직 구간 합이 10을 넘지 못했기 때문에 두번째 포인터를 증가시키고 해당 index에 대한 값을 구간 합 변수에 더해준다. 따라서 partialSum 변수는 8이 된다. count = 0 partialSum = 8 p1 ..

해당 그래프를 최소한의 비용으로 모든 정점을 연결하려면? 필요한 간선 외에는 모두 제거하면 된다. 이러한 알고리즘을 최소 신장 트리라고 한다. ✨ 최소 신장 트리 (Minimum Spanning Tree) 신장 트리 (Spanning tree)란 그래프 내에 모든 정점을 포함하는 최소 연결 부분 그래프이다. 여기서 최소 신장 트리 (MST)는 다음과 같은 조건을 만족한다. 최소한의 간선으로 모든 정점이 연결되어야 한다. 모든 신장 트리 중 가중치의 값이 최소여야 한다. Cycle이 발생해서는 안된다. 최소 신장 트리를 위한 알고리즘은 대표적으로 두 가지가 있다. 크루스칼 (Kruskal) 프림 (Prim) 미리 알아두면 좋은 크루스칼 알고리즘 그리디 개념을 이용하여 구현할 수 있다. 먼저 모든 그래프를 ..

✨ 최단 경로 알고리즘 그래프에서 특정 정점에서 목적지까지 최단 경로를 구하는 알고리즘 DFS, BFS도 최단 경로 알고리즘으로 사용할 수 있다. 대표적인 최단 경로 알고리즘 BFS 다익스트라 (Dijkstra) 벨만-포드 (Bellman-Ford's) 플로이드 와샬 (Floyd Warchall) 목적에 따라 알고리즘을 선택할 수 있다. BFS, DFS 그래프의 간선 가중치가 모두 같을 때 적합하다. 예를들어, 아래와 같이 2차원 배열(지도) 입력이 주어진 상태로 최단거리를 찾아야 한다면 BFS, DFS로 푸는 경우가 많다. 이 경우 배열의 한 칸이 정점이 된다. 그리고 위, 아래, 오른쪽, 왼쪽이 간선이 된다. 간선의 가중치는 공평하게 1이 된다. 만약 간선에 가중치가 있다면? Dijkstra 그래프의..

✨ 순열과 조합 순열과 조합은 코딩테스트에서 자주 나오지만 자바스크립트에서 제공해주는 built-in 함수가 없기때문에 직접 구현해야한다. 성능이나 콜 스택 위험으로 인해 스택으로 구현하는 것이 좋지만, 순열과 조합 자체가 시간복잡도가 굉장히 크기때문에 n이 크게 나오는 경우가 많지 않다. 따라서 재귀로 외우는 것이 직관적으로 편하다. 1. 순열 시간복잡도 O(n!) function permutations(arr, n) { // 1개만 뽑는다면 그대로 순열을 반환한다. 탈출 조건으로도 사용된다. if (n === 1) return arr.map((v) => [v]); let result = []; arr.forEach((fixed, idx, arr) => { // 현재 index를 제외한 요소를 추출한다..