TIL ~2022-02-24

1. 학습한 내용

백준 동적 프로그래밍 문제 11053번
문제 : https://www.acmicpc.net/problem/11053
내가 푼 코드 : https://github.com/MinYeongPark/Coding/blob/main/baekjoon/n11053/Main.java

2. 알게 된 내용

• 숫자가 일치할 때 dp의 값도 일치한다
  {10,20,10,30,20,50}이 있을 때 2번째의 20과 5번째의 20은 조금 다를 것이라 생각했었는데, 여러 사람들의 설명들을 읽어보면서 숫자가 일치하는 건 dp값도 일치한다는 것을 알게 되었다. 이 예제에서는 20보다 작은 것은 10밖에 없기 때문에, 20이라는 이 숫자들은 모두 dp[i]값이 2로 나올 수 밖에 없다!

• 이전 것들과 비교하는 것
  나 혼자만의 힘으로는 풀지 못했고, 여러 설명들과 코드를 참고하면서 이해하면서 갈피를 잡게 되었는데 아래의 코드처럼 i번째 이전의 수들과도 비교를 해서 현재 i번째 수가 어떤 우위(?)를 갖는지를 비교하는 점도 필요하다는 것을 알게 되었다.

for (int i = 1; i <= n; i++) {
    dp[i] = 1;      // 일단 1개는 부분수열에 들어가므로 1로 설정
    for (int j = 1; j < i; j++) { // i번째 수 이전의 수들을 고려해서 이 숫자보다 작은 게 있었는지 파악 필요
    	if (array[j] < array[i] && dp[i] <= dp[j]) // 숫자가 크고, 부분 수열의 수가 같거나 큰 게 있는지
        	dp[i] = dp[j] + 1;
    }
}

내 머리에서는 이 방법을 생각해낼 수 없었지만.. 이번 기회에 이런 방법으로도 구한다는 것을 알아간다!

설명 및 코드 참고한 사이트
https://developer-mac.tistory.com/71
https://st-lab.tistory.com/137

3. 느낀 점

내가 처음에 생각한 방법들은 틀린 방법이였고, 다른 분들의 설명을 이해하는 데까지도 많이 어렵게 느껴져서 조금 힘들었다. 그래도 매일 조금씩이라도 꼭 풀면서 익숙해지자!