알고리즘15 그리디 알고리즘(Greedy Algorithm) : 욕심쟁이 알고리즘 📌 그리디 알고리즘이란? 매 선택에서 지금 이 순간 당장 최적인 답을 선택하는 알고리즘 그러나 그리디 알고리즘은 전체에서 최적의 값을 언제나 구할 수는 없다. 예를 하나 들어보자 그리디 알고리즘(Greedy Algorithm)에서 경로를 선택할 때는 선택하는 순간의 최적 값을 찾는다. 그러니까 B, C, D를 선택하는 순간에서는 C 경로인 A, C, E를 고르게 된다. 그러나 실제 최단 경로는 A, D, E다. 이처럼 선택의 순간 그리디 알고리즘에 의해 최적의 값을 선택했지만 전체 선택에 대해서는 최적이 아닌 경로를 선택하게 된 꼴이다. 그리디 알고리즘은 경우의 수를 검증하는 백 트랙킹(Backtracking)을 하지 않기 때문에 전체 문제에서 항상 최적의 값을 구하지는 못한다. 📌 그리디 알고리즘을 사.. 2022. 7. 10. 동적 계획법(Dynamic Programming : 기억하며 풀기) -1 📌 동적 계획법(Dynamic Programming) 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법 동적이라는 말을 쉽게 말하자면 답을 재활용하는 것이다. 앞에서 구했던 답을 뒤에서도 이용하고, 옆에서도 이용하는 등 알고리즘이라기 보다는 문제를 해결하기 위한 하나의 방법론과 같다. 동적 계획법은 어떤 문제를 해결하기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는 방식의 알고리즘을 총칭한다. ❗️피보나치 수열을 예로 들어보자 피보나치 수열은 위와 같은 구조로 재귀 함수를 통해 구현된다. 즉, 값이 1인 fib(0)과 fib(1)을 제외하고 f(n) = f(n-1) + f(n-2)로 정의가 가능하다. 하지.. 2022. 7. 10. 버블 정렬(Bubble Sort) 주의 ! 이 내용은 글쓴이가 공부하기 위해 작성한 글로서 부정확할 수 있습니다. (반박시 니 말 다 맞음) 버블 정렬(또는 거품 정렬)은 인접한 두 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 O(N²)으로 상당히 느리지만 그만큼 코드 구현이 쉽다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보여 지어진 이름이라고 한다. 양방향으로 번갈아 수행하면 칵테일 정렬(?)이 된다고 한다. 아이디어 버블 정렬은 간단하다. 인접한 두 개의 원소를 비교하기만 하면된다. 한 턴이 지나면 맨 오른쪽은 가장 큰 값이 자리하게 된다. 예를 들자면 1 턴 97 64 34 59 72 첫번째와 두번째 비교 64 97 34 59 72 두번째와 세번째 비교 64 34 97 59 72 세번째와 네번째 비교 64 34 5.. 2022. 4. 5. 이전 1 2 3 4 다음
