[코드트리 챌린지] 3주차 - DP

dev_Hyun·2023년 9월 20일

코드트리 코딩테스트 코딩테스트실력진단

코드트리 챌린지

목록 보기

3/8

0) 들어가기 앞서

지난 2주차에서는 NM 단계의 시뮬레이션2를 학습하여 dx, dy 를 활용한 방향전환 유형에 익숙해졌다.
이번 3주차는 NH 단계의 DP를 학습했다. 코드의 구현은 없었으나, 문제 유형을 익히고 점화식을 도출하는 과정을 학습하였다.

1) 실력 진단 결과

3주차 실력진단 결과는 697점으로 상승세를 유지하고 있다. 학습 진단 요약에 의하면 '그래프 탐색을 이용한 문제를 해결할 수 있지만 동적계획법 유형이 부족한 상황이에요' 라고 한다.

그래프 탐색을 아직 공부하지 못했는데 다른 유형이 부족하다고 하니, 계획을 수정해야 했다.

블로그 챌린지 기간동안에만 실력진단 결과에서 추천하는 커리큘럼을 따르겠다 결정했으니 이번 3주차는 DP유형을(넷플릭스 D.P. 아니고 DP 깔깔깔 🤣) 학습하기로 한다! 다만 NH 단계와 IL 단계 모두 DP와 그래프 탐색이 존재하는데, 보다 낮은 단계인 NH 먼저 학습해보자.

2) 3주차 학습 주요 내용

DP(Dynamic Programming, 동적계획법)

항상 점화식을 기반으로 한다. 어떤 풀이 방향을 선택하든 점화식을 구하는 것이 중요한 것 같다.

어느 유형이든 공통적이겠지만 특히 DP 유형은, 많은 DP 점화식을 경험해본 사람이 처음으로 맞닥뜨리는 사람보다 훨씬 유리하다고 생각이 든다.

풀이 방향

재귀함수 또는 for loop 를 사용해 구현할 수 있다.
재귀함수 만 사용할 경우 시간복잡도가 O(n^2) 이지만, 배열에 작은 문제의 답을 기록하는 Memoization 기법을 활용할 경우 시간복잡도 O(n) 가 된다. (개념 설명 : 코드 트리 링크)

작은 문제들의 해가 여럿 사용되는 유형

문제

타일채우기(2) (링크 : https://www.codetree.ai/missions/6/problems/dp-modeling-tile2?&utm_source=clipboard&utm_medium=text)

리뷰

바로 직전의 작은 해 만 고려하는 것이 아니라 현재의 문제가 몇 개의 작은 해와 얽혀 있는지 파악할 필요가 있었다.
타일채우기(2) 와 유사한 문제로 BST 개수(이진탐색트리 개수) 문제가 있다.

아이템 적절히 고르기

주어진 아이템을 적절히 골라, 목표로 하는 값에 도달할 수 있는 경우의 수를 찾는 유형이다. 대표적으로 배낭문제가 이 유형에 포함된다.

문제

은행 (링크 : https://www.codetree.ai/missions/6/problems/dp-modeling-bank?&utm_source=clipboard&utm_medium=text)

리뷰

공통적으로 다음 두 가지 고려사항이 존재한다고 이해했다.
1. DP table 으로 구하고자 하는 것이 최소/최대 중 무엇인가?
2. 몇 번째 아이템 까지 고려하였는가?
  - n번째 아이템이 마지막 아이템에 포함되는 경우와 마지막 아이템에 포함되지 않는 경우를 비교하여 최소/최대 값을 DP table에 저장한다.

LCS(Longest Common Subsequence)

LCS 약자는 두 가지 의미(최장 공통 부분수 열, 최장 공통 부분 문자열)가 있을 수 있는데, 이번 유형은 최장 공통 부분 수열이다.

부분 문자열일 경우 한 번에 이어져 있는 문자열만 가능하지만, 부분 수열일 경우 문자와 문자 사이를 건너뛰며 공통되는 부분 문자열을 구하면 된다.
다음 포스팅이 해당 개념을 이해하는데 큰 도움이 되었다. 참고 링크 : (https://velog.io/@emplam27/알고리즘-그림으로-알아보는-LCS-알고리즘-Longest-Common-Substring와-Longest-Common-Subsequence)

문제