프론트 개발자를 위한 여정

모든 영역을 안내하는 개발자

Algorithm 35

DFS & BFS 탐색 문제 개념 정리(개념, 코드, 시간/공간복잡도 비교)

🔎 1️⃣ DFS & BFS 문제에서 묻는 것그래프 탐색 문제에서 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)를 구현할 수 있는지를 확인합니다.✅ 주요 개념DFS(Depth-First Search, 깊이 우선 탐색)그래프에서 한 경로를 깊게 탐색하다가 막히면 다시 되돌아가며 탐색하는 방식재귀(Recursive) 또는 스택(Stack)으로 구현BFS(Breadth-First Search, 너비 우선 탐색)시작점에서 가까운 노드부터 탐색하는 방식큐(Queue)를 활용하여 구현✅ 이 문제에서 확인하려는 핵심 내용그래프 탐색 알고리즘을 이해하고 있는가?DFS와 BFS를 직접 구현할 수 있는가?스택(Stack), 큐(Queue) 자료구조를 활용할 수 있는가?시간복잡도와 공간복잡도를 고려하여 효율적으로 탐..

Algorithm 2025.03.16

[JS] 동적 계획법 (DP)문제 / 중복계산방지, O(n)

🚀 문제n개의 계단을 오를 때, 한 번에 1계단 또는 2계단을 오를 수 있다. 계단을 오르는 방법의 수를 반환하는 함수를 작성하시오.function climbStairs(n) { // 여기에 코드 작성}console.log(climbStairs(5)); // 8🔹 코드function climbStairs(n) { if(n  📌 동적 계획법 (DP)🔎 1️⃣ 문제가 묻는 것동적 계획법(DP)은 복잡한 문제를 여러 개의 작은 문제로 나누어 푸는 알고리즘 설계 기법입니다. 보통 최적화 문제나 계산을 효율적으로 해결해야 할 문제에서 유용하게 사용됩니다. 주로 두 가지 방식인 탑다운(Top-Down) 방식과 바텀업(Bottom-Up) 방식으로 구현할 수 있습니다.✅ 핵심 개념:문제 분할:문제를 더 ..

[JS] 탐색 알고리즘 (이진 탐색) / 반복문, 재귀함수 함수비교

🚀 문제정렬된 배열에서 특정 값을 찾는 이진 탐색 알고리즘을 구현하시오.function binarySearch(arr, target) { // 여기에 코드 작성}console.log(binarySearch([1, 3, 5, 7, 9, 11], 5)); // 2🔹 코드function binarySearch(arr, target) { let left = 0; let right = arr.length - 1; while (left 📌 이진 탐색 문제🔎 1️⃣ 문제가 묻는 것이진 탐색 문제에서 요구하는 것은 정렬된 배열에서 특정 값을 효율적으로 찾는 방법입니다. 이진 탐색은 배열을 반씩 나누어가며 탐색을 진행하므로 시간 복잡도를 O(log N)로 줄일 수 있습니다. 문제는 일반적으로 배..

메모이제이션과 동적 계획법(DP): Top-Down vs Bottom-Up 방식

💡 1. 동적 계획법(DP) 개요동적 계획법(DP)은 문제를 작은 하위 문제로 나누어 해결하는 알고리즘 기법입니다. 반복적인 계산을 피하고 중복 계산을 줄여 성능을 향상시키는 방식입니다.DP에서 중요한 개념은 중복 계산을 방지하는 것과 최적의 해법을 찾는 것입니다.💡 2. 메모이제이션과 DP: 무엇이 다를까?메모이제이션은 동적 계획법의 일종입니다. 구체적으로, 메모이제이션은 Top-Down 방식으로 문제를 해결하며, 계산한 결과를 저장하고 재사용하는 기법입니다. DP의 Bottom-Up 방식은 작은 문제부터 차례대로 해결하여 큰 문제를 풀어가는 방식입니다.  방법 방식 설명메모이제이션Top-Down 방식재귀를 이용하여 큰 문제를 먼저 해결하고, 작은 문제를 나누어 해결. 중복 계산을 줄이기 위해 결..

Algorithm 2025.03.16

[JS] 피보나치 수 반환 / 재귀함수, 반복문, 시간복잡도,공간복잡도 비교

🚀 문제재귀를 사용하여 n번째 피보나치 수를 반환하는 함수를 작성하시오.function fibonacci(n) { // 여기에 코드 작성}console.log(fibonacci(10)); // 55🔹 코드function fibonacci(n) { if (n === 0) return 0; if (n === 1) return 1; return fibonacci(n - 1) + fibonacci(n - 2);}console.log(fibonacci(10)); // 55📌 피보나치 수열 문제🔎 1️⃣ 문제가 묻는 것일반적으로 코딩 테스트에서 피보나치 수열을 반환하는 문제는 다음을 요구할 가능성이 큽니다:✅ 정의:fibonacci(n) 함수는 n번째 피보나치 수를 반환해야 한다.피보나치 ..

메모이제이션(Memoization) vs 반복문 비교

🔥 메모이제이션 vs 반복문, 무엇이 더 효율적일까?프로그래밍에서 성능 최적화는 매우 중요한 요소입니다. 특히 반복적으로 계산해야 하는 문제에서는 어떤 방법을 선택하느냐에 따라 속도와 메모리 사용량이 크게 달라질 수 있어요. 가장 많이 비교되는 기법이 바로 메모이제이션(재귀)과 반복문(반복 구조) 입니다. 그렇다면, 두 방식 중 어떤 것이 더 효율적일까요? 🤔💡 메모이제이션(Memoization)이란?메모이제이션은 이전에 계산한 값을 저장하여 동일한 연산을 반복하지 않도록 하는 기법이에요. 주로 재귀(탑다운 방식)와 함께 사용되며, 동적 계획법(DP)의 핵심 개념 중 하나로 활용됩니다.✔️ 장점: 중복 연산을 방지하여 속도를 향상시킬 수 있음 🚀✔️ 단점: 추가적인 메모리 공간이 필요할 수 있음 ..

Algorithm 2025.03.16

동적 계획법 (DP) 개념

🚀 동적 계획법(DP)이란?동적 계획법(Dynamic Programming, DP)은 반복 계산을 줄여 성능을 향상시키는 알고리즘 기법입니다.✔️ 작은 문제를 해결하고 결과를 저장해 불필요한 계산을 방지!✔️ 피보나치 수열, 배낭 문제, 최단 경로 문제 등에 활용 가능!✔️ 재귀(메모이제이션)와 반복문(타뷸레이션) 방식으로 구현할 수 있음!💡 DP의 핵심 개념🔥 왜 DP가 필요할까?프로그래밍을 하다 보면 같은 계산을 반복하는 비효율적인 코드로 인해 성능이 저하되는 경우가 많아요. 예를 들어, 피보나치 수열을 단순 재귀로 구현하면 중복 연산이 많아져 실행 속도가 느려질 수밖에 없죠. 😵이럴 때 필요한 게 바로 동적 계획법(DP)!DP를 사용하면 중복 계산을 최소화하고 실행 속도를 최적화할 수 있어요..

Algorithm 2025.03.16

[JS] 버블 정렬 (Bubble Sort) / 버블 정렬, 최적화 버블 정렬, 내장 sort()

🚀 문제주어진 배열을 버블 정렬 (Bubble Sort) 알고리즘을 이용하여 오름차순으로 정렬하시오.function bubbleSort(arr) { // 여기에 코드 작성}console.log(bubbleSort([5, 3, 8, 4, 2])); // [2, 3, 4, 5, 8]🔹 코드function bubbleSort(arr) { for (let i = 0; i arr[j + 1]) { const temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } console.log(arr); } } return ..

[JS] 문자열 내 각 문자 개수 세기 / Map 사용, Object 사용, reduce 활용 방법 비교

📌 문제주어진 문자열에서 각 문자의 등장 횟수를 계산하여 객체(Map)로 반환하는 함수를 구현하시오.function charCount(str) { // 여기에 코드 작성}console.log(charCount("hello world"));/*출력 예시:{ h: 1, e: 1, l: 3, o: 2, w: 1, r: 1, d: 1 }*/ 🔹 코드function charCount(str) { const map = new Map(); const word = str.split(''); for(let i = 0; i  🔎 풀이 과정1️⃣ 문제 접근 방식문자열을 순회하면서 각 문자의 등장 횟수를 세면 됨공백은 무시해야 하므로 if (word[i] === ' ') continue; 처리객체(Ma..

[JS] 배열에서 최솟값과 최댓값 찾기 / 정렬sort, Math.min()&max(), 반복문 방법 비교

📌 문제주어진 배열에서 최솟값과 최댓값을 찾아 배열로 반환하는 함수를 구현하시오.function findMinMax(arr) { // 여기에 코드 작성 }console.log(findMinMax([3, 1, 4, 1, 5, 9, 2, 6])); // [1, 9]  🔹 코드function findMinMax(arr) { arr.sort(); return [arr[0], arr[arr.length - 1]];}console.log(findMinMax([3, 1, 4, 1, 5, 9, 2, 6])); // [1, 9]🔎 풀이 과정1️⃣ 문제 접근 방식배열을 정렬한 후, 첫 번째 값과 마지막 값이 최솟값과 최댓값이므로 이를 반환함.정렬을 사용하는 방식은 직관적이지만, 비효율적인 방법일 수 있..