99클럽 코테 스터디 21일차 TIL + 동적계획법 (3)
📍 오늘의 학습 키워드
동적 계획법 (Dynamic Programming)
📖 오늘의 회고
📚 어떤 문제가 있었고, 나는 어떤 시도를 했는지
오늘의 문제는 원형으로 배치된 집들에서 도둑이 훔칠 수 있는 돈의 최댓값을 구하는 것이었다. 첫 번째 집과 마지막 집이 연결되어 있어 인접한 두 집을 동시에 털 수 없는 제약 조건이 있었다. 이 문제를 해결하기 위해 동적 계획법을 사용하기로 했다.
🤔 어떻게 해결했는지
🔖 참고링크 (https://develop-tracking.tistory.com/90)
문제를 두 가지 경우로 나누어 해결했다
- 첫 번째 집을 터는 경우.
- 첫 번째 집을 털지 않는 경우. 각 경우에 대해 DP 배열을 정의하고 최댓값을 계산한 후, 두 결과를 비교하여 최종 답을 도출했다.
🤓 무엇을 새롭게 알았는지
동적 계획법을 사용할 때 문제를 부분 문제로 나누고, 각 부분 문제의 최적해를 기반으로 전체 문제의 최적해를 구하는 방법을 다시 확인했다. 특히, 원형 배열과 같은 문제에서는 처음과 끝이 연결되어 있어 문제를 두 가지 경우로 나누어 해결해야 한다는 점을 배웠다.
⏳ 내일 학습할 것은 무엇인지
내일은 다음 주제를 학습할 계획이다:
- 동적 계획법의 응용 문제 더 풀어보기
- 알고리즘 최적화 기법 (예: 메모이제이션)
- 다양한 문제 해결을 위한 알고리즘 패턴 익히기
'Algorithm > Study' 카테고리의 다른 글
[99클럽 코테 스터디] 📝 Day23. 이진탐색 2 (0) | 2024.06.11 |
---|---|
[99클럽 코테 스터디] 📝 Day22. 이분탐색 (0) | 2024.06.10 |
[99클럽 코테 스터디] 📝 Day20. 동적계획법 (2) (0) | 2024.06.09 |
[99클럽 코테 스터디] 📝 Day19. 동적 프로그래밍 (DP) 2 (0) | 2024.06.09 |
[99클럽 코테 스터디] 📝 Day18. 동적 프로그래밍 (DP) (0) | 2024.06.09 |