전체 글 (92) 썸네일형 리스트형 [Algorithm 기초] 분할 정복 알고리즘 분할 정복 (Divide and Conquer) - 큰 문제를 작은 부분 문제로 나누어 해결하는 방법 --> 예) 합병정렬, 퀵 정렬, 이진 검색 등 - 문제를 나누어 처리하며 어려운 문제 해결 가능하고 병렬 처리에 이점이 있음 - 재귀 호출 구조이기 때문에 메모리를 많이 사용 분할정복과정 1. 문제를 하나 이상의 작은 부분 들로 분할 2. 부분들을 각각 정복 3. 부분들의 해답을 통합하여 원래 문제의 답을 구함 //20240303 분할 정복 알고리즘 사용예제 public class Main { public static int getMax(int[] arr, int left, int right) { int m = (left + right) / 2; if (left == right) { return arr.. [Algorithm 기초연습] 그리디 알고리즘 - 거스름 돈 문제 import java.util.HashMap; import java.util.Map; //20240303 그리디알고리즘 - 거스름 돈 문제 public class greedyPractice02 { public static void getChangeCoins(int receivedMoney, int price){ final int[] coins = {500, 100, 50, 10, 5, 1}; HashMap result = new HashMap(); int change = receivedMoney - price; int cnt = 0; for (int i = 0; i < coins.length; i++) { if (change < coins[i]){ continue; } int q = change / co.. [Algorithm 기초] 그리디 알고리즘 이진 탐색 ( Greedy Algorithm ) - 매 순간 현재기준으로 최선의 답을 선택해 나가는 기법 - 빠르게 근사치를 계산할 수 있고 결과적으로는 최적해가 아닐 수 있다. ( 항상 최적의 값을 보장하는것이 아니라 최적의 값의 ‘근사한 값’을 목표로 함) Activity Selection Problem - 종료 시간 기준으로 정렬 - 먼저 종료되는 활동 순, 겹치지 안흐는 순으로 선택 적용조건 속도는 빠르지만 최적해를 보장하지 못함 - 탐욕적 선택 특성(Greedy choice property) - 지금 선택이 다음 선택에 영향을 주지 않는다. - 최적 부분 구조(Optimal substructure) - 전체 문제의 최적해는 부분 문제의 최적해로 이루어진다. import java.util.Arra.. 이전 1 ··· 9 10 11 12 13 14 15 ··· 31 다음
