개요본 글에서는 그래프 탐색 알고리즘의 종류인 너비 우선 탐색:BFS(Breadth-First Search) 알고리즘에 대해서 정리해보고자 합니다. BFS의 대한 내용은 아래의 포스팅에서 확인 가능합니다. [Algorithm] 효율적인 그래프 탐색: 자바로 구현한 DFS 알아보기 (1/2)이번 포스팅에서는 Java 알고리즘에서 필수적이라고도 말할 수 있는 DFS와 BFS에 대해서 알아보겠습니다. 자바를 활용하다 보면 그래프나 트리 구조를 탐색해야 할 때가 있습니다. 예를 들어,pixx.tistory.com BFS (너비 우선 탐색) 이란❓BFS(Breadth-First Search)는 그래프 탐색 알고리즘의 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가장 가까운 노드를 먼저 방문하면서 탐색..
최장 공통 부분 수열(Longest Common Subsequence, LCS)란❓최장 공통 부분 수열(LCS)은 두 수열이 주어졌을 때, 두 수열 모두의 부분 수열이 되는 수열 중 가장 긴 것을 말합니다. 여기서 중요한 점은 순서는 반드시 유지되어야 하지만, '연속된' 부분이 아니어도 된다는 것입니다.부분 수열이란?부분 수열은 주어진 수열에서 일부 원소를 선택해 원래 순서를 유지하면서 만든 수열입니다. 예를 들어, "ABCDE"의 부분 수열은 다음과 같습니다."A" "ACE""ABD""ABCD" 등이 될 수 있습니다. 최장 공통 부분 수열 찾기공통 부분 수열을 찾을 때의 핵심 규칙은 다음과 같습니다.두 문자열에 모두 있는 문자여야 함선택한 문자들의 순서가 두 문자열에서의 순서와 일치해야 함문자열 1: ..
개요알고리즘 학습을 하다 보면 반드시 한 번쯤은 마주치게 되는 유명한 문제가 있습니다. 바로 '배낭 채우기 문제' (Knapsack Problem)입니다. 배낭 문제는 크게 두 가지로 나뉩니다. 물건을 부분적으로 쪼갤 수 있는 Fractional Knapsack 문제와, 물건을 온전히 하나만 선택하거나 선택하지 않아야 하는 0/1 Knapsack 문제가 있습니다. 실제 현실 세계에서는 물건을 마음대로 쪼개서 담을 수 없는 경우가 대부분이기 때문에, 0/1 배낭 문제가 주로 사용되고는 합니다. 본 글에서는 두 가지 문제 중 0/1 Knapsack 문제에 대해서 정리하고자 합니다. 배낭 문제 해결을 위한 초기 접근 방법들도둑이 보석 가게에 침입했다.배낭의 최대 용량을 초과하면 찢어지기 때문에, 무게 제한 ..
LIS이란 ❓LIS(Longest Increasing Subsequence, 가장 긴 증가하는 부분 수열)는 주어진 수열에서 가장 긴 증가하는 부분 수열을 찾는 문제입니다. 여기서 부분 수열이란, 원래의 수열에서 원소들의 순서를 유지하면서 일부 원소들을 선택한 새로운 수열을 말합니다. 증가하는 수열이란, 선택된 원소들이 항상 오름차순으로 배치되는 수열을 의미합니다.LIS 예시주어진 수열이 [10, 20, 10, 30, 20, 50]일 때, LIS는 [10, 20, 30, 50]입니다. 이 부분 수열은 주어진 수열의 원소들 중에서 가장 긴 증가하는 부분 수열로, 원래 수열의 순서를 유지하면서 오름차순으로 나열된 부분 수열입니다. LIS의 특징1. 부분 수열원래 수열에서 일부 원소들을 선택하여 만든 새로운 ..
