[99클럽 코테 스터디] 📝 Day21. 동적계획법 (3)

99클럽 코테 스터디 21일차 TIL + 동적계획법 (3)

📍 오늘의 학습 키워드

동적 계획법 (Dynamic Programming)

📖 오늘의 회고

📚 어떤 문제가 있었고, 나는 어떤 시도를 했는지

오늘의 문제는 원형으로 배치된 집들에서 도둑이 훔칠 수 있는 돈의 최댓값을 구하는 것이었다. 첫 번째 집과 마지막 집이 연결되어 있어 인접한 두 집을 동시에 털 수 없는 제약 조건이 있었다. 이 문제를 해결하기 위해 동적 계획법을 사용하기로 했다.

🤔 어떻게 해결했는지

🔖 참고링크 (https://develop-tracking.tistory.com/90)

문제를 두 가지 경우로 나누어 해결했다

1. 첫 번째 집을 터는 경우.
2. 첫 번째 집을 털지 않는 경우. 각 경우에 대해 DP 배열을 정의하고 최댓값을 계산한 후, 두 결과를 비교하여 최종 답을 도출했다.

🤓 무엇을 새롭게 알았는지

동적 계획법을 사용할 때 문제를 부분 문제로 나누고, 각 부분 문제의 최적해를 기반으로 전체 문제의 최적해를 구하는 방법을 다시 확인했다. 특히, 원형 배열과 같은 문제에서는 처음과 끝이 연결되어 있어 문제를 두 가지 경우로 나누어 해결해야 한다는 점을 배웠다.

⏳ 내일 학습할 것은 무엇인지

내일은 다음 주제를 학습할 계획이다:

• 동적 계획법의 응용 문제 더 풀어보기
• 알고리즘 최적화 기법 (예: 메모이제이션)
• 다양한 문제 해결을 위한 알고리즘 패턴 익히기