[Algorithm] DP(Dynamic Programming) 동적계획법

동적계획법(DP) 이란? 하나의 큰 문제를 여러개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할때 사용하는 것 계산한 값을 저장해두는 메모리 장소 캐쉬(cache)에 저장하고, 답을 여러번 계산(중복)하는 대신 한번 만 계산해서 계산결과를 재활용함으로써 속도 향상을 꾀할 수 있는 알고리즘이다 * 그럼 분할 정복이랑 뭐가 다른건가요? 동적계획법과 분할 정복이 차이가 발생하는 부분은 문제를 나누는 방식이다 분할 정복은 단지 큰문제를 작은 문제로 나누어 푸는 것으로 중복된 것이 없다 동적 계획법은 어떤 부분 문제는 두개 이상의 문제를 푸는 데(반복이 일어남) 사용될 수 있기 때문에, 답을 여러번 계산 하는 대신 한번만 계산한다(중복된 것 활용) * 그럼 다른 dfs등 과 같은 재귀함수 쓰..

[알고리즘] 병합정렬(Merge Sort)의 개념 with c++

병합정렬 또는 합병정렬은 정렬할 데이터들을 일단 반으로 쪼개고 각 각 정렬한 후 나중에 합치는 알고리즘이다. 비교 기반 정렬 알고리즘이고, 일반적인 방법으로 구현했을 때 안정 정렬에 속하며 분할 정복 알고리즘의 하나이다. 매번 정렬된 데이터를 담을 배열 공간이 추가적으로 필요하다는 점에서 메모리 사용이 비효율적인 문제가 있다. 이에 병합 정렬의 시간 복잡도는 어떤 상황에서도 O(N*logN)이다. 병합 정렬 c++ 코드구현 #include #include //배열 #include using namespace std; int a[101], b[101], c[300]; int main(){ // 두 배열 합치기 int n, m, i, p1=1, p2=1, p3=1;//포인트 scanf("%d", &n); f..

[알고리즘] 삽입 정렬(Insertion sort) 의 개념 with c++

삽입 정렬이란 자료 배열의 모든 요소를 앞에서 부터 비교하고자 하는 타겟값(tmp)과 정렬된 값을 비교하여 자신의 위치를 찾아 삽입하면서 정렬해나가는 알고리즘이다. 매번 비교할 때마다 앞 부분에 해당하는 범위 모두 타겟값과 비교하여 해당 원소를 삽입할 수 있는 위치를 찾아 배열 위치에 넣는다. 📌정렬 과정(오름차순) 1. 2번째 원소부터 비교 시작한다 2. 이전 위치에 있는 원소들과 타겟이 되는 원소들을 비교한다(타켓 원소는 임시변수에 넣는다) 3. 타겟 원소가 이전 위치에 있던 원소보다 작다면 위치를 바꾼다 4. 이전 데이터도 차례대로 비교하며 정렬해나간다 5. 이 방법을 반복해서 정렬한다 📌특징 구현이 간단하다 배열이 길어질수록 효율이 떨어진다 선택 정렬이나 버블 정렬과 같은 O(n^2) 알고리즘에 ..

[알고리즘] 버블 정렬(Bubble sort)의 개념 with c++

버블 정렬은 인접한 두 수를 계속해서 비교하여 정렬하는 알고리즘이다. 1. 인접한 두 수를 대소를 비교한다. 2. 내림차순, 오름차순에 따라 두 수의 자리를 바꾼다. 3. 나머지 값들도 동일하게 처리한다. 구현이 매우 간단하여 코드 구현이 쉽지만, 비교 작업이 많기 때문에 시간 복잡도(n^2) 로 오래걸린다는 단점이 있다. 적은 양의 데이터를 정렬할때는 버블 정렬을 쓸 수 있지만, 대용량의 데이터를 정렬시 엄청 시간이 소요될 것이다. 📌 버블 정렬 c++ 코드 구현 #include using namespace std; int main(){ //버블정렬-오름차순 int n, i,j, tmp, a[101]; scanf("%d", &n); for(i=0; i

[알고리즘] 선택 정렬(Selection Sort) 의 개념 with c++

선택 정렬(Selection Sort) 선택 정렬은 제자리 정렬 알고리즘의 하나로 정렬되지 않은 데이터들 중에서 가장 작은 값을 추출하여 가장 맨 앞으로 정렬해나가는 알고리즘이다. 1. 배열 중에 최솟값을 찾는다. 2. 최솟값을 맨 앞으로 정렬시킨다.(swap) 3. 나머지 값들도 동일한 방식으로 정렬해나간다. 알고리즘이 단순하고 사용할 수 있는 메모리가 제한적인 경우 사용하기에 용이하며, 구현이 간단하지만 비효율적인 방법인 알고리즘이다. 📌시간 복잡도 기준값과 비교값들 중 최솟값을 찾기 위해 이중 for문 필요 - 첫 번째 회전 비교 횟수 : 1 부터 (n-1) = n-1 - 두 번째 회전 비교 횟수 : 2 부터 (n-1) = n-2 ... => 최솟값 찾기 : n-1, n-2, ..., 2, 1 번 ..