본문 바로가기

전체 글

 (97)
🚀 그래프 탐색 알고리즘 - 너비 우선 탐색!? ❓그래프 탐색이란?저번에 깊이 우선 탐색을 공부하면서 까먹을까봐 한번 더 적어보자면!! 네트워크가 어떻게 퍼져나가는지, 지도가 어떻게 연결되어 있는지, 소셜 네트워크에서 누가 누구와 이어져 있는지 등복잡한 관계를 이해하고 문제를 해결하는 핵심 도구가 바로 그래프 탐색이다.그래프 탐색은 정점(Node) 과 간선(Edge) 으로 이루어진 그래프에서특정 시작점으로부터 다른 노드를 차례로 방문하는 과정을 말한다. 👉 목적: 원하는 노드나 경로를 찾거나, 연결 관계를 분석하기 위해👉 응용: 네트워크 감염 추적, 미로 길 찾기, 소셜 네트워크 관계 분석, 전력망 탐색, 지도 탐색 등 그래프 탐색에는 크게 두 가지 대표적인 방법이 있다.깊이 우선 탐색 (DFS, Depth First Search)너비 우선 탐색 ..
[BeakJoon] 유기농 배추(JavaScript) 📘 오늘의 코딩테스트 - 유기농 배추(JavaScript)🔢 문제 번호: 1012번🔗 문제 링크: 백준 - 유기농 배추 🧠 문제 요약배추밭에서 인전한(상하좌우) 배추들이 몇 개의 그룹으로 나뉘어져 있는지 찾는 문제각 그룹마다 배추흰지렁이 한 마리가 필요하므로, 총 몇 마리의 지렁이가 필요한지 구해야 함입력: 테스트 케이스 T, 각 케이스마다 M(가로), N(세로), K(배추 개수), 배추 위치들출력: 각 테스트 케이스마다 필요한 지렁이 마리 수 ✅ 실행 예시 및 결과입력:210 8 170 01 01 14 24 34 52 43 47 48 49 47 58 59 57 68 69 610 10 15 5출력:51 ✍️ 내 풀이테스트 케이스마다 NxM 크기의 2차원 배열(배추밭) 생성배추 위치들을..
🚀 그래프 탐색 알고리즘 - 깊이 우선 탐색!? ❓그래프 탐색이란?프로그래밍을 공부하다 보면 그래프 탐색이라는 개념이 자주 등장한다.네트워크가 어떻게 퍼져나가는지, 지도가 어떻게 연결되어 있는지, 소셜 네트워크에서 누가 누구와 이어져 있는지 등복잡한 관계를 이해하고 문제를 해결하는 핵심 도구가 바로 그래프 탐색이다.그래프 탐색은 정점(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..
[BaekJoon] 1로 만들기(JavaScript) 📘 오늘의 코딩테스트 - 1로 만들기(JavaScript)🔢 문제 번호: 1463번🔗 문제 링크: 백준 - 1로 만들기 🧠 문제 요약정수 N이 주어졌을 때, 다음과 같은 연산 세 개를 적절히 사용해 1을 만들려고 한다연산을 사용하는 횟수의 최솟값을 출력하시오 X가 3으로 나누어 떨어지면 3으로 나눈다X가 2로 나누어 떨어지면 2로 나눈다1을 뺀다입력: 1보다 크거나 같고, 10^6보다 작거나 같은 정수 N출력: 연산을 하는 횟수의 최솟값 ✅ 실행 예시 및 결과입력: 10출력: 3 ✍️ 내 풀이다이나믹 프로그래밍(DP: Dynamic Programming)을 사용!!dp 배열을 생성하여 for문으로 결과를 dp에 저장입력값을 dp 배열에서 찾아 출력!! 💻 내가 푼 코드const ..
🚀 다이나믹 프로그래밍!?!? 🔎 다이나믹 프로그래밍이란?다이나믹 프로그래밍(Dynamic Programming, DP)은👉 복잡한 문제를 작은 하위 문제들로 나누어 해결하는 알고리즘 기법이다 💡핵심은!! 한번 계산한 결과는 저장해두고 재사용하자는것!! ❓왜 중요할까??일반적인 재귀 알고리즘에서는 같은 계산을 반복적으로 수행하게 된다.DP는 이런 중복 계산을 없애 ⏱️ 시간 복잡도를 획기적으로 개선할 수 있다!! ✅ DP를 적용할 수 있는 조건최적 부분 구조(Optimal Substrcuture)큰 문제의 최적해가 작은 문제들의 최적해로 구성되어야 한다예: 서울 → 부산 최단경로(서울 → 대전 최단 경로) + (대전 → 부산 최단경로)중복되는 부분 문제(Overlapping Subproblems)같은 하위 문제가 여러 번 ..
🚀 그리디 알고리즘!?!? 📝 그리디 알고리즘이란?그리디 알고리즘(Greedy Algorithm)은 매 순간 지금 당장 가장 좋아 보이는 선택을 하는 알고리즘이다"탐욕적"이라는 이름답게, 미래를 고려하지 않고 현재 상황에서 최선의 선택만을 반복한다 🔑 핵심 특징1. 지역 최적해(Local Optimal)를 선택뜻: 문제를 풀 때 매 단계마다 "그 순간 가장 좋아 보이는 해답"을 선택한다는 것특징: 이미 한 선택은 절대 되돌리지 않는다👉 즉, "지금 당장 제일 좋아 보이는 카드"만 계속 고르는 것!! 2. 전역 최적해(Global Optimal)를 보장해야 함뜻: 그렇게 지역 최적해만 쌓아가도 "최종적으로 전체 문제의 최적해(최선의 답)"가 되어야 한다는 것중요한 점: 모든 문제가 이 조건을 만족하지 않는다!! 👉 그래서..
[BaekJoon] 듣보잡(JavaScript) 📘 오늘의 코딩테스트 - 듣보잡(JavaScript)🔢 문제 번호: 1764번🔗 문제 링크: 백준 - 듣보잡 🧠 문제 요약김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 문제두 명단에 모두 포함된 사람들을 찾아 사전순으로 정렬하여 출력해야 한다입력: N(듣도 못한 사람 수), M(보도 못한 사람 수), 각각의 이름들출력: 듣보잡의 수와 그 명단을 사전순으로 출력 ✅ 실행 예시 및 결과입력:3 4ohhenriecharliebaesangwookobamabaesangwookohhenrieclinton출력:2baesangwookohhenrie ✍️ 내 풀이Set을 활용하여 교집합을 구하는 방식으로 접근한 그룹을 Set으로 만들고 다..

티스토리툴바