728x90 개발3 [WEEK04] 알고리즘_그리디(Greedy) 알고리즘 [WEEK04] 알고리즘_그리디(Greedy) 알고리즘 당장 눈 앞에 보이는 최적의 상황만을 쫓는 알고리즘 난이도가 매우 낮은 알고리즘 중 하나이다. 항상 최적의 결과를 도출하는 것은 아니지만 어느정도 빠르게 구할 수 있으며 특정한 상황에서는 그리디 알고리즘이 최적의 해를 구할 수 있게 해준다. 예를 들면 거스름 돈 문제이다. 무조건 더 큰 화폐 단위부터 거슬러 주는 것이 최적의 해를 제공한다. 즉, 무조건 큰 경우, 작은 경우, 긴 경우, 짧은 경우 등 극단적으로 문제에 접근한다는 점에서 정렬(Sort) 기법이 함께 사용되는 경우가 많다. 사실 뭔가 특별한 테크닉이 아니라 그냥 특정 경우에 평소 풀던대로 풀면 되는 듯 하다.. 유튜브 - 동빈나 그리디(Greedy) 알고리즘 [ 실전 알고리즘 강좌(Al.. 2021. 8. 30. [WEEK04] 알고리즘_다이나믹 프로그래밍(DP) [WEEK04] 알고리즘_다이나믹 프로그래밍(DP) 다이나믹 프로그래밍 특징 하나의 문제는 단 한 번만 풀도록 하는 알고리즘 메모이제이션(Memoization, 이미 계산한 결과는 배열에 저장함. Memorization이 아님)을 통해 동일 계산시 저장된 값을 단순히 반환하여 시간을 줄임 -> 메모리를 적절히 사용하여 수행 시간을 굉장히 단축시킨다. 일반적으로 탑다운(하향식, 재귀함수 이용), 바텀업(상향식) 두가지 방식으로 구현한다. 보통 바텀업이 전형적인 형태이다. 다이나믹 프로그래밍 사용 조건 최적 부분 구조(Optimal Substructure) - 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 통해 큰 문제를 해결 가능한 구조 중복 부분 문제(Overlapping Subproblem.. 2021. 8. 27. [WEEK01] 8/15 TIL_힙 정렬 [WEEK01] 8/15 TIL_힙 정렬 선택 정렬을 응용한 알고리즘인 힙 정렬을 알아보겠다. 힙 정렬은 힙의 특성을 이용하여 정렬하는 알고리즘이다. 힙은 부모의 값이 자식의 값보다 항상 크다는 조건을 만족하는 완전 이진트리이다. 선택 정렬 먼저 힙 정렬에 알아보기 전에 선택 정렬을 알아보자. 선택 정렬은 '가장 작은 원소부터 정렬하는 방법'이다. 힙 정렬 - 특성 힙(heap) 정렬은 힙의 특성을 이용하여 정렬하는 알고리즘이다. 힙은 '부모의 값이 자식의 값보다 항상 크다'는 조건을 만족하는 완전 이진 트리이다. 이때 부모의 값이 자식의 값보다 항상 작아도 힙이라고 한다. 힙(heap)은 쌓아 놓음을 의미한다. 트리의 가장 윗부분에 위치한 노드를 루트(root)라고 하고 가장 하래에 위치한 노드를 리프.. 2021. 8. 15. 이전 1 다음 728x90
