알고리즘 썸네일형 리스트형 LCA(Lowest Common Ancestor) 주어진 두 노드의 가장 가까운 공통 조상을 찾는 알고리즘 핵심 요소 Depth 배열: 각 노드의 깊이(루트에서 해당 노드까지의 거리)를 저장 Parent 배열: 각 노드의 부모 노드 정보를 저장 프로세스 Depth 및 Parent 계산: 먼저 트리를 순회하면서 각 노드의 깊이와 부모 노드 정보를 저장(DFS나 BFS 이용) LCA 찾기: 두 노드의 깊이가 다를 경우, 깊이가 더 깊은 노드를 그의 부모 노드로 올려서 깊이를 일치시킴 두 노드의 깊이가 같아지면, 두 노드가 같아질 때까지 각 노드를 그 부모 노드로 이동 같아지는 순간의 노드가 LCA 예제 function findLCA(parent, depth, node1, node2) { // 먼저 두 노드의 깊이를 같게 맞춥니다. while (depth[n.. 더보기 다익스트라 알고리즘 그래프에서 한 노드에서 다른 노드까지의 최단 경로를 찾기 위한 알고리즘 가중치가 있는 그래프에서 사용되며, 가중치는 음수가 아니어야 함 다익스트라 알고리즘의 기본 원리 초기화: 시작 노드의 거리를 0으로 설정하고, 나머지 모든 노드의 거리를 무한대로 설정 방문 처리: 아직 방문하지 않은 노드 중에서 가장 거리가 짧은 노드를 선택 경로 갱신: 선택된 노드를 경유하여 인접한 노드까지의 거리를 계산하고, 기존에 저장된 거리보다 짧다면 업데이트 반복: 모든 노드가 방문될 때까지 2번과 3번을 반복 배열 예제 function dijkstra(graph, start) { const distances = Array(graph.length).fill(Infinity); // 모든 노드까지의 거리를 무한대로 초기화 co.. 더보기 비트마스크(BitMask) 비트 연산을 이용하여 문제를 효율적으로 해결하는 기법 비트 연산자 AND (&): 두 비트가 모두 1이면 1을 반환 OR (|): 두 비트 중 하나라도 1이면 1을 반환 XOR (^): 두 비트가 서로 다르면 1을 반환 NOT (~): 비트 반전 Left Shift (): 비트를 오른쪽으로 이동 활용 삽입 let flags = 0b0000; // 초기 상태: 0000 flags |= (1 더보기 DP(동적계획법) 복잡한 문제를 여러 개의 작은 부분 문제로 나누어 해결하고, 이러한 작은 문제의 해결 결과를 저장하여 재사용함으로써 전체 문제의 효율적인 해결을 가능하게 하는 알고리즘 DP 조건 최적 부분 구조(Optimal Substructure): 부분 문제에 대한 최적 해결 방법으로 큰 문제의 최적 해결 방법을 구함 중복되는 부분 문제(Overlapping Subproblems): 동일한 작은 문제를 저장, 재사용 DP의 구현 방법 메모이제이션(Memoization): 하향식(top-down) 접근 방법, 재귀, 큰 문제를 작은 부분 문제로 나누어 해결 타뷸레이션(Tabulation): 상향식(bottom-up) 접근 방법, 반복문, 작은 부분 문제부터 차례대로 해결하여 전체 문제를 해결 피보나치 수열 예시 메모이.. 더보기 LIS(최장 증가 수열) 주어진 수열에서 원소들의 값이 증가하는 순서를 유지하는 최장의 부분 수열을 찾는 알고리즘 1. DP 방식 알고리즘: dp 배열을 1로 초기화(최소값, 1개로 이루어진 수열) 현재 요소보다 작은 요소들 중에서 가장 긴 dp 값을 찾아 현재의 dp 값을 업데이트 시간 복잡도: O(n^2) function lis(arr) { const dp = Array(arr.length).fill(1); for (let i = 1; i arr[j]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } } return Math.max(...dp); } 2. Binary Search 방식 .. 더보기 DFS & BFS DFS (Depth-First Search, 깊이 우선 탐색) 특징 및 방법: 스택 또는 재귀 함수를 사용 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색 모든 노드를 방문, 경로의 특징을 저장 구현이 간단하나 BFS보다 느림 시간복잡도: O(V + E) (V는 노드 수, E는 간선 수) function dfs(graph, start) { const visited = new Set(); const stack = [start]; while (stack.length) { const node = stack.pop(); if (!visited.has(node)) { visited.add(node); console.log(node); graph[node].forEach(neighbor => { if (!vi.. 더보기 이분 탐색 (Binary Search) 정렬된 배열에서 특정 값의 위치를 찾는 알고리즘 프로세스 배열의 중간 값을 확인 중간 값이 찾는 값이면 위치를 반환 중간 값보다 찾는 값이 작으면 왼쪽 부분에서 탐색을 계속 중간 값보다 찾는 값이 크면 오른쪽 부분에서 탐색을 계속 시간복잡도: O(log n) function binarySearch(arr, target) { let left = 0; let right = arr.length - 1; while (left 더보기 정렬 알고리즘 1. 거품 정렬 (Bubble Sort) 설명: 인접한 두 원소를 비교하여 서로 교환하는 방식 프로세스: 리스트의 첫 번째 원소부터 인접한 원소를 비교하여 필요에 따라 교환 리스트 끝까지 이동한 후, 가장 큰 원소가 마지막에 위치 리스트의 길이만큼 반복 시간복잡도: 최선/평균/최악 O(n^2) 장단점: 장점: 구현이 간단, 제자리 정렬, 안정 정렬 단점: 비효율적 function bubbleSort(arr) { const len = arr.length; for (let i = 0; i arr[j + 1]) { [arr[j], arr[j + 1]] = [arr[j + 1], arr.. 더보기 이전 1 다음