프로그래밍 공부

Kadane's Algorithm은 연속된 부분 수열의 최대 합을 찾는 알고리즘으로, 동적 계획법(Dynamic Programming)을 기반으로 한다. 이 알고리즘은 O(n)의 시간 복잡도로 효율적으로 해결할 수 있다.알고리즘 목표입력: 길이 n인 수열 arr (음수와 양수 모두 포함 가능).목표: 이 수열에서 연속된 부분 수열 중에서 그 합이 가장 큰 값을 찾는 것.알고리즘의 기본 아이디어연속된 수들의 합이 최대가 되는 구간을 찾기 위해, 각 인덱스에서 끝나는 부분 수열의 최대 합을 동적으로 계산.특정 위치에서 연속된 부분 수열의 최대 합을 구하려면 그 위치에서 "현재까지 계산된 최대 연속합"을 유지하면서, 그 값을 계속 갱신해 나가는 방식으로 해결.구체적인 알고리즘 흐름초기화:첫 번째 원소를 cur..

x^2 + y^2 = z^2을 만족하는 수를 찾으면 된다. 코드 #include #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); int cnt = 0; clock_t start, end; start = clock(); for(int i = 1; i

퀵 정렬은 일반적으로 사용되고 있는 아주 빠른 정렬 알고리즘임 알고리즘 먼저 배열을 두 그룹으로 나눕니다 그룹을 나누는 순서는 임의의 피벗을 선택한후 피벗을 기준으로 피벗보다 큰 값은 피벗 뒤, 피벗보다 작은 값은 피벗 앞에 원소를 넣어준다. 글을 읽는 것 보단 코드를 보는게 이해가 빠를것이다. void swap(int *x, int *y){int tmp = *x; *x = *y; *y = tmp;} void partition(int arr[], int left, int right){ int pl = left; int pr = right; int pivot = arr[(pl + pr) / 2]; do{ while(arr[pl] pivot) pr--;..

삽입 정렬은 선택한 요소를 "그보다 더 앞쪽의 알맞은 위치에 삽입"하는 작업을 반복해 정렬하는 알고리즘이다. 선택 정렬과 비슷해 보이지만 선택 정렬은 "값이 가장 작은 요소를 선택해서 옮기는 것"이다. 바로 알고리즘을 설명하자면, 요소를 선택하고 그 요소의 값보다 작은 요소를 만날 때까지 이웃한 왼쪽의 요소를 대입하는 작업을 반복하다 멈추면 멈춘 위치에 그 요소를 대입한다. 알고리즘 1. 정렬된 열의 왼쪽 끝에 도달함. 2. tmp보다 작거나 같은 key값을 갖는 항목을 발견함. 이 두 조건을 만족할 때까지 설명한 작업을 반복한다. 코드 void insertion(int arr[], int size){ int i, j; for(i = 1; i < size ; i++){ // i까지는 정렬이 끝남 int ..

선택 정렬은 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘이다. 예를들어 배열안의 원소가 { 3, 2, 5, 4, 1 }일 때 원소가 교환이 일어난 것만 표현할 경우 { 1, 2, 5, 4, 3 } -> { 1, 2, 3, 4, 5 }순으로 정렬이 완료된다. 알고리즘 1. 아직 정렬하지 않은 부분에서 가장 작은 값의 인덱스를 선택한다. 2. 가장 작은값의 인덱스의 요소와 정렬하지 않은 부분의 첫 번째 요소를 교환한다. 이걸 n - 1회 반복해주면 된다. 코드 // 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘 void Selection_Sort(int arr[], int size){ for(int i = 0; i < size - 1; i++){ i..

배열을 정렬하기 위한 다양한 알고리즘이 있다 이 글은 정렬의 기초 중의 기초인 버블 소트에 대해 작성한다. 버블 소트는 이웃한 두 요소의 대소 관계를 비교하여 교환을 반복한다. 예를 들어 배열 안에 원소가 { 5, 4, 3, 6, 2 }가 있을 때 배열의 크기를 n을 5라고 하면 배열의 끝 부분인 n - 1부터 배열 안의 모든 원소를 비교하여 교환해주는 방식이다. 이를 나타내면 { 5, 4, 3, 6, 2 } -> { 2, 5, 4, 3, 6 } -> { 2, 3 ,5, 4, 6 } -> { 2, 3, 4, 5, 6 } 이 순서대로 정렬을 마친다. 보면 알 수 있듯이 버블 소트는 원소를 한 개씩 정렬해 나가는 걸 알 수가 있다. 알고리즘 요소의 개수를 size라 할때 1. 배열의 처음 인덱스부터 size..