[백준] DP (골드4 이하) 코멘트 모음

그리디와 쌍두마차로 씽크빅 문제라고 생각한다.

 

그래도 개인적으로 그리디보다는 문제를 많이 풀면 쉬워진다는 느낌은 드는 편인다.

 

⭕️15681번 : 트리와 쿼리 (골드5)

• 문제 유형 : dp, tree
• 시간 복잡도 : O(n)
• 풀이 방식 :

- ArrayList를 이용해서 트리를 저장
- 방문한 정점 체크용 visit배열 이용
- 리프노드부터 루트 노드로 올라오며 각 서브트리별 정점의 갯수를 dp배열에 저장

 

❌ 9251번 : LCS (골드5)*

• 문제 유형 : dp, String
• 시간 복잡도 : O(nm)
• 풀이 방식 :

- 두 문자열의 위치를 나타내는 2차원 int 배열 dp 선언(0으로 초기화, 인덱스는 i, j로 표현)
- 각 문자열의 현재 문자가 같을 경우 dp[i][j] = dp[i-1][j-1]
- 다를 경우 dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) -> 현재까지 구한 LCS의 길이를 뜻함
- dp의 마지막 값이 LCS의 길이를 뜻함

 

⭕️ 9252번 : LCS2 (골드4)

• 문제 유형 : dp, String
• 시간 복잡도 : O(nm)
• 풀이 방식 :

- 9251번과 같은 방식으로 dp 배열을 구하고 마지막 값부터 시작하여 dp[i-1][j]와 dp[i][j-1] 중 dp[i][j]가 같은 값이 존재할 경우 해당 위치로 이동
- 같은 값이 없을 경우 해당 위치의 문자를 Stack에 추가 후 dp[i-1][j-1]로 이동 -> 해당 dp의 위치가 두 문자열에서 현재 문자를 찾은 순간이기 때문에 현재 문자를 stack에 추가하고 현재 문자 전 위치의 dp로 이동

 

❌ 11053번 : 가장 긴 증가하는 부분 수열 (실버2)*

• 문제 유형 : dp
• 시간 복잡도 : O(n^2)
• 풀이 방식 :

- 일차원 dp배열을 이용
- 수열의 현재 값 보다 앞선 작은 값 중 dp에 저장되어있는 부분 수열의 크기가 가장 큰 수열의 크기 택해 1 증가된 값을 dp의 현재 값에 저장

 

⭕️ 11053번 : 공통 부분 문자열 (골드5)

• 문제 유형 : dp, string
• 시간 복잡도 : O(nm)
• 풀이 방식 :

- 2차원 dp배열을 이용
- 두 문자열을 순서대로 비교하여 같은 문자(i, j에 위치)가 발견되면 해당 문자의 각 문자열 이전 문자(i-1, j-1)의 dp값에 1을 더한값을 현재 dp값으로 함
- dp배열에 저장되어 있는 값 중 가장 큰 값을 출력

 

⭕️ 14002번 : 가장 긴 증가하는 부분 수열4 (골드4)

• 문제 유형 : dp
• 시간 복잡도 : O(n^2)
• 풀이 방식 :

- 일차원 dp배열을 이용
- 부분 수열의 각 값에 선행 값을 저장하는 prev배열 이용
- 수열의 현재 값 보다 앞선 작은 값 중 dp에 저장되어있는 부분 수열의 크기가 가장 큰 수열의 크기 택해 1 증가된 값을 dp의 현재 값에 저장하고, prev 배열에 선행 값 저장
- 선행 값을 따라가다보면 역순으로 나열되기 때문에 stack에 저장후 값을 모두 빼내어 출력

 

❌ 11054번 : 줄 세우기 (골드4)*

• 문제 유형 : dp
• 시간 복잡도 : O(n^2)
• 풀이 방식 :

- 증가하는 순서로 서있는 애들을 제외한 나머지 어린이의 위치를 옮기면 최소 횟수로 줄을 세울 수 있기 때문에 가장 긴 증가하는 부분 수열(LCS)를 이용
- LCS를 구해서 총 어린이 수에서 빼면 위치를 옮겨야되는 최소 어린이 수를 구할 수 있다

 

❌ 10942번 : 팰린드롬? (골드4)*

• 문제 유형 : dp
• 시간 복잡도 : O(n^2)
• 풀이 방식 :

- 2차원 dp 배열을 이용하며 dp[i][j]는 문자열 i부터 j까지 펠린드롬인지 아닌지를 나타냄
- dp[i][j]에서 dp[i+1][j-1](대각선 왼쪽아래방향)은 문자열 i+1부터 j-1까지 펠린드롬 판정을 의미하기 때문에 i번째 문자와 j번째 문자가 같고, dp[i+1][j-1]이 펠린드롬(1)일 경우(문자열에서 i+1 ~ j-1까지) i부터 j까지 문자열도 펠린드롬이 되기 때문에 점화식을 짤 수 있음
- 단 인접한 두 개의 문자끼리 비교할 때는 dp[i+1][j-1]의 값이 존재하지 않고, 두 문자만 같으면 무조건 펠린드롬이기 때문에 따로 조건문으로 관리
- 원하는 범위(i, j)에서 dp[i][j]가 1이면 펠린드롬이므로 1 출력, 0이면 펠린드롬이 아니기 때문에 0 출력

10942번 : 자두 나무 (골드5)

• 문제 유형 : dp
• 시간 복잡도 : O(n^2m)
• 풀이 방식 :

- 2차원 dp배열 이용
- 이동 횟수별 주울 수 있는 최대 개수를 구하기 위해 자두가 들어올 때마다 방향을 구분하여 dp배열 값을 바꿔야 함
- 시작을 왼쪽에서 하기 때문에 왼쪽에 서 있는 경우의 이동 횟수는 무조건 짝수, 오른쪽에 서 있는 경우의 이동 횟수는 무조건 홀수
- 자두가 왼쪽으로 떨어질 경우 현재 이동 횟수-1번 이동하고 오른쪽에 서 있는 경우의 dp 값+1과 현재 이동 횟수(왼쪽)+1의 값을 비교(0번 이동했을 때의 자두 개수는 무조건 +1개)
- 오른쪽에서 떨어질 경우는 위와 반대(0번 이동은 존재하지 않음)
- dp배열 값 중 가장 큰 값

 

❌ 2293번 : 동전 1 (골드5)*

• 문제 유형 : dp
• 시간 복잡도 : O(n^2)
• 풀이 방식 :

- 메모리 제한이 4mb 밖에 되지 않기 때문에 일차원 dp배열을 사용해야 함
- 동전들의 조합으로 돈의 액수를 맞출 수 있는 경우의 수를 따져야하기 때문에 작은 단위로만 가능한 경우 + 현재 단위와 더 작은 단위의 조합으로 가능한 경우를 구해줘야 함 (dp[i] = dp[i] + dp[i-coin])
- 단위가 작은 동전부터 dp를 덧붙여 채워넣으면서 가장 큰 단위의 동전까지 완료한 후 dp[k]에 있는 값이 정답

 

⭕️ 5721번 : 사탕 줍기 대회 (골드4)

• 문제 유형 : dp
• 시간 복잡도 : O(nm)
• 풀이 방식 :

- 2차원 dp 배열을 이용
- dp의 각 행의 인덱스 1의 값을 해당 위치의 사탕 수로 초기화(나머지는 0)
- 각 행마다 왼쪽 끝에서 오른쪽 끝으로 진행하며 현재 위치(i)를 선택하지 않았을 때의 최대값(i-1)과 현재 위치를 선택하고 왼쪽으로 2칸까지의 최대값(i-2) + 현재 위치 사탕 개수를 비교하는 방식으로 dp배열을 채움
- 각 행의 오른쪽 끝 값에는 행을 선택 했을 때 얻을 수 있는 사탕의 최대 개수가 적혀있기 때문에 맨 오른쪽 열에서 위부터 내려가며 위의 과정을 진행
- 위의 과정이 끝나면 dp배열에서 가장 오른쪽 아래값에 사탕 줍기 대회에서 주을 수 있는 최대 사탕 개수가 저장되어