개발 공부 기록

☑️ 분할 정복이란? 분할 정복(Divide and Conquer)은 큰 문제를 작은 하위 문제로 분할하고, 각 하위 문제를 해결한 다음, 그 해답을 합쳐서 원래의 큰 문제를 해결하는 방법입니다. 즉, 분할 → 정복 → 결합의 단계로 이루어집니다. 대표적인 예로, 퀵 정렬(Quick Sort)이나 병합 정렬(Merge Sort)과 같은 정렬 알고리즘 문제와 이진 탐색 문제가 있습니다. ☑️ 재귀 함수를 통한 분할 정복의 구현 분할 정복 알고리즘은 주로 재귀 함수를 통해 구현됩니다. 재귀 함수는 자기 자신을 호출하는 함수로, 하위 문제를 해결하기 위해 반복적으로 자신을 호출합니다. 전체적인 과정은 아래와 같습니다. 1. 분할 : 큰 문제를 작은 하위 문제로 나누는 단계에서 재귀 함수를 호출하면서 하위 문제..

Dynamic programming이란 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘으로, 중복 계산을 피하기 위해 실행 중간중간의 결과를 저장하고 이를 재사용하는 방식입니다. 어떠한 큰 문제를 작은 하위 문제로 분할하여 큰 문제의 최적 해결 방법을 하위 문제의 최적 해결 방법을 조합하여 만들어냅니다. 피보나치 수열을 예로 들어보겠습니다. public static int fibo(int x) { if(x == 1 || x == 2) { return 1; } return fibo(x - 1) + fibo(x - 2); } fibo(6)을 생각해봅시다. fibo(6)은 fibo(5)와 fibo(4)를 호출하고 fibo(5)는 fibo(4)와 fibo(3)을, fibo(4)는 fibo(3)과 fib..

DFS와 BFS 모두 정점(node)와 간선(edge)으로 이루어진 그래프를 탐색하는 방법으로, 하나의 정점에서 시작하여 차례대로 다수의 정점들을 방문합니다. 🔉 DFS(Depth-First Search) - 깊이 우선 탐색 DFS는 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘입니다. 스택 또는 재귀함수로 구현하며, 일반적으로 모든 노드를 방문하고자 할 때 사용됩니다. 예를 들어, 미로의 어느 한 지점에서 한 방향의 길로 쭉 탐색하다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와 그곳에서부터 다시 다른 방향의 길로 탐색하는 방식입니다. 아래는 DFS가 활용되는 몇 가시 예시입니다. 1. 두 노드 간의 경로가 존재하는지 확인하거나 모든 가능한 경로를 찾을 경우 - DFS는 깊게 들어..

이분 탐색이란 정렬된 배열 혹은 리스트에서 데이터를 빠르게 탐색할 수 있는 방법으로, 배열 내부의 데이터가 정렬되어 있어야만 사용이 가능합니다. 배열의 중앙에 있는 값을 보고, 찾고자 하는 데이터가 왼쪽 혹은 오른쪽 부분에 있는지를 파악하여 탐색의 범위를 반으로(O(logN)) 줄여가는 방식을 반복적으로 사용하여 데이터를 탐색합니다. 이분 탐색은 주로 언제 사용하는가? 이는 데이터의 삽입 혹은 삭제가 빈번할 경우엔 적합하지 않으며, 주로 고정된 데이터에 대한 탐색에 적합합니다. 또한 다량의 데이터를 검색하거나 탐색 범위가 1,000만 단위 이상으로 넘어가면 이분 탐색과 같이 O(logN)의 속도를 내야 하는 알고리즘을 떠올려야 문제 해결에 도움이 될 것입니다. 이분 탐색은 아래와 같이 위치를 나타내는 변..