알고리즘4 [알고리즘] 그리디 알고리즘(Greedy Algorithm) 그리디 알고리즘이란?그리디 알고리즘(탐욕법)이란 현재 상황에서 가장 좋은 것(최선의 선택)을 고르는 알고리즘을 뜻한다. 그리디 알고리즘은 동적 프로그래밍(DP)을 간단한 문제 해결에 사용하면 지나치게 많은 일을 한다는 것을 착안해 고안되었다. 그리디 알고리즘은 현재 상황에서 가장 좋은 결과를 선택해 나가는 방식의 알고리즘 설계 기법이다.하지만 이 가장 좋은 결과는 항상 최종적인 결과 도출에 대한 최적해를 보장해 주는 것은 아니다. 위 그림에서 가장 큰 값이 최적의 값일 때, 그리디 알고리즘은 현재 상황에서 가장 최적의 값을 구하기 때문에최종적인 답은 23이 나오게 된다(최적의 값: 128). 그리디 알고리즘은 항상 최종적인 결과 도출에 최적해를 보장해 주는 것이 아니기 때문에 상황에 맞게 사용해야 한.. 2024. 6. 18. [알고리즘] 다이나믹 프로그래밍(Dynamic Programming) 다이나믹 프로그래밍(동적 계획법)은 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법이다. 알고리즘 설계 기법: 문제 해결을 위해 알고리즘을 설계하는 방법이나 접근 방식을 뜻한다.설계 기법은 알고리즘을 개발하고 구현하는 데 사용되는 전략과 원칙을 뜻한다. DP와 재귀 호출의 차이점DP와 재귀 호출의 차이점을 알기 전에 하향식 접근법과 상향식 접근법이 무엇인지 알아야 한다.1. 하향식(top-down) 접근법과 상향식(bottom-top) 접근법하향식 접근 방식은 큰 문제를 작은 하위 문제로 쪼개서 해결하는 방법이다. 주로 재귀 호출을 할 때 사용된다.상향식 접근 방식은 작은 문제들부터 시작해 작은 문제들의 결과를 이용해 점점 큰 문제의 결과를 구하는 방법. 2. 메모이제이션(Memo.. 2024. 6. 12. [Kotlin] 유클리드 호제법 알고리즘 유클리드 호제법이란? 2개의 자연수의 최대공약수를 구하는 알고리즘이다. 기본 과정 예시로 32와 24의 최대공약수를 구하면, 32는 24로 나누어 떨어지지 않기 때문에, 32를 24로 나눈 나머지를 구한다. => 8 32는 8로 나누어 떨어진다. 따라서 32와 24의 최대공약수는 8이다. 예제 코드1. 재귀 함수를 사용 package algorithm import java.io.BufferedReader import java.io.InputStreamReader fun main() { val bf = BufferedReader(InputStreamReader(System.`in`)) val number = bf.readLine().split(" ") val a = number[0].toInt() val .. 2022. 10. 24. [Kotlin] 이진 탐색 알고리즘 이진 탐색이란? 정렬된 리스트의 중간 값을 이용해 검색 값을 줄여 가면서 원하는 값을 찾는 알고리즘 탐색 과정 정렬된 리스트의 중간값을 찾는다. 찾는 수가 중간값보다 크면 오른쪽으로, 작으면 왼쪽으로 검색 범위를 좁힌다. 1, 2번을 반복한다. 이 과정을 반복하면 그냥 반복문을 이용해 찾는 것보다 더 빠르게 원하는 숫자를 찾을 수 있다. 예제 코드 숫자의 범위와 원하는 숫자를 입력하고 이진 탐색으로 그 숫자를 찾는 알고리즘 package algorithm import java.io.BufferedReader import java.io.InputStreamReader fun main() { val bf = BufferedReader(InputStreamReader(System.`in`)) val array.. 2022. 10. 21. 이전 1 다음 728x90
