알고리즘 & 문제 해결 패턴/기본 알고리즘 & 자료구조 (6) 썸네일형 리스트형 [알고리즘] DFS vs BFS : 차이점 및 언제 사용해야 할까? [알고리즘] DFS vs BFS: 차이점 및 언제 사용해야 할까?1. DFS와 BFS란?DFS(Depth-First Search)와 BFS(Breadth-First Search)는그래프(또는 트리) 탐색 알고리즘입니다.이 두 알고리즘은 자료구조 문제에서경로 탐색,연결 요소 찾기,최단 거리 구하기 등 다양한 문제에 활용됩니다. 2. DFS (Depth-First Search, 깊이 우선 탐색)DFS는 한 방향으로 끝까지 탐색한 뒤,더 이상 갈 곳이 없을 때 이전으로 돌아가며 탐색을 이어갑니다.**스택(Stack)** 또는 **재귀(Recursion)** 를 활용합니다.✔ DFS 예제 (재귀 방식)public class DFSExample { static boolean[] visited = new bo.. [알고리즘 & 문제 해결 패턴] 해시 테이블(Hash Table) 개념과 활용 사례 [알고리즘] 해시 테이블(Hash Table) 개념과 활용 사례1. 해시 테이블(Hash Table)이란?해시 테이블(Hash Table)은 키(Key)와 값(Value)을 저장하는 자료구조입니다.키를 특정한 함수(해시 함수)를 사용하여 특정한 인덱스로 변환하고,이를 기반으로 값을 저장하거나 검색하는 방식입니다.2. 해시 테이블의 구조해시 테이블의 핵심 요소:✔ 해시 함수(Hash Function): 키를 해시값(인덱스)으로 변환하는 함수✔ 해시 충돌(Collision): 서로 다른 키가 동일한 해시값을 가질 때 발생✔ 충돌 해결 방법: 체이닝(Chaining), 개방 주소법(Open Addressing) 등---3. 해시 테이블 기본 구현 (Java 예제)🔹 **1. 기본적인 HashMap 사용**i.. [알고리즘 & 문제 해결 패턴] 탐욕 알고리즘(Greedy) 원리 및 활용 사례 [알고리즘] 탐욕 알고리즘(Greedy) 원리 및 활용 사례1. 탐욕 알고리즘(Greedy)이란?탐욕 알고리즘(Greedy Algorithm)은**각 단계에서 최적이라고 판단되는 선택을 반복하여 최종 해답을 찾는 방식**의 알고리즘입니다.일반적으로 전체 최적해를 구하는 것이 아닌,각 단계에서 가장 좋은 선택을 했을 때 최적해를 구할 수 있는 경우에 효과적입니다.2. 탐욕 알고리즘의 특징✔ **지역 최적해(Local Optimal Choice)를 선택하여 전체 최적해(Global Optimal Solution)를 찾음**✔ 항상 최적해를 보장하지는 않지만, **근사 최적해(Approximate Solution)**를 빠르게 구할 수 있음✔ DP(Dynamic Programming)와 다르게, **과거의 선.. [알고리즘 & 문제 해결 패턴] 다이나믹 프로그래밍(DP) 개념과 대표 문제 풀이 [알고리즘] 다이나믹 프로그래밍(DP) 개념과 대표 문제 풀이1. 다이나믹 프로그래밍(DP)이란?다이나믹 프로그래밍(Dynamic Programming, DP)은복잡한 문제를 작은 부분 문제로 나누어 해결하는 최적화 기법입니다.일반적인 분할 정복(Divide and Conquer)과 다르게, 동일한 부분 문제가 반복될 경우중복 계산을 줄이기 위해 결과를 저장(Memoization)하여 성능을 향상시킵니다.2. DP의 핵심 개념✔ **중복되는 부분 문제(Subproblem Overlapping)**큰 문제를 작은 문제로 나누어 해결예: 피보나치 수열✔ **최적 부분 구조(Optimal Substructure)**부분 문제의 최적 해가 전체 문제의 최적 해를 구성예: 최단 경로 문제✔ **메모이제이션(Mem.. [알고리즘] DFS(깊이 우선 탐색) 개념 및 구현 [알고리즘] DFS(깊이 우선 탐색) 개념 및 구현1. DFS(깊이 우선 탐색)란?DFS(Depth-First Search, 깊이 우선 탐색)는 그래프 탐색 알고리즘 중 하나로, 한 노드에서 출발해 **최대한 깊이 탐색한 후, 다시 돌아와서 다른 경로를 탐색하는 방식**입니다.일반적으로 **스택(Stack) 또는 재귀(Recursion)**을 이용하여 구현할 수 있습니다.✔️ DFS의 시간 복잡도: O(V + E) (V: 노드 수, E: 간선 수)2. DFS의 동작 원리 시작 노드를 방문하고, 방문한 노드를 **스택에 저장** 해당 노드에서 **방문하지 않은 인접 노드**를 찾고, 있다면 방문 더 이상 방문할 노드가 없으면 **스택에서 꺼내면서 뒤로 이동** 이 과정을 반복하여 모든 노드를 탐색.. [알고리즘] 이진 탐색(Binary Search) 개념 및 구현 [알고리즘] 이진 탐색(Binary Search) 개념 및 구현📌 이진 탐색(Binary Search)이란?이진 탐색은 정렬된 배열에서 **탐색 범위를 반씩 줄여가며 값을 찾는 알고리즘**입니다.탐색할 데이터가 많을 경우, **선형 탐색(순차 탐색)보다 훨씬 빠르게 원하는 값을 찾을 수 있습니다.**⏳ 시간 복잡도: O(log N) (탐색 범위를 절반씩 줄이므로)📌 이진 탐색 동작 원리 배열의 중간 값을 선택 찾고자 하는 값과 비교 중간 값이 찾는 값보다 크다면 **왼쪽 부분만 탐색** 중간 값이 찾는 값보다 작다면 **오른쪽 부분만 탐색** 중간 값이 찾는 값과 같다면 탐색 종료 위 과정을 반복하여 값을 찾을 때까지 탐색📌 이진 탐색 구현 방법1️.. 이전 1 다음
