본문 바로가기

Study/Algorithm

 (4)
🚀 그래프 탐색 알고리즘 - 깊이 우선 탐색!? ❓그래프 탐색이란?프로그래밍을 공부하다 보면 그래프 탐색이라는 개념이 자주 등장한다.네트워크가 어떻게 퍼져나가는지, 지도가 어떻게 연결되어 있는지, 소셜 네트워크에서 누가 누구와 이어져 있는지 등복잡한 관계를 이해하고 문제를 해결하는 핵심 도구가 바로 그래프 탐색이다.그래프 탐색은 정점(Node) 과 간선(Edge) 으로 이루어진 그래프에서특정 시작점으로부터 다른 노드를 차례로 방문하는 과정을 말한다. 👉 목적: 원하는 노드나 경로를 찾거나, 연결 관계를 분석하기 위해👉 응용: 네트워크 감염 추적, 미로 길 찾기, 소셜 네트워크 관계 분석, 전력망 탐색, 지도 탐색 등 그래프 탐색에는 크게 두 가지 대표적인 방법이 있다.깊이 우선 탐색 (DFS, Depth First Search)너비 우선 탐색 (B..
🚀 누적합(Prefix Sum)!?!? 🤔 누적합이란?간단히 말하자면 👉 배열의 앞에서부터 지금까지의 합을 미리 다 계산해놓는 것!원본 배열: [1, 3, 5, 7, 9]누적합: [1, 4, 9, 16, 25] ↑ ↑ ↑ ↑ ↑ 1 1+3 1+3+5 ... 모든수의합 📝 기본 공식 (외워야 함!) 1단계: 누적합 배열 만들기const arr = [1, 3, 5, 7, 9];const n = arr.length;const prefix = new Array(n).fill(0);// 첫 번째 값은 그대로prefix[0] = arr[0];// 이전 누적합 + 현재값for (let i = 1; i 2단계: 구간합 구하기// [L, R] 구간 합 구하기 (0-indexed)function ran..
🚀 다이나믹 프로그래밍!?!? 🔎 다이나믹 프로그래밍이란?다이나믹 프로그래밍(Dynamic Programming, DP)은👉 복잡한 문제를 작은 하위 문제들로 나누어 해결하는 알고리즘 기법이다 💡핵심은!! 한번 계산한 결과는 저장해두고 재사용하자는것!! ❓왜 중요할까??일반적인 재귀 알고리즘에서는 같은 계산을 반복적으로 수행하게 된다.DP는 이런 중복 계산을 없애 ⏱️ 시간 복잡도를 획기적으로 개선할 수 있다!! ✅ DP를 적용할 수 있는 조건최적 부분 구조(Optimal Substrcuture)큰 문제의 최적해가 작은 문제들의 최적해로 구성되어야 한다예: 서울 → 부산 최단경로(서울 → 대전 최단 경로) + (대전 → 부산 최단경로)중복되는 부분 문제(Overlapping Subproblems)같은 하위 문제가 여러 번 ..
🚀 그리디 알고리즘!?!? 📝 그리디 알고리즘이란?그리디 알고리즘(Greedy Algorithm)은 매 순간 지금 당장 가장 좋아 보이는 선택을 하는 알고리즘이다"탐욕적"이라는 이름답게, 미래를 고려하지 않고 현재 상황에서 최선의 선택만을 반복한다 🔑 핵심 특징1. 지역 최적해(Local Optimal)를 선택뜻: 문제를 풀 때 매 단계마다 "그 순간 가장 좋아 보이는 해답"을 선택한다는 것특징: 이미 한 선택은 절대 되돌리지 않는다👉 즉, "지금 당장 제일 좋아 보이는 카드"만 계속 고르는 것!! 2. 전역 최적해(Global Optimal)를 보장해야 함뜻: 그렇게 지역 최적해만 쌓아가도 "최종적으로 전체 문제의 최적해(최선의 답)"가 되어야 한다는 것중요한 점: 모든 문제가 이 조건을 만족하지 않는다!! 👉 그래서..

티스토리툴바