[Algorithm]그리디(Greedy) 알고리즘, 분할 정복, 다이나믹 프로그래밍 이란? 비교 및 분석하기 - 알고리즘 문제를 풀기전에 알아야 하는 개념(배낭 문제, 동전 바꾸기, 피보나치 수열 등)
그리디 알고리즘 그리디 알고리즘이란 바로 눈앞의 이익만을 좇는 알고리즘을 말한다. 그리디 알고리즘은 최적화 문제를 대상으로 한다. 최적해를 찾을 수 있으면 그것을 목표로 삼고, 찾기 어려운 경우에는 주어진 시간 내에 그런대로 괜찮은 해를 찾는 것을 목표로 삼는다. 그리디 알고리즘이 잘 작동하는 문제들은 탐욕 선택 속성을 갖고 있는 최적 부분 구조인 문제들이다. 여기서 탐욕 선택 속성이란 앞의 선택이 이후 선택에 영향을 주지 않는 것을 말한다. 다시 말해 그리디 알고리즘은 선택을 다시 고려하지 않는다. 또한 최적 부분 구조란 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우를 말한다. 이렇게 탐욕 선택 속성과 최적 부분 구조의 2가지 조건을 만족하면 최적해를 찾을 수 있다. 하지..
문제 연결 리스트를 O(n*logn)에 정렬하라. 입력 4 → 2 → 1 → 3 출력 1 → 2 → 3 → 4 코드 병합 정렬 class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next class Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: if l1 and l2: if l1.val > l2.val: l1, l2 = l2, l1 l1.next = self.mergeTwoLists(l1.next, l2) return l1 or l2 def sortList(self, head: ListNode) -> ListNode: if n..