종식당

Greedy Algorithms이란 그리디 알고리즘이란 현재 상황에서 가장 좋은 선택지를 고르는 알고리즘이며 탐욕 알고리즘이라고도 부른다. 현재 상황에서 가장 좋은 결과를 선택한다고 해서 최종적인 결과 도출에 대한 최적해를 보장해 주는 것은 아니다! 그림을 통해 좀 더 자세히 알아보겠다. 가장 큰 수 를 찾아야 하는 문제라고 쳤을 때, 우리는 시작에서 부터 6->128로 가는 경로가 가장 큰 수를 찾는 경로라는 것을 직관적으로 알 수 있다. 하지만 그리디 알고리즘을 이용한다면 시작에서 17->23으로 가는 경로를 선택할 것이다. 그리디 알고리즘의 두가지 조건 탐욕스러운 선택 조건 Greedy-choice property 탐욕적인 선택으로 인해 전체 문제의 최적해를 반드시 도출할 수 있어야 한다는 것이다...

병합 정렬 주어진 배열을 더 이상 쪼갤 수 없을 때까지 데이터 크기의 절반으로 계속 나누어, 재귀적으로 정렬을 수행하면서 통합하는 정렬 알고리즘 이 알고리즘 총 3단계로 나눌 수 있다. Divide 주어진 배열을 데이터 크기의 절반으로 나누어 2개의 부분 배열로 분할한다. 이를 더 이상 쪼갤 수 없을 때까지 분할한다. Conquer 나누어진 부분 배열에 대해서 재귀적으로 합병 정렬을 한다. Combine 정렬한 2개의 부분 배열을 통합하여 원래 크기의 정렬된 배열로 만든다. Merge sort의 슈도 코드 Merge sort의 수행 과정 Merge sort의 시간 복잡도 먼저 전체 리스트를 반으로 나누어 가면서 리스트를 분할한다. 만약 길이가 8인 리스트라면 이를 총 3번 나눌 것이고, 길이가 16인 리..

삽입 정렬 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. 어떠한 리스트가 있다고 가정했을 때 두 번째 위치의 값부터 정렬을 시작할 것이다. 이를 key값이라고 부를것이다. 해당 key값의 앞에 있는 데이터부터 비교하여 key값이 더 작다면, 데이터를 key값 뒤 인덱스로 복사 이를 key값이 더 큰 데이터를 만날 때까지 반복 큰 데이터를 만난 위치 바로 뒤에 key값을 이동 말로 풀어쓰면 정확하게 이해가 되지 않아 이를 그림을 보며 설명하겠다. 위 사진을 참고하면 먼저 리스트의 두 번째 값을 key값으로 정하고 이를 이전의 값과 크기를 비교하며 정렬해 주는 모습을 확인할 수 있다. 정렬이 완료되면 key값을 ..