CS(Computer Science)/알고리즘 (총 7개) 썸네일형 리스트형 알고리즘 - Dynamic Programming(동적프로그래밍)이란? Dynamic Programming(동적계획법) 이란 1. Dynamic Programming(동적계획법)이란?큰 문제를 작은문제로 나누어 푸는 문제를 일컫는 말입니다. 동적 계획법이란 말 때문에 어떤 부분에서 동적으로 프로그래밍이 이루어지는 찾아볼 필요가 없습니다. 바로 동적프로그래밍이란 말을 창조한 사람도 이것이 단지 멋있어서 부여한 이름이라고 합니다. 1.1 Divide and Conquer(분할정복)과 비슷한데요?네, 거의 비슷하지만 결정적인 차이점이 있습니다. 바로 작은 문제가 중복이 일어나는지 안일어나는지 입니다. 분할정복은 큰 문제를 해결하기 어려워 단지 작은 문제로 나누어 푸는 방법입니다. 특징은 작은 문제에서 반복이 일어나는 부분이 없다는 점입니다. 동적프로그래밍은 어떨까요? 네, 작은 .. 알고리즘 - 그리디01 그리디(Greedy) 알고리즘이란? 그리디(Greedy) 알고리즘 이란- 그리디(Greedy) 알고리즘이란 탐욕알고리즘이란 뜻으로 각 단계에서 최선책만을 선택하며 다음단계로 진행하는 알고리즘을 말한다. - 최적의 해를 구하는 알고리즘은 아니다 최적의 해의 근사의 해를 구하는 알고리즘이다.- 동적프로그래밍이 지나치게 많은 일을 하는 것에서 착안하여 고안된 알고리즘이며 동적프로그래밍을 대체하는 것은 아니고 서로 보완하며 사용되는 알고리즘이다.- 각 단계에서 최선책만을 선택하기 때문에 현재의 선택에 의해 다음 단계의 조건이 변하는 경우에는 부적합한 알고리즘이다. 최적의 해가 아닌 이유?- 그리디 알고리즘은 당장 선택할 수 있는 경우중 최선의 선택을 하기 때문이다. 예를 들어 지금 당장 금을 팔면 1돈에 10000원인데 내일은 1돈에 12000원.. JAVA 퀵정렬(Quick Sort)이란 - 수정중 https://www.youtube.com/watch?v=7BDzle2n47c&t=303s 과정1. 배열에서 적절한 피봇을 선출한다- 배열에서 값이 중간값일 수록 좋지만 중간값을 찾기위해서는 탐색을 해야하므로 물리적으로 중간에 위치한 값을 피봇으로 선택 2. 배열의 시작위치의 인덱스를 L로 지정하고 배열의 끝 위치의 인덱스를 R로 지정한다 3. L은 피봇값보다 작은값(L Pivot)은 무시하며 인덱스를 1씩 감소시킨다(계속해서 감소하다가 Pivot의 위치에 다달으면 Pivot값보다 큰값이 아니므로 피봇의 위치.. JAVA 버블정렬이란(Bubble Sort) 버블정렬이란.- 두 인접한 원소를 검사하여 정렬하는 방법- 정렬 속도는 느리지만 코드가 단순하여 자주 사용된다.- 원소의 이동이 거품이 수면위로 올라오는 듯한 모습을 보여 지어진 이름이다. 과정1. 첫 원소와 바로 다음의 원소를 비교하여 뒤바꾼다 한 원소씩 이동하며 반복한다. 2. 이렇게 한 사이클을 돌면 제일 큰값(오름차순의 경우)이 맨마지막에 위치 하게 된다.3. 다시 맨첫 원소부터 정렬이 확정된 마지막 원소 전까지 1번 과정을 반복한다. 시간 복잡도 - Θ(n2) 코드 1) BubbleSort Class123456789101112131415161718192021public class BubbleSort { public void bubbleSort(int[] unsortedList) { for(int.. JAVA 선택정렬이란(Selection Sort) 선택정렬이란- 제자리 정렬 알고리즘의 하나 - 정렬되지 않은 자료중 과정1. 주어진 리스트중 가장 작은 값을 찾는다 2. 그 값을 맨앞에 위치한 값과 뒤 바꾼다3. 맨 처음 위치를 뺀 나머지리스트를 같은 방법으로 순회하여 교체한다. 시간 복잡도 - Θ(n2) 코드 1) SelectionSort Class1234567891011121314151617181920212223242526public class SelectionSort { public void selectionSort(int[] unsortedList) { for(int i = 0; i 알고리즘 성능분석 1. 공간복잡도 - 알고리즘에 사용되는 메모리 공간의 총량- 메모리 사용량의 분석결과 2. 시간복잡도 - 알고리즘에 사용되는 연산횟수의 총량- 속도에 대한 분석결과- 연산의 횟수를 센다 1. n번 반복 123for(int i = 0; i 프린터 큐 문제여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 .. 이전 1 다음
