갱주

📌그리디 알고리즘이란? 그리디 알고리즘(탐욕 알고리즘, Greedy Algorithm)은 문제를 해결할 때 현재 시점에서 가장 최선의 선택(탐욕적인 선택)을 반복적으로 수행하여 최종 해답에 도달하는 알고리즘 기법입니다. 이 알고리즘은 각 단계에서 가능한 최적의 선택을 하지만, 그 선택이 전체 문제에 대해서도 최적해를 보장하는지에 대해서는 문제마다 다릅니다. 🙄 그리디 알고리즘의 기본 원리선택의 기준: 매 단계에서 가장 좋은 선택(탐욕적 선택)을 합니다.최적 부분 구조: 전체 문제의 최적 해결 방법이 부분 문제의 최적 해결 방법들로 구성될 수 있어야 합니다.일관된 선택: 그리디 알고리즘이 적용 가능한 문제는 이렇게 매 순간의 선택이 최종 결과에도 영향을 미치지 않고, 항상 최적해를 보장하는 경우여야 합..

이분탐색?이분 탐색(Binary Search)은 정렬된 배열에서 원하는 값을 빠르게 찾는 효율적인 알고리즘입니다.배열을 절반씩 나누어 탐색하기 때문에 시간 복잡도는 O(log n)입니다.알고리즘 설명정렬된 배열에서 중간 인덱스를 선택합니다.찾고자 하는 값(target)과 중간 값(mid) 값을 비교합니다.만약 target이 중간 값보다 작다면, 왼쪽 절반만 탐색합니다.만약 target이 중간 값보다 크다면, 오른쪽 절반만 탐색합니다.이 과정을 반복하여 찾고자 하는 값이 중간 값과 같아질 때까지 배열을 절반으로 나누어 탐색합니다.구현 코드1. 재귀 방식def binary_search(arr, target, low, high): if low > high: return -1 # 값을 찾지 ..

유클리드 호제법?유클리드 호제법(Euclidean Algorithm)은 두 수의 최대공약수(GCD)를 구하는 방법 중 하나입니다.유클리드 호제법은 나눗셈과 나머지를 이용하여 반복적으로 계산하여 GCD를 구하는 매우 효율적인 알고리즘으로, 시간 복잡도는 O(log(min(a, b)))입니다.알고리즘 설명유클리드 호제법은 다음 규칙을 기반으로 동작합니다:두 수 a와 b (a > b)가 있을 때, a를 b로 나눈 나머지를 r이라고 합니다.이제 a와 b의 최대공약수는 b와 r의 최대공약수와 같습니다.이 과정을 r이 0이 될 때까지 반복합니다. 이때 나머지가 0이 되면, b가 바로 최대공약수(GCD)입니다.구현 코드def gcd(a, b): while b != 0: a, b = b, a % b ..

에라토스테네스의 체?에라토스테네스의 체(Sieve of Eratosthenes)는 주어진 범위 내에서 모든 소수를 찾는 알고리즘입니다.이 알고리즘은 소수의 배수를 제거하는 방식으로 동작하며, 시간 복잡도는 O(n log log n)입니다.(소수란 1과 자기 자신만을 약수로 가지는 수)알고리즘 설명2부터 n까지의 자연수를 나열합니다.가장 작은 수인 2를 소수로 선택합니다.2를 제외한 2의 배수들을 모두 지웁니다.다음 남은 수 중 가장 작은 수를 소수로 선택하고, 그 수의 배수들을 모두 지웁니다.이 과정을 반복하여 선택된 소수의 배수를 모두 제거합니다.더 이상 지울 배수가 없으면 남아 있는 수들이 모두 소수입니다. 구현 코드def eratosthenes_sieve(n): # 0과 1은 소수가 아니므로 ..

너비 우선 탐색(BFS, Breadth-First Search) 알고리즘은 그래프나 트리의 노드를 탐색하는 방법으로, 특정 시작 노드에서부터 인접한 모든 노드를 탐색한 다음, 그 다음 수준의 노드로 이동하여 다시 탐색하는 방식입니다.동작 원리시작 노드 선택: 탐색을 시작할 노드를 선택합니다.큐 사용: BFS는 큐(Queue) 자료구조를 사용하여 탐색할 노드를 관리합니다. 먼저 들어온 노드가 먼저 나가는 FIFO(First In, First Out) 방식입니다.탐색: 시작 노드를 큐에 추가하고, 큐가 빌 때까지 다음을 반복합니다:큐에서 노드를 꺼내어 방문합니다.방문한 노드의 인접 노드를 큐에 추가하고, 이때 방문하지 않은 노드만 추가합니다.종료 조건: 모든 노드를 탐색할 때까지 이 과정을 반복합니다.BFS..

깊이 우선 탐색(DFS, Depth-First Search) 알고리즘은 그래프 또는 트리의 노드를 탐색하는 데 사용되는 기본적인 알고리즘입니다. DFS는 한 방향으로 가능한 깊게 탐색한 후, 더 이상 갈 수 없게 되면 마지막 분기점으로 되돌아가서 다른 경로를 탐색하는 방식으로 작동합니다.  동작 원리시작 노드 선택: 탐색을 시작할 노드를 선택합니다. 일반적으로 루트 노드나 시작 지점이 됩니다.탐색: 현재 노드를 방문하고, 그 노드와 연결된 인접 노드 중 방문하지 않은 노드를 선택하여 탐색을 계속합니다.재귀적 호출: 방문한 노드에서 인접한 노드를 재귀적으로 탐색합니다.백트래킹: 더 이상 방문할 노드가 없으면 이전 노드로 되돌아가 다른 인접 노드를 탐색합니다.종료 조건: 모든 노드를 탐색할 때까지 이 과정을..