코딩인터뷰 퀘스천"메모" 탐욕,분할정복 알고리즘, 동적 계획법, 복잡도 클래스

.

.

책 읽으면서 메모했던 내용들 옮겨봅니다.

​

-

챕터17 탐욕 알고리즘

체스 게임에서 의사 결정은 향후의 수에 대해서도 고려. 반면 테니스는 그 순간 최선이라고 생각하는 현재 상태를 기반으로 행동. Greedy Strategy 는 테니스에 적합.

​

직관적이고 간단하며 이해하기 쉽고 코드화가 용이함.

지역적 최선이 전체 문제의 해라는 보장이 없다.

​

응용 : 선택정렬, 위상정렬. 힙 정렬. 허프만 부호화 압축 알고리즘. 동전 교환 문제. 환전. 작업 스케쥴 알고리즘.

​

챕터18 분할 정복 알고리즘

탐욕 전략으로 해결되지 않는 문제들 주 몇몇은 Divide & Conquer 로 해결 가능. 재귀 기반, 문제를 직접 해결할 수 있을 정도로 간단한 문제가 될 때까지 동일한 유형인 둘 이상의 하위 문제로 나눔. 이런 하위 문제를 재귀적으로 처리. (간단한 문제란, 입력의 크기 n의 값이 원래 문제보다 작은 것)

​

어려운 문제를 해결하는 강력한 방법. 처리가 느리다는 단점. 반복적인 접근 방식보다 더 복잡해질 수 있다.

​

응용 : 이진 검색, 병합 정렬, 퀵 정렬, 중간값 찾기, 최소 최대값 찾기, 행렬 곱셈, 최근접쌍 문제

​

챕터19 동적 계획법

Dynamic Programming, DP 는 간단한 기술이지만 완전히 익히는 것은 어렵. 분할 정복과의 큰 차이점은, 분할 정복은 하위 문제들이 독립적이지만 DP는 하위 문제들 간의 중첩이 일어남. 메모이제이션.

이미 해결한 하위 문제들을 테이블에 보관.

동적 계획법 = 재귀 + 메모이제이션

​

챕터20 복잡도 클래스

컴퓨터 과학에서 해결되지 않은 문제를 이해하기 위해 문제들을 그룹핑하여 나눈 것.

복잡도 이론에서 복잡도 클래스는 복잡도와 관련된 문제들의 집합.

이런 문제를 해결하기 위해 계산에 필요한 자원을 연구하는 계산 이론의 한 분야.

---

내용이 많고 어려워서 대략적인 개요부분만 메모했습니다.

.

.

.