[Algorithm] ๐๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด
0. ๋ฌธ์
์์ด A๊ฐ ์ฃผ์ด์ก์ ๋, ๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์๋ฅผ ๋ค์ด, ์์ด A = {10, 20, 10, 30, 20, 50} ์ธ ๊ฒฝ์ฐ์ ๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด์ A = {10, 20, 10, 30, 20, 50} ์ด๊ณ , ๊ธธ์ด๋ 4์ด๋ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ์์ด A์ ํฌ๊ธฐ N (1 โค N โค 1,000)์ด ์ฃผ์ด์ง๋ค.
๋์งธ ์ค์๋ ์์ด A๋ฅผ ์ด๋ฃจ๊ณ ์๋ Ai๊ฐ ์ฃผ์ด์ง๋ค. (1 โค Ai โค 1,000)
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ์์ด A์ ๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด์ ๊ธธ์ด๋ฅผ ์ถ๋ ฅํ๋ค.
1. ์์ด๋์ด
์ด์ ์ list๊ฐ๋ณด๋ค ์ปค์ผํจ
์ด์ ์ dp๊ฐ์ด ํ์ฌ dp๊ฐ๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ์์ผํจ
2. ํต์ฌ ํ์ด
1) ์ด์ ์ list๊ฐ๋ณด๋ค ์ปค์ผํจ && ์ด์ ์ dp๊ฐ์ด ํ์ฌ dp๊ฐ๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ์์ผํจ
if(lis[j]<lis[i] && dp[i] <= dp[j])
dp[i] = dp[j] + 1;
3. ์ฝ๋
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class DP_EX_4 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int max = -1;
int n = Integer.parseInt(br.readLine());
String s[] = br.readLine().split(" ");
int lis[] = new int[n];
int dp[] = new int[n];
for(int i=0; i<n; i++)
lis[i] = Integer.parseInt(s[i]);
for(int i=0; i<n; i++) {
dp[i] = 1;
for(int j=0; j<i; j++) {
if(lis[j]<lis[i] && dp[i] <= dp[j])
dp[i] = dp[j] + 1;
}
}
for(int i=0; i<n; i++)
max = Math.max(max, dp[i]);
System.out.println(max);
}
}
4. ๊ฒฐ๊ณผ
์ฑ๊ณต!
Author And Source
์ด ๋ฌธ์ ์ ๊ดํ์ฌ([Algorithm] ๐๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด), ์ฐ๋ฆฌ๋ ์ด๊ณณ์์ ๋ ๋ง์ ์๋ฃ๋ฅผ ๋ฐ๊ฒฌํ๊ณ ๋งํฌ๋ฅผ ํด๋ฆญํ์ฌ ๋ณด์๋ค https://velog.io/@kha0318/Algorithm-๊ฐ์ฅ-๊ธด-์ฆ๊ฐํ๋-๋ถ๋ถ-์์ด์ ์ ๊ท์: ์์์ ์ ๋ณด๊ฐ ์์์ URL์ ํฌํจ๋์ด ์์ผ๋ฉฐ ์ ์๊ถ์ ์์์ ์์ ์ ๋๋ค.
์ฐ์ํ ๊ฐ๋ฐ์ ์ฝํ ์ธ ๋ฐ๊ฒฌ์ ์ ๋ (Collection and Share based on the CC Protocol.)
์ข์ ์นํ์ด์ง ์ฆ๊ฒจ์ฐพ๊ธฐ
๊ฐ๋ฐ์ ์ฐ์ ์ฌ์ดํธ ์์ง
๊ฐ๋ฐ์๊ฐ ์์์ผ ํ ํ์ ์ฌ์ดํธ 100์ ์ถ์ฒ ์ฐ๋ฆฌ๋ ๋น์ ์ ์ํด 100๊ฐ์ ์์ฃผ ์ฌ์ฉํ๋ ๊ฐ๋ฐ์ ํ์ต ์ฌ์ดํธ๋ฅผ ์ ๋ฆฌํ์ต๋๋ค