[4주차_수요일] 7570_줄세우기

[yeahdy]

• 사이트 : 백준(BOJ)
• 문제: 줄세우기
• 번호: 7570

[baexxbin]

🤔 시간복잡도 고려사항

• 1<= 어린이 <= 1,000,000 (10^6)
• O(NlogN)이내로 풀기

💡 풀이 아이디어

• 처음엔 이분탐색을 통한 LIS를 이용했으나 실패

  • 해당 방법은 연속여부 상관없이 증가하는 수열을 찾음

    어제 문제 착각하고 이문제 이분탐색으로 먼저 풀다 실패..ㅎㅎ

• 이 문제에서는 연속된 증가 수열을 찾아야함

  • 어린이 맨앞, 맨뒤 이동만 가능함, 중간에 못끼워넣음
  • 예제를 보면 연속된 증가수열(2,3)제외하고 움직임

• 점화식: dp[i] = dp[i-1]+1

  • i를 마지막으로 하는 연속된 증가수열의 길이, (이전 dp값+1)
  • 최종적으로 N-mx(최장 연속 부분 수열)

[icegosimperson]

🤔 시간복잡도 고려사항 시간복잡도 : O(N) N <= 10^6 -> O(N^2) 불가

💡 풀이 아이디어 어린이들 최소한 이동 후 오름차순 정렬 -> LIS(최장 증가 부분 수열) 이동해야하는 어린이 수 = 전체 어린이 수 - LIS

cnt : 연속된 증가 수열 길이

        // 연속된 증가 수열의 길이 계산
        for (int i = 1; i <= N; i++) {
            if (arr[i] > arr[i - 1]) {  // 현재 위치의 값이 이전 위치의 값보다 크다면 (=연속된 수열)
                cnt++;  // 연속된 수열의 길이 증가
                LIS = Math.max(LIS, cnt);  // 최장 길이 LIS 갱신
            } else { // 연속되지 않으면
                cnt = 1;  // 길이 1로 초기화
            }
        }

[Jewan1120]

🤔 시간복잡도 고려사항

• 1 ≤ n ≤ 1,000,000 → 10^6 이므로 O(n logn)이하의 연산

💡 풀이 아이디어

• 움직이지 않아도 되는 아이들의 수들 중 최댓값을 구하는 문제
• 최장 증가 수열 중 연속하는 증가 수열이어야 함
• 순차적으로 탐색하면서 해당 값 -1의 인덱스에서 1을 증가시키면서 최댓값을 찾아 줌

[KodaHye]

🤔 시간복잡도 고려사항

• 1 <= 어린이 수 <= 1,000,000이므로 완전 탐색을 통한 방법은 안됨
• 우선순위 큐 써도 안됨
  • 우선순위를 써서 풀이했을 때 최악의 경우 → O(NlogN * N)
• DP를 통한 풀이 방법: O(N)에 해결 가능

💡 풀이 아이디어

• 전체 길이 - 연속해서 증가하는 부분수열의 최대 길이
• dp[num] = dp[num - 1] != 0 ? dp[num - 1] + 1: 1;

나중에 보니 dp[num] = dp[num - 1] != 0 ? dp[num - 1] + 1: 1;과 dp[num] = dp[num - 1]가 똑같은 식인데, 제가 필요없는 연산을 했다는 것을 알았습니다 ㅜ

[yeongleej]

🤔 시간복잡도 고려사항

• N <= 1,000,000 : O(N) 방법을 생각해야 함

💡 풀이 아이디어

• 순서를 바꾸는 위치가 맨앞과 맨뒤로 고정되어 있으므로 연속으로 증가하는 최장 부분 수열을 구해야 함
• dp활용
  • dp[num] : num까지 탐색했을 때 연속 증가 부분 수열의 길이
  • dp[num- 1]이 0이면, 연속된 수열이 없으므로 dp[num] = 1
  • 그렇지 않으면, 연속 수열길이 증가 dp[num] = dp[num-1]+1

처음에는 저번주에 풀었던 줄세우기(BOJ_2631)와 같은 문제라고 생각했지만, 이 문제는 단순히 증가하는 부분 수열이 아니라 연속으로 증가하는 최장 부분 수열의 길이를 구해야 하는 문제임을 꺠달았습니다,,,,, ㅎㅎㅎ DP도 더 연습해야할 것 같습니다~ ㅜㅜㅜㅜ

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: DP 최장증가부분수열
• 시간복잡도: 1<=어린이 수<=1,000,000 10^6 으로 단순 이중 반복문으로 풀 경우 시간초과 발생

💡 풀이 아이디어

• LIS의 의미: 해당 길이 만큼은 정렬이 되어 있기 때문에 고정하고 나머지 요소들만 이동 시키면 됨.
• 띄엄띄엄? 최장 증가 부분 수열로 풀 경우 맨앞, 맨뒤 위치가 아닌 요소도 이동이 가능하기 때문에 불가능
• 최장 증가 부분 수열에서 연속으로 증가할 때의 가장 긴 구간을 찾아야 함

dp 점화식을 세우는 부분이 이해가 안가서 점화식 사용안한 블로그 참고했어요💦💦💦💦

연속되는 최장증가수열을 찾는이유? 일반적인 최장증가수열의 경우 요소들이 사이에 들어올 수 있는데, 연속되는 최장증가수열의 경우 해당 길이만큼 연속되게 있기 때문에 중간에 요소들이 들어올 수 없음! 따라서 요소들이 맨앞 맨뒤 위치로만 이동하는 것