FandPROG FandPROG

플로이드-와샬(Floyd-Warshall) 알고리즘은 그래프에서 모든 정점 쌍 간의 최단 경로를 찾는 알고리즘이다. 이 알고리즘은 특히 음의 가중치가 포함된 그래프에서도 동작하지만, 음의 사이클(negative cycle)이 있으면 고장난다.플로이드 와샬의 기본 개념플로이드 와샬은 기본적으로 Dp(Dynamic Programming)알고리즘을 사용하는 알고리즘이다. 플로이드 와샬의 핵심은 "거쳐가는 경로"이다. 플로이드 알고리즘은 "dp[i][j][k] = "i에서 j사이 거쳐가는 모든 정점의 번호가 k 이하인 최단거리"를 기반으로 둔 것이다.  그래프 표현:그래프는 일반적으로 n x n 크기의 인접 행렬로 표현된다. 여기서 n은 그래프의 정점의 수이다. 이 행렬의 각 요소 Floyd[i][j]는 정점 ..

백트래킹(Backtracking)은 모든 가능한 해를 탐색하는 과정에서, 현재 상태에서 더 이상 해를 찾을 가능성이 없는 경우 되돌아가서 이전 상태로 돌아가는 기법이다. 이 방법은 최적화 문제와 조합적 탐색 문제에서 사용되는 경우가 많다.백트래킹의 기본 개념문제 해결을 위한 상태 공간 트리:백트래킹은 상태 공간 트리를 탐색하면서 해결책을 찾는다. 상태 공간 트리는 가능한 모든 상태(해결책 후보)를 나타내는 트리를 말한다. 백트래킹은 이 트리의 모든 노드를 탐색하여 해를 찾는 방법이다.가능성 없는 해의 가지치기(Pruning):백트래킹의 핵심은 겹치거나 가능성이 없어보이는 경로를 탐색하지 않고 이를 더이상 탐색하지 않는 것다. 이를 가지치기(Pruning)이라고 부른다. 더이상 탐색하지 않아도 되는 경로는..

누적합 알고리즘(Prefix Sum Algorithm)은 배열이나 리스트같은 데이터에서 연속된 부분의 합을 빠르게 계산하기 위한 알고리즘이다. 이 알고리즘은 주어진 배열의 각 요소에 대해 이전 요소까지의 누적합을 미리 계산해 두고, 이를 활용하여 특정 구간의 합을 효율적으로 구하는 데 사용된다. 누적합과 관련된 여러 문제가 있지만 먼저 가장 기본적인 누적합의 형태에대해 알아보자.누적합 알고리즘의 기본 개념누적합 배열(Sum Array):주어진 배열 A의 누적합 배열 Sum을 만든다. S[i]는 A 배열의 0번째부터 i번째 요소까지의 합을 뜻한다. 즉, S[i] = A[0] + A[1] + ... + A[i]구간 합 계산:배열 A의 구간 [i, j] (i 시간 복잡도 전처리: 누적합 배열을 생성하는 데 O..

1. 탐욕 알고리즘(Greedy - 그리디) 그리디 알고리즘은 매번 항상 최적의 답안을 선택하여 적절한 해를 구해내는 알고리즘입니다. 탐욕 알고리즘은 과정이 직관적이기 때문에 일반적으로 시간 복잡도가 낮고, 구현이 단순하여 빠르게 동작합니다. 이때문에  이해하기 쉽고 구현하기 간단합니다. 하지만 그리디 알고리즘이 항상 최적해를 보장하지 않는 경우가 많습니다.2. 탐욕 알고리즘의 특성(1) 탐욕적인 선택조건(Greedy Choice Property) : 각 단계에서 내리는 최적의 선택이 결국 전체 문제에 대한 최적해로 이어질 수 있어야 합니다. (2) 최적 부분 구조(Optimal property) : 문제의 최적해가 부분 문제들의 최적해로 구성될 수 있어야 합니다. 3. 동전 문제를 통한 탐욕 알고리즘의..

이진 탐색(Binary Search)은 정렬된 배열에서 원하는 값을 효율적으로 찾는 알고리즘입니다. 배열의 중간 요소와 목표 값을 비교하여, 목표 값이 더 작으면 왼쪽 절반, 더 크면 오른쪽 절반을 선택하여 검색을 반복합니다. 최악의 경우 시간 복잡도는 O(log⁡n)입니다.「이진 탐색의 동작 과정」1. 분할 과정 (Divide)우선 알아야할점은 배열은 항상 정렬 되어있어야 한다는 것입니다. 첫번째 분할과정에서는 현재 배열의 중간 원소를 선택합니다. 그 후 중간 원소와 찾고자 하는 값을 비교합니다.-IF 찾고자 하는 값이 중간 요소보다 작으면 : 배열에서 중간 원소의 왼쪽 절반을 선택합니다.-IF 찾고자 하는 값이 중간 요소보다 크면 : 배열에서 중간 원소의 오른쪽 절반을 선택합니다.12345 위 배열에..

퀵 정렬(Quick Sort)은 분할 정복 알고리즘의 일종으로, 배열을 임의의 기준으로 두 부분으로 나눈 후 각각을 재귀적으로 정렬하는 방식입니다. 평균 시간 복잡도는 O(nlog⁡n)이며, 최악의 경우 O(n ² )이 될 수 있습니다. 일반적으로 빠른 수행 속도로 널리 사용되는 정렬입니다.「퀵 정렬의 동작 과정」1. 분할 과정 (Divide) 퀵 정렬의 첫번째 단계에서는 "피벗(pivot)"을 정해 이를 통해 구간을 나누는 과정입니. 피벗은 일반적으로 배열의 첫 번째 원소, 마지막 원소, 또는 중앙값을 선택합니다. 피벗을 정한뒤, 배열의 원소들을 피벗을 기준으로 두 부분으로 나눕니다. 피벗보다 작은 원소들은 피벗의 왼쪽에, 피벗보다 큰 원소들은 피벗의 오른쪽에 위치하도록 합니다. -처음 주어진 배열[3..

병합정렬(Merge-sort)은 퀵 정렬(Quick Sort)와 같이 분할정복 알고리즘을 이용한 정렬 알고리즘중 하나입니다. 선택정렬같은 O(N²)의 느린 정렬 알고리즘과 다르게 병합정렬은 시간복잡도 O(NlogN)의 빠른 정렬 알고리즘입니다.「병합 정렬의 동작 과정」1. 분할 과정 (Divide)  병합정렬의 첫 번째 단계인 분할과정에서는 배열을 가능한 한 작게 나눕니다. 이 단계에서는 배열을 중간을 기준으로 두 개의 하위 배열로 분할합니다. 이 과정을 배열에 원소가 하나가 될때까지 계속 반복하면 됩니다. -처음 주어진 배열 ↓ [38, 27, 43, 3, 9, 82, 10] -첫번째 분할 ↓ [38, 27, 43], [3, 9, 82, 10] -두번째 분할  [38, 27], [43],  [3, 9]..

1. 분할정복 알고리즘 분할정복(Divide and Conquer) 알고리즘은 여러알고리즘의 기본이 되는 방법중 하나로 복잡한 문제를 더 단순하고 작은 문제로 나누어 해결하는 방식으로 이루어집니다. 잘 알려진 예로는 병합 정렬(Merge Sort)과 퀵 정렬(Quick Sort)등이 있습니다.  2. 분할 정복 알고리즘의 과정 분할정복 알고리즘의 설계 과정은 세 단계로 이루어집니다. 이 각각의 과정은 분할(Divide), 정복(Conquer), 결합(Combine)이라고부릅니다. 1. 분할(Divide): 해결하려는 문제를 더 작은 하위 문제로 나누는 과정. 2. 정복(Conquer): 나눈 하위 문제를 재귀적으로 해결. 단, 하위 문제를 더이상 분할할 수 없다면 직접 해결. 3. 결합(Combine):..