공부 기록

[알고리즘] 카데인 알고리즘 (Kadane's Algorithm)

카데인 알고리즘 (Kadane's Algorithm) ?배열 내의 연속된 부분 배열의 합 중에서 합이 최대인 부분 배열을 찾는 알고리즘이다.배열을 한 번 순회하면서 현재 위치에서 끝나는 가장 큰 부분 배열의 합을 계산하고 이를 통해 전체 배열에서의 최대 부분 배열 합을 구하는 방식이다. 이 알고리즘은 시간 복잡도가 O(n), 공간 복잡도가 O(1)로 매우 효율적이다. 또한 1차원 배열뿐만 아니라 2차원 배열에서도 적용할 수 있다. 2차원 배열에서 최대 합을 갖는 부분 행렬을 찾는 문제는 복잡하지만 알고리즘을 행별로 적용하여 문제를 1차원 문제로 축소함으로써 해결할 수 있다. 핵심 아이디어카데인 알고리즘은 다음과 같은 두 가지 값을 사용한다.현재까지의 최대 부분 배열 합 (current_max) : 특정 ..

DFS (깊이 우선 탐색) 와 BFS (너비 우선 탐색) ?그래프 탐색 알고리즘의 대표적인 예로 이 알고리즘들은 그래프, 트리, 네트워크 등의 자료구조를 탐색하는 데 사용한다. 그래프는 노드(정점)와 노드 간의 연결선(간선)으로 이루어진 자료구조를 말한다.노드 (Vertex) : 그래프에서 하나의 개체를 말하며 정점이라고도 한다.간선 (Edge) : 두 노드를 연결하는 선인접 노드 : 특정 노드와 직접 연결된 노드DFS (깊이 우선 탐색)시작 노드에서부터 한 방향으로 갈 수 있을 만큼 깊이 내려가며 탐색을 진행한다. 그 깊이의 노드를 모두 탐색한 후 더 이상 갈 수 없게 되면 이전 정점으로 돌아가 다음 노드를 탐색하는 방식이다. 탐색 과정시작 노드에서 출발하여 다음 노드로 이동더 이상 방문하지 않은 인..

이분 / 이진 탐색 (Binary Search) ?정렬된 리스트에서 특정 값을 찾는 데 사용되는 효율적인 알고리즘이다. 리스트의 중앙값과 목표 값을 비교하여 목표 값이 중앙값보다 작으면 리스트의 왼쪽 절반을 탐색하고 크면 리스트의 오른쪽 절반을 탐색하는 방식으로 진행된다. 이렇게 계속해서 리스트를 반씩 줄여 나가면서 값을 찾는다.  이분 / 이진 탐색 알고리즘의 단계초기화: 리스트의 처음과 끝 인덱스 설정반복 또는 재귀: 중앙값을 계산하고 이 값을 목표 값과 비교값 비교:목표 값 = 중앙값 → 해당 인덱스 반환목표 값 목표 값이 > 중앙값 → 리스트의 오른쪽 절반 탐색반복 종료: 리스트의 탐색 범위가 0이 되면 목표 값이 리스트에 없는 것으로 간주하고 탐색 종료 이분 / 이진 탐색 알고리즘의 시간 복잡도..

그리디 알고리즘? 최적해를 구하는 데 사용되는 알고리즘의 한 유형으로 문제를 해결하는 과정에서 현재 상황에서 가장 좋다고 생각되는 선택을 반복적으로 하는 방식이다.즉 전체적인 최적해를 고려하지 않고 현재 단계에서 가장 좋은 선택을 하는 것을 반복하여 최종적인 해결책을 찾는 알고리즘이다.이 알고리즘은 각 단계에서의 최적 선택이 결국 전체 문제에 대한 최적 해결책을 보장할 수 있을 때 유효하다.  특징탐욕적 선택 속성 (Greedy Choice Property): 각 단계에서 현 시점에서 가장 최적인 선택을 한다.최적 부분 구조 (Optimal Substructure): 문제의 최적 해결 방법이 부분 문제들의 최적 해결 방법으로 구성될 수 있다.장점간단하고 직관적: 구현이 간단하고 이해하기 쉬운 편빠른 수행..

유클리드 호제법 최대공약수 GCD와 최소공배수를 구하는 방법 a,b ∈ ℤ 이고, r = a mod b (a를 b로 나눈 나머지)라고 가정하면 r 은 (0 ≤ r < b)이고 a ≥ b 이다. 그러면 이때 a와 b의 최대공약수를 (a, b)라고 할 때 (a, b)의 최대공약수는 (b, r)의 최대공약수와 같아지고 이는 다음과 같다. GCD(a, b) = GCD(b, r) 예시 1. a = 64, b = 42 일 경우 GCD(64, 42)일 때 r = 22이고 GCD(64, 42) = GCD(42, 22)이다. GCD(42, 22)를 보면 r = 20 이고 GCD(42, 22) = GCD(22, 20)이다. GCD(22, 20)을 보면 r = 2 이고 GCD(22, 20) = GCD(20, 2)이다. GC..

에라토스테네스의 체 소수를 구하는 방법 중 하나 i = 2 부터 √N 이하까지 반복하여 자연수들 중 i를 제외한 i의 배수들을 제외시키는 방식 시간복잡도: O(Nlog(log N)) 다음의 그림과 같이 1을 제외하고 2부터 시작하여 2의 배수인 4, 6, 8, 10 .. 는 이미 2를 약수로 가져 소수가 아니므로 제외하고 그 후 3의 배수인 9, 15, 21, 27 .. 들도 이미 3를 약수로 가져 소수가 아니므로 제외하면서 범위 내 소수를 구하는 방식이다. 왜 N 까지가 아니라 √N 까지일까? n = a × b 라고 하고 하면 1 ≤ a, b √ N 하다면 a × b > n 이므로 a와 b 중 적어도..