[Day 37] [코딩 테스트 준비] Greedy, DP

학습 주제

 

Greedy 문제풀이
DP

 

---

 

새롭게 배운 내용

 

 

2022.07.28 - [Etc/Algorithm] - Implementation - Simulation, Brute-Force, Binary Search

Implementation - Simulation, Brute-Force, Binary Search

🍎 ++ 동적 프로그래밍 - DP를 활용한 피보나치 수열

 

🍎 알고리즘 내에서도, 평소에도 전역변수, 필드변수 사용 피하기
      필드: 클래스의 내부이면서 생성자와 메소드 밖에서 정의하는 것

🍎 copyOf(), indexOf() 등과 같은 메서드를 쓰면 내부적으로 반복이 존재해서 시간 복잡도에 영향을 준다

 

 

보강할 내용

 

자료구조 복습

 

 

회고

 

 

DP에서 메모이제이션은 작은 문제의 답을 저장해 두는 것을 말한다.

재귀를 공부할 때 정말 비효율적이겠다 생각은 했지만 이미 찾은 해답을 저장해 두는 방법이 있다는 게 신기했다. 재귀 함수의 대표적은 예시라고 할 수 있는 피보나치 수열에서도 배열을 생성하고 이미 계산을 거친 값은 저장해 두어서 필요할 때 접근하여 꺼내 쓰는 방법을 사용할 수 있다. 단 몇 줄만 추가해도 이렇게 효율을 높일 수 있다는 게 신기하고 재미있다.

나름의 공식이 있는데, 익숙한 개념이 아니어서 이해는 했어도 쉽게 받아들여져서 적용되지가 않는다. 주말에는 자료 구조에 대한 전체적인 복습과 알고리즘 문제에 많이 적용된다는 순열 + 조합에 대해서 다음 주 학습에 앞서 미리 공부해야겠다.

 

 

★★★★☆