인프런 강의 참고 동적 계획법 (Dynamic Programming) 이란 (출처 나무위키) 동적 계획법이란 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 이다. 즉, 답을 재활용!! 한다고 생각하면 쉽다. 기본적으로 분할 정복 알고리즘과 비슷하다. 동적 계획법은 계산 횟수를 줄일 수 있다. 특히 이 방법은 하위 문제의 수가 기하급수적으로 증가할 때 유용하다. +동적 계획법을 영문으로는 다이나믹 프로그래밍(dynamic programming)이라 표기하는데, 이름과는 달리 딱히 다이나믹하지도 않고 프로그래밍이라는 단어와도 큰 연관이 없다. 예시 피보나치 수열 //재귀함수를 이용한 피보나치 수열 함수 int fib(int n) { if (n == ..

삽입정렬 삽입정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. + 손 안의 카드를 정렬하는 방법과 같다. 새로운 카드를 정렬된 카드 사이의 알맞은 사이를 찾아 삽입해준다. 두번째 원소부터 시작하여 그 앞 원소들과 비교하여 삽입할 위치를 지정하고 원소를 뒤로 옮기고 그 자리에 원소를 삽입하여 정렬한다. 삽입정렬 GIF 이런식으로 두번째 원소부터 마지막 원소까지 정렬된 앞 원소들과 비교하여 알맞은 위치를 찾아 삽입한다. 역시 gif가 이해가 잘된다... C++로 구현 #include using namespace std; int a[10] = { 3,6,7,1,4,2,9,0,5,8 }; void insertion..

버블 정렬 버블정렬 (bubble sort)란 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간복잡도가 O(n^2)로 상당히 느리지만 코드가 단순하기 때문에 자주 사용된다. (출처 위키백과) GIF 으로 개념이해 오름차순정렬을 하게되면 첫번째 원소와 두번째 원소를 비교하여 첫번째 원소가 두번째 원소보다 크면 두 원소를 교환하고 두번째 원소와 세번째 원소를 비교하고, 세번째 원소와 네번째 원소를 비교하고 이런식으로 (마지막-1) 번째 원소와 마지막 원소를 비교하여 정렬한다. 이런식으로 1번 처음부터 끝까지 수행하게 되면(1회전 후) 배열의 가장 큰 원소가 맨 뒤로 이동하므로 2회전을 수행할때는 맨 끝에 있는 원소는 정렬에서 제외된다. 1회전을 할때 교환이 이루어지지 않으면 정렬이 된 상태라고 볼 수 있는..

선택정렬 선택정렬 (selection sort)은 제자리 정렬 알고리즘의 하나이다. 주어진 리스트 중에 최소값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)). 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 이 1,2,3을 계속 반복하는 알고리즘이다. 이런식으로 처음엔 첫번째 원소부터 마지막 원소중 최소값을 찾아 배열 맨 앞에 있는 원소와 교환하고 (정렬된 첫번째 원소를 제외한) 두번째 원소부터 마지막 원소중 최소값을 또 찾아 배열 두번쨰 원소와 교환하고 배열 마지막 원소는 자동으로 정렬되기 때문에 원소 개수 -1 만큼 반복해 주면 된다. C++ 로 구현 #include using namespace std; int a[10] = { 3,6,7,1,4,2,9,0,5,8 }..

이후에 추가로 알게된 것들을 계속 추가 할 예정이다. 인프런 강좌 내용을 참고하였습니다, 퀵 정렬 (quick sort) 퀵정렬은 분할정복 방법을 사용합니다. 분할정복방법이란 순환적(recursive)으로 문제를 푸는 하향식(top-down) 접근방법입니다. 분할: 배열을 pivot 을 기준으로 pivot보다 작은 값들과 pivot 보다 크거나 같은 값으로 두 부분으로 나눈다. 정복: 각 부분을 순환적으로 정렬한다. 합병: nothing to do (필요x) 슈도코드 A배열의 첫번째 원소를 p, 마지막 원소를 r로 설정한다. 마지막 수를 pivot으로 뒀을때 그 pivot이 어디에 위치해있는지 구하는 partition 함수를 이용한다. 검사하려는 값이 pivot보다 클때, 결국 오른쪽에 있는 원소들 값이..