토랑님의 블로그

개념분할 정복(Divide and Conquer)은 문제를 더 작은 부분 문제로 분할한 뒤, 각 부분 문제를 재귀적으로 해결하고, 그 결과를 결합하여 원래 문제의 해답을 얻는 알고리즘 설계 기법주요 단계Divide (분할)문제를 동일하거나 유사한 더 작은 부분 문제로 나눔Conquer (정복)나눠진 부분 문제를 재귀적으로 해결부분 문제가 충분히 작아질 경우 직접 해결Combine (결합)부분 문제의 해답을 결합하여 원래 문제의 해답을 얻음특징재귀적 접근분할 정복 알고리즘은 재귀적으로 문제를 해결부분 문제의 독립성나누어진 부분 문제는 서로 독립적으로 해결할 수 있음효율성문제를 분할해 해결하므로 효율적인 시간 복잡도를 가질 가능성이 높음장점과 단점장점효율적문제의 크기를 줄여 효율적인 시간 복잡도를 가질 수 ..

백트래킹이란?백트래킹은 가능한 모든 경우의 수를 체계적으로 탐색하여 정답을 찾는 기법주로 재귀(Recursion)를 이용하며, 유망하지 않은 경우(해가 될 가능성이 없는 경우)를 빠르게 포기(Prune)하여 효율성을 높임주요 특징완전탐색 기반: 가능한 모든 해를 고려가지치기(Pruning): 유망하지 않은 경로를 조기에 제거재귀적 접근: 작은 문제를 해결하면서 전체 문제를 해결백트래킹은 "상태 공간 트리(State Space Tree)"를 탐색하는 알고리즘으로 생각할 수 있습니다. 각 노드는 현재까지의 선택을 나타내며, 가지(branch)는 가능한 다음 선택을 나타냅니다.더보기상태 공간 트리(State Space Tree)란?상태 공간 트리(State Space Tree)는 탐색 문제를 해결하기 위해 모..

특징현재 시점에서 가장 최적인 선택을 반복하여 최종 해답에 도달하는 알고리즘각 단계의 선택이 문제 전체에 대해 최적임을 보장할 수 있는 문제에서 사용일반적으로 최적해를 보장하기 위해 그리디 선택 속성과 최적 부분 구조 조건을 만족해야 함최적 부분 구조문제를 작은 하위 문제로 나누고, 각 하위 문제의 최적해를 조합해 전체 문제의 최적해를 얻을 수 있는 경우 그리디 선택 속성 각 단계에서 최적의 선택을 해도, 결과적으로 전체 문제에 대해 최적해가 되는 경우적용 여부 판단 질문문제를 하위 문제로 나누고, 하위 문제의 최적해를 조합해 전체 문제의 최적해를 얻을 수 있는가?각 단계에서 지역적으로 최적 선택을 하면, 전체적으로도 최적해를 보장할 수 있는가?그리디 선택을 할 때, 이후 선택들에 영향을 미치지 않는가?..

동적 프로그래밍 (Dynamic Programming)개념 설명복잡한 문제를 작은 하위 문제들로 나누고, 결과를 저장하여 동일한 하위 문제를 반복 계산하지 않도록 하는 방법론특징최적 부분 구조 (Optimal Substructure) : 문제를 작은 문제로 나누고 이를 결합하여 전체 문제를 해결할 수 있음중복되는 하위 문제 (Overlapping Subproblems) : 동일한 하위 문제가 여러 번 반복적으로 계산됨메모리 사용 : 하위 문제 결과를 저장하기 위한 메모리 사용 (메모이제이션 또는 테뷸레이션)상향식(Bottom-Up) 또는 하향식(Top-Down) 접근 방식 사용장단점장점중복 계산을 방지해 시간 복잡도를 줄일 수 있음탐욕 알고리즘이나 분할 정복으로 해결할 수 없는 문제를 해결 가능단점메모리..

선형 탐색 (Linear Search)특징배열이나 리스트의 첫 번째 요소부터 마지막 요소까지 순차적으로 탐색데이터가 정렬되지 않은 경우에도 사용 가능장점구현이 매우 간단하고 직관적임정렬 여부와 상관없이 사용할 수 있음단점탐색 시간이 오래 걸림(특히 데이터가 많을수록 비효율적)최악의 경우, 모든 요소를 탐색해야 함시간 복잡도BestO(1) (찾는 값이 첫 번째에 있는 경우)Average/WorstO(n)Java 코드 예시더보기public class LinearSearch { public static int linearSearch(int[] arr, int target) { for (int i = 0; i  이진 탐색 (Binary Search)특징정렬된 배열에서 중간값을 기준으로 탐색 범..

기본 정렬 알고리즘1. Bubble Sort특징인접한 두 요소를 비교하며 크기에 따라 교환모든 요소를 여러 번 반복적으로 정렬하기 때문에 단순하지만 비효율적임장점구현이 간단이미 정렬된 데이터에서는 효율적단점대규모 데이터에서는 매우 비효율적데이터가 많을수록 처리 시간이 급격히 증가합시간 복잡도BestO(n) (이미 정렬된 경우)Average/WorstO(n^2)코드 예시SudoCode더보기BubbleSort(array): for i from 0 to length(array) - 1: for j from 0 to length(array) - i - 1: if array[j] > array[j+1]: swap(array[j], array[j+1]..

트라이(Trie)란?문자열을 문자 단위로 트리에 저장하는 자료구조각 노드는 문자열의 한 문자를 저장루트 노드는 비어 있으며, 문자열의 공통 접두사는 동일한 경로를 공유트라이는 접두사 기반 검색, 자동완성, 문자열 사전 구현 등에 널리 사용트라이의 주요 특징빠른 문자열 검색검색 복잡도: O(L) (L은 문자열의 길이)공통 접두사 공유동일 접두사를 가지는 문자열은 트리의 동일 경로를 공유공간 효율성중복된 문자열 저장을 줄여 공간 절약 가능(특히 공통 접두사가 많은 경우)주요 연산(1) 삽입 (Insert)문자열의 각 문자를 따라가며 노드를 생성하고, 문자열의 끝을 표시(2) 검색 (Search)루트에서 시작하여 문자열의 각 문자를 따라가며 탐색합니다. 문자열 끝에 도달하면 해당 문자열이 존재함을 확인할 수 ..

우선순위 큐(Priority Queue)란?각 요소가 우선순위를 가지며, 높은 우선순위를 가진 요소가 먼저 처리되는 자료구조큐(Queue)가 선입선출(FIFO) 원칙을 따르는 반면, 우선순위 큐는 우선순위에 따라 요소의 처리 순서가 결정특징우선순위가 높은 요소가 먼저 처리됨동일한 우선순위를 가진 요소는 일반적으로 선입선출사용 사례작업 스케줄링다익스트라 알고리즘허프만 코딩예시 코드기본 우선순위 큐 구현import java.util.PriorityQueue;public class Main { public static void main(String[] args) { PriorityQueue pq = new PriorityQueue(); // 요소 추가 pq.offer..

DFS (Depth-First Search)정의DFS는 깊이 우선 탐색(Depth-First Search)으로, 그래프나 트리에서 출발 노드에서 시작해 한 방향으로 끝까지 탐색한 후 다시 돌아와 다른 경로를 탐색하는 방식스택(Stack) 자료구조를 기반으로 작동하며, 재귀적으로 구현하는 경우도 많음특징탐색 방식특정 경로로 갈 수 있을 때까지 계속 탐색자료구조스택(재귀 호출 포함)활용 예시경로 탐색, 조합 생성, 순열 생성장점경로 탐색 및 백트래킹 문제에 적합메모리 사용량이 적은 경우도 있음(특히 그래프가 얕은 경우)단점경로가 매우 길거나 무한 루프의 가능성이 있는 경우, 스택 오버플로우 발생 가능최단 경로를 보장하지 않음시간 복잡도O(V + E)V는 노드(정점)의 개수, E는 간선의 개수.모든 노드와 간..

그래프(Graph)란그래프는 정점(Vertex, 노드)들의 집합과, 이들을 연결하는 간선(Edge)들의 집합으로 이루어진 자료구조특징정점과 간선이라는 2개의 요소로 이루어짐간선은 방향이 있을 수도(방향 그래프) 있고 없을 수도(무방향 그래프) 있음사이클(순환 구조)이 존재할 수 있음import java.util.ArrayList;import java.util.LinkedList;import java.util.List;class Graph { private int vertices; // 정점의 개수 private LinkedList[] adjList; // 인접 리스트 public Graph(int vertices) { this.vertices = vertices; ..