Algorithm

자바를 활용하다 보면 데이터 집합에서 특정 값을 빠르게 찾아야 할 때가 있습니다.  예를 들어, 정렬된 배열이나 리스트에서 원하는 값을 효율적으로 검색해야 하는 경우가 그렇습니다. 이러한 상황에서 사용하는 것이 바로 이진 탐색(Binary Search)입니다.  이진 탐색(Binary Search)란❓이진 탐색은 데이터가 정렬된 상태에서 중간 값을 기준으로 탐색 범위를 절반씩 좁혀가며 원하는 값을 찾는 효율적인 알고리즘입니다. 동작 방식이진 탐색은 다음과 같은 단계로 동작합니다초기 설정: 탐색 범위의 시작점(left)과 끝점(right)을 설정합니다. 처음에는 배열의 시작 인덱스와 끝 인덱스를 사용합니다.중간점 계산: 중간 인덱스(mid)를 계산합니다. mid = left + (right - left) ..

이번 포스팅에서는 Java 알고리즘에서 필수적이라고도 말할 수 있는 DFS와 BFS에 대해서 알아보겠습니다.  자바를 활용하다 보면 그래프나 트리 구조를 탐색해야 할 때가 있습니다.  예를 들어, 네트워크 경로 탐색, 웹 크롤링, 게임 AI 에서의 경로 탐색 등 다양한 분야에서 이러한 탐색 알고리즘이 사용됩니다.  이때 사용할 수 있는 것이 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)입니다. 이 두 알고리즘은 그래프나 트리 구조에서 특정 노드를 찾거나, 모든 노드를 방문하는 데 유용합니다.  DFS(Depth-First-Search)란❓Depth-First-Search를 번역해보면, 깊이 우선 탐색입니다. DFS(Depth-First Search)는 그래프 탐색 알고리즘 중 하나로, 이름에서 알 ..

그리디 알고리즘이란❓ 그리디 알고리즘이란 greedy라는 이름의 뜻에서 알 수 있듯이 탐욕스러운, 욕심스러운 알고리즘입니다. 탐욕이라는 뜻처럼 그리디 알고리즘(탐욕 알고리즘)은 각 단계에서 가장 최선의 선택을 하는 방법을 말합니다.  다음 그림을 보면 한눈에 알 수 있습니다. 위 그림을 보면 가장 큰 수를 탐색하는 과정을 greedy 알고리즘과 일반적으로 탐색하는 과정을 보여줍니다. 가장 큰 수를 찾기 위해 앞으로 간다면 제일 큰 수가 있는 "99"과 연결되어 있는 3 ➡️ 99 을 생각할 것입니다. 하지만 Greedy 알고리즘은 시작부터 3과 12 두 수중 가장 큰 수인 "12"을 탐색하고 그다음 큰 수인 "6"을 탐색합니다. 이 처럼 그리드는 최종결과에서의 최적의 해가 아닌 "현재상황에서 최적의 해"..

동적 계획법 DP란❓  동적 계획법은 프로그래밍 대회 문제에 가장 자주 출현하는 디자인 패러다임 중 하나로 1940년대 리처드 벨만이 사용하던 용어입니다.  주로 줄여서 DP라고 많이 말하며, 주어진 문제를 작은 하위 문제로 나누고, 그 결과를 저장하여 동일한 문제가 나왔을 시 저장해둔 결과를 재사용함으로써 전체 문제를 효율적으로 해결하는 기법입니다. 위 말을 기준으로 핵심을 뽑아보자면 다음과 같습니다.하나의 큰 문제를 여러 개의 작은 문제로 나누어 결과 저장동일 결과 재사용 DP 문제 성립 조건동적 계획법(DP)는 두 가지 주요 원리인 "최적 구분 구조"와 "중복되는 하위 문제"를 기반으로 합니다. 최적 부분 구조(Optimal Substructure)문제의 최적 해가 하위 문제의 최적 해로 구성되는 ..