ehdbs0903 ehdbs0903

동적 계획법(Dynamic Programming) 알고리즘이란?복잡한 문제를 더 작고 관리 가능한 부분 문제로 나누어 해결하는 알고리즘 설계 기법이다.알고리즘의 기본 아이디어는 각 부분 문제의 해답을 저장하고, 이를 재사용함으로써 중복 계산을 피해 계산 효율을 극대화하는 것이다.  시간복잡도동적 계획법 알고리즘의 시간복잡도는 문제에 따라 다양하지만, 일반적으로 부분 문제의 수와 각 부분 문제를 해결하는 데 걸리는 시간의 곱으로 표현된다. 피보나치 수열 계산:각 수를 계산하기 위해 이전 두 수만 알면 되므로, 한 번 계산된 값은 다시 계산할 필요가 없다.시간복잡도는 O(n)이다.최장 공통 부분 수열(Longest Common Subsequence, LCS):시간복잡도는 O(m * n)이다.m, n은 두 시..

브루트포스(Bruteforce) 알고리즘이란?가장 단순하지만, 최적의 해를 보장하는 접근법이다.알고리즘의 기본 아이디어는 모든 가능한 경우의 수를 탐색하여 문제의 해를 찾는 것이다.  시간복잡도브루트포스 알고리즘의 시간복잡도는 문제의 크기와 경우의 수에 따라 달라진다.일반적으로 매우 높은 시간복잡도를 가지며, 이는 문제가 커질수록 기하급수적으로 증가한다. 순열 생성:n개의 원소에 대한 모든 순열을 생성하는 경우시간복잡도는 O(n!)이다.부분집합 생성:n개의 원소에 대한 모든 부분집합을 생성하는 경우시간복잡도는 O(2^n)이다. 문자열 패턴 매칭:텍스트 길이가 n이고, 패턴 길이가 m인 경우, 모든 위치에서 패턴을 비교하는 방식시간복잡도는 O(n * m)이다.  브루트포스의 기본 원리가능한 모든 경우 생성..

그리디(Greedy) 알고리즘이란?최적의 해를 구하는 데에 사용되는 근사적인 방법이다.알고리즘의 기본 아이디어는 문제를 해결하는 과정에서 각 단계에서 가장 최적이라고 생각되는 선택을 하는 것이다.  시간복잡도그리디 알고리즘의 시간복잡도는 문제의 특성과 구체적인 알고리즘 구현에 따라 다르다. 거스름돈 문제:동전 단위가 미리 정렬되어 있고, 각 동전을 한 번씩 선택시간복잡도는 O(n)이다.여기서 n은 동전의 종류 수활동 선택 문제:활동을 종료 시간 기준으로 정렬한 후, 한 번의 순회로 선택시간복잡도는 O(n log n) (정렬) + O(n) (활동 선택) = O(n log n)최소 신장 트리 문제 (Kruskal 알고리즘):간선을 가중치 기준으로 정렬한 후, Union-Find 자료구조를 사용하여 사이클을 ..

너비 우선 탐색 / BFS (Breadth-First Search) 알고리즘이란?그래프에서 모든 노드를 방문하는 알고리즘 중 하나이다.알고리즘의 기본 아이디어는 가까운 노드부터 먼 노드 순으로 그래프를 탐색하는 것이다.   시간복잡도BFS의 시간 복잡도는 그래프의 표현 방식에 따라 달라진다. 1. 인접 리스트 사용 시:각 노드에 대해 모든 인접한 노드를 방문해야 한다.각 노드는 한 번씩 방문하며, 각 노드의 모든 인접한 노드를 확인하는 데 걸리는 시간은 인접한 노드의 개수에 비례한다.따라서 시간 복잡도는 O(V + E) 이다.  (* V = 정점의 수, E = 간선의 수){ 'A': ['B', 'C', 'D'], 'B': ['A'], 'C': ['A', 'D'], 'D': ['A', 'C', 'E..

깊이 우선 탐색 / DFS (Depth-First Search) 알고리즘이란?그래프에서 모든 노드를 방문하는 알고리즘 중 하나이다.알고리즘의 기본 아이디어는 한 방향으로 갈 수 있는 한 최대한 깊게 그래프를 탐색하는 것이다.   시간복잡도DFS의 시간 복잡도는 그래프의 표현 방식에 따라 달라진다. 1. 인접 리스트 사용 시:각 노드에 대해 모든 인접한 노드를 방문해야 한다.각 노드는 한 번씩 방문하며, 각 노드의 모든 인접한 노드를 확인하는 데 걸리는 시간은 인접한 노드의 개수에 비례한다.따라서 시간 복잡도는 O(V + E) 이다.  (* V = 정점의 수, E = 간선의 수){ 'A': ['B', 'C', 'D'], 'B': ['A'], 'C': ['A', 'D'], 'D': ['A', 'C',..

이진 탐색 / 이분 탐색 (Binary Search) 알고리즘이란?배열에서 특정한 값을 효율적으로 찾기 위한 알고리즘이다.알고리즘의 기본 아이디어는 탐색 범위를 반으로 줄여가면서 원하는 값을 찾는 것이다. 정렬된 상태의 배열에서만 사용할 수 있다.  시간복잡도O(log n)  이분 탐색의 기본 원리초기화:start (시작점)를 배열의 첫 번째 인덱스로, end (끝점)를 배열의 마지막 인덱스로 설정한다.반복 조건:start가 end보다 작거나 같은 동안 반복한다. (start가 end를 초과하면 찾고자 하는 값이 배열에 없다는 것을 의미)중간점 찾기:배열의 중간 지점 mid를 (start + end) / 2로 계산한다.탐색 로직:찾고자 하는 값 targe..