오름차순으로 만드는 최소 횟수

문제 링크

난이도

  • 골드 5
    • dp의 특성상 푸는 코드는 짧았다.
  • 코드트리에서 릴레이 하다가 푼 재밌는 문제
    • 근데 어떻게 풀어야 하는지가 고민해야 했다.
    • LIS를 구현해야 했는데 그게 어려웠다.

문제 요약

  • n 까지의 숫자가 중복 없이 존재
  • 정렬 되지 않은 상태
  • 오름차순으로 만들기 위해 최소 이동 횟수를 구하라.
    • 이동은 위치 교환이 아닌, 삽입 정렬처럼 해당 위치로 꽂아 넣는 형태이다.

접근

  1. 왼쪽부터 순서대로 오름차순을 만든다.
  • 가장 간단한 방법으로 생각.
  • 문제점은 1237456이면?
    • 중간의 7때문에 456을 전부 왼쪽으로 넘기느라 이동 횟수가 추가된다.
  • 그럼 7을 오른쪽으로 옮기면 되지 않나?
    • 그걸 어떻게 판단하지?
  1. LIS(최장 부분 증가 수열)를 이용하기
  • 이동은 무조건 이뤄진다. 이를 최소화 해야한다.
  • 이동은 특정 위치와 교환이 아닌, 삽입 정렬처럼 꽂아 넣는방식이 핵심
  • 그럼 오름차순으로 이뤄진 숫자를 제외하고 이동시키면 된다.
    • 이를 최장 부분 증가 수열(LIS) 이라 한다.
  • 이 LIS가 가장 긴 길이를 찾아 n에서 빼면 그게 이동횟수가 된다.

간단 알고리즘

  • LIS를 찾는 알고리즘
    • 핵심은 오름차순으로 부분적으로 증가하는것을 찾는거.
    • 현위치를 기준으로 왼쪽것들중 작은것의 갯수를 세면 된다.
      • 그냥 세면 안되고! 점차 증가하는것만 세면 된다.
      • dp의 정의를 잘 하면 된다.

  • dp

    • dp[i]는 i이하 까지의 LIS를 저장
    • 초기는 1로 초기화
  • i를 0부터 n까지 반복
    • j는 0부터 i-1까지 반복
      • data[j] < data[i]로 왼쪽에서 나보다 낮은 LIS를 찾는다.
        • dp[i] < dp[j]+1로 기존에 갱신된 LIS보다 높을때만 갱신한다.
          • dp[i] = dp[j]+1로 갱신한다.

후기

  • LIS를 구현하는게 어려운 문제였다.
    • 오른쪽을 확인해야 할지, 왼쪽을 확인 해야 할지
    • 적당한 설계를 하기 고민했다.
  • dp의 특성상 코드는 짧았다.