[2주차_수요일] 2631_줄세우기

[baexxbin]

• 사이트: 백준
• 문제: 줄세우기
• 번호: 2631번

[baexxbin]

🤔 시간복잡도 고려사항

• 2 <= N <=200
• 완전탐색 가능
• 완전탐색 또는 DP 생각함

💡 풀이 아이디어

• 설계 1) 숫자 순서대로 옮기기 불가X

  • 모든 숫자 다 움직여 봐야함 → 최소 이동X 2) 최소로 움직이기 위해 최대한 연속되어있는 부분 살리기 → 최장부분증가수열 이용

• 구현

  • 최장부분증가수열
    • DP이용: O(N^2)
    • 이분탐색이용: O(NlogN) ✔︎
  • N-최장부분증가수열 길이

이분탐색 더 연습하기...

[Jewan1120]

🤔 시간복잡도 고려사항

• 제한이 넉넉해서 따로 신경쓰진 않았음

💡 풀이 아이디어

1. 아이끼리 스왑하는 것이 아니라 이동하는 것이기 때문에 움직여야 할 아이와 움직이지 않아도 되는 아이를 구분하는 게 핵심
2. 움직이지 않아도 되는 아이가 LIS(최장 증가 부분 수열)을 이루는 것을 보고 LIS의 길이를 구함
3. 전체 길이 - LIS의 길이 = 움직여야 할 아이의 수

   LIS 떠올리기 어렵슴다..

[yeongleej]

🤔 시간복잡도 고려사항

N<=200, 200 * 200

💡 풀이 아이디어

가장증가하는부분수열(LIS) 활용 LIS를 제외한 나머지를 옮겨주면 됨

(LIS를 떠올리는데 많은 시간이 걸렸습니다^O^ㅜㅜ)

[icegosimperson]

🤔 시간복잡도 고려사항

• 시간복잡도 : 2<= N <=200, O(N^2) 가능

💡 풀이 아이디어

• 처음에 pivot 값보다 크면, 비교값 오른쪽에 pivot값 넣고, swap한 뒤, pivot 값 변경하는 방식을 고려
• 이미 증가하는 순서를 최대한 유지하기 위해서는 단순 정렬X -> LIS
• 나머지 아이들이 이동해야할 수 : N - LIS

LIS 방식을 이해하는데 많은 시간이 걸렸습니다.

[KodaHye]

🤔 시간복잡도 고려사항

• DP(LCS)
  • 200 * 200

💡 풀이 아이디어

• 배열의 전체 길이 - 최대증가부분수열의 최대 길이
  • 최대증가부분수열을 구해서 움직이지 않아도 되는 수열의 최대 길이를 구함
  • 최대증가부분수열에 속하지 않는 나머지는 위치를 옮겨야 되는 원소

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: DP > 최장증가 부분수열(Longest Increasing Subsequence)
• 시간복잡도: 2 <= N <= 200 이므로 신경쓰지 않아도 됨

💡 풀이 아이디어

• 어떤 기준으로 정렬을 해야 하는지? 최소 이동 횟수는 이미 정렬된 수는 제외하고, 나머지 정렬 안된 수들만 움직이기
• 이미 정렬된 수는 제외하는 기준? 주어진 숫자들에서 오름차순으로 가장 길게 정렬된 수는 이동하지 않아도 됨
• 최장 오름차순 정렬 수 구하는 방법? 현재 값과 이전 값을 비교해서 이전 값이 더 작을 경우, 현재 정렬수(기본 1) +1 한다 (누적)