알고리즘 (5) 썸네일형 리스트형 5. 그리디 알고리즘(Greedy Algorithm) ✅ 그리디 알고리즘이란? ㅇ 그리디 알고리즘은 탐욕 알고리즘이라고 불리며, 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. ㅇ 주로 최적해를 구하는데에 사용되는 방법이며, 속도가 빠르다는 장점이 있다. ㅇ 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행된다. - 순간마다 하는 선택은 그 순간에 대해서는 지역적으로 최적이지만, 최종적(전역적)으로는 최적이라고 보장할 수 없다. ㅇ 특성을 가지는 문제들을 해결하는데 강점이 있는 알고리즘으로, 한 번의 선택이 다음 선택에는 전혀 무관한 값이어야 하며 매 순간의 최적해가 문제에 대한 최적해여야 한다. ✅ 그리디 알고리즘을 적용하기 위한 조건 1️⃣ 탐욕적 선택 .. 4. 동적계획법 (Dynamic Programming) ✅ 동적 계획법이란? ㅇ 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하고, 다시 큰 문제를 해결할 때 사용하는 것. ㅇ 즉, 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘이다. ㅇ 동적 계획법은 다이나믹 프로그래밍(DP) 라고도 불린다. ✅ 동적 계획법의 조건 1️⃣ 최적 부분 구조 ㅇ 부분 문제의 최적 결과 값을 사용하여 전체 문제의 최적 결과를 낼 수 있는 경우. ㅇ 특정 문제의 정답은 문제의 크기에 상관없이 항상 동일하다는 특징이 있음. ㅇ 피보나치 수열의 점화식은 f(n) = f(n-1) + f(n-2)으로, 위와 같은 트리구조로 함수가 호출되게 된다. 위 그림에서도 쉽게 찾을 수 있듯이 fib(1), fib(2), fib(3)과 같이 동일한 부분 문제가 중복되어 .. 3. 이진탐색 알고리즘(binary_search) 이진 탐색(Binary_search) 이진 탐색이란 탐색의 범위를 절반씩 좁혀가며 데이터를 탐색하는 알고리즘이다. 입력 데이터가 많거나 탐색 범위의 크기가 매우 넓을 때 효과적으로 문제를 해결할 수 있다. 단, 오름차순으로 정렬되어 있는 리스트가 있어야 하며, 데이터가 무작위로 정렬되어 있다면 사용할 수 없다. 정렬된 데이터에서만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목푯값을 찾을 확률은 두배가 되므로 속도가 빠르다는 장점이 있다. 이진 탐색의 동작 과정 1. 시작 인덱스와 마지막 인덱스 사이의 중간 값을 중간 인덱스로 정한다. (이 때, 소수점 이하는 무시하고 중간 인덱스를 정한다.) 2. 중간 인덱스에 해당하는 데이터와 현재 찾으려는 데이터(타겟)이 같은지 비교한다. 3. 중간값이 .. 2. 복잡도(Time complexity) 알고리즘의 실행시간은 컴퓨터가 알고리즘 코드를 실행하는 속도에 의존한다. 이 속도는 컴퓨터의 처리속도, 사용된 언어 종류, 컴파일러의 속도에 달려있다. 알고리즘의 실행시간은 두 부분으로 나누어 볼 수 있다. ㅇ 입력값의 크기에 따라 알고리즘의 실행시간을 검증할 수 있다. ㅇ 입력값의 크기에 따른 함수의 증가량 - 중요하지 않은 상수와 계수들을 제거하면 알고리즘의 실행시간에서 중요한 성장률에 집중할 수 있는데 이것을 점금적 표기법(Asymptotic notation)이라고 부른다. - 점근적이라는 의미는 가장 큰 영향을 주는 항만 계산한다는 의미이다. 시간 복잡도 점근적 표기법을 알아보기 전에 시간복잡도라는 것이 무엇인지를 알아보자. 시간 복잡도는 문제를 해결하는 알고리즘의 성능을 표기하는 방법이다. 알고.. 1. 알고리즘이란? 알고리즘(Algorithm)이란? ㅇ 알고리즘의 의미 - 문제를 해결하기 위한 일련의 순서적인 계산/풀이 절차/방법으로, 컴퓨터 프로그램의 작성 시 기초가 된다. - 또한 요구되는 해로 이끄는 일련의 단계이지만, 이러한 절차/단계들이 보다 수학적으로 엄격하고 간결하게 다루어질 필요가 있다. ㅇ 알고리즘의 목적 - 궁극적으로 문제의 해결을 기계로 실행하기 위한 것 알고리즘의 특징 ㅇ 입력, 출력 - 입력은 없을 수도 있으나, 출력은 반드시 하나 이상 생성되어야 한다. ㅇ 유한성( Finiteness ) - 한정된 수의 작업 후에는, 반드시 유한 시간 내에 종료해야 한다. ㅇ 명확성( Definiteness ) - 각 단계는 단순 명확해야 하며, 모호하지 말아야 한다. ㅇ 유효성( Effectiveness .. 이전 1 다음
