자료구조 및 알고리즘23 [알고리즘] 자바에서의 병합 정렬 병합 정렬(Merge Sort) - 재귀 용법을 활용한 정렬 알고리즘 1. 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 2. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 3. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. * 분할 정복 알고리즘의 대표적인 예시 중 하나이다. * 병합 정렬은 하나의 함수를 가지고 재귀 호출을 했던 지금까지 와는 달리 함수 2개를 가지고 재귀 호출을 하는 알고리즘이다. - 하나는 리스트를 절반으로 자르는 함수 - 또 하나는 정렬된 리스트를 정렬해서 병합해주는 함수 자바 코드로 직접 살펴보자. 일단 전체 코드는 이렇게 된다. - MergeSort.java import java.util.ArrayList; import java.uti.. 2021. 12. 3. [알고리즘] 자바에서의 퀵 정렬 퀵 정렬(Quick Sort) - 퀵 정렬은 정렬 알고리즘의 꽃이라고 할 수 있다. - 기준점(pivot) 을 정해서, 기준점 보다 작은 데이터는 왼쪽(left), 큰 데이터는 오른쪽(right) 으로 모으는 함수를 작성한다. - 각 왼쪽, 오른쪽은 재귀 용벙을 사용해서 다시 동일 함수를 호출하여 위 작업을 반복한다. - 함수는 왼쪽 + 기준점 + 오른쪽 으로 리턴한다. - 기준점을 고를땐 해당 리스트의 맨 앞에 있는 데이터로 결정한다. - 왼쪽, 오른쪽으로 갈라진 이후, 각 리스트 길이가 1 이하라면 해당 리스트를 그대로 리턴해준다. - 그렇지 않으면 기준점을 결정하고 해당 기준점 보다 작은지 큰지를 판별한 다음, 작다면 왼쪽 재귀 호출, 크다면 오른쪽 재귀 호출을 수행한다. - 각 재귀 호출을 수행하.. 2021. 12. 3. [알고리즘]자바에서의 동적 계획법(Dynamic Programming - DP) 동적 계획법(Dynamic Programming) 과 분할 정복(Divide and Conquer) * 동적 계획법(DP) - 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘 이다. - 상향식 접근법으로, 가장 최하위 해답을 구한 후 이를 저장하고, 해당 결과값을 이용해서 상위 문제를 풀어가는 방식이다. - Memoization(메모이제이션) 기법을 사용한다. - 프로그램 실행 시 이전에 계산한 값을 저장해서 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술이다. - 잘개 쪼개진 작은 부분 문제들을 한번씩만 풀기 위해서 사용한다. - 예시 : 피보나치 수열 - 말이 어려울 뿐이지 사실 한.. 2021. 12. 2. [알고리즘] 자바에서의 재귀 호출(Recursive Call) # 2 다음과 같은 문제를 살펴보자. https://www.acmicpc.net/problem/18511 18511번: 큰 수 구성하기 첫째 줄에 N, K의 원소의 개수가 공백을 기준으로 구분되어 자연수로 주어진다. (10 ≤ N ≤ 100,000,000, 1 ≤ K의 원소의 개수 ≤ 3) 둘째 줄에 K의 원소들이 공백을 기준으로 구분되어 주어진다. 각 www.acmicpc.net 문제의 설명을 보면 제시되는 숫자 N 과 1 ~ 9 까지의 숫자가 1개 에서 최대 3개 까지 저장되는 집합 K 가 주어질 때, K 집합 내부에 들어있는 원소들만으로 만들수 있는 숫자들 중에서 숫자 N 이하의 최대값을 찾으라고 되어 있다. 알고리즘 분류를 보면 무식하게 모든 경우의 수를 다 뒤져보는 완전 탐색 알고리즘인 브루트 포스(B.. 2021. 12. 1. 이전 1 2 3 4 5 6 다음
