Greedy(18)_반도체설계(2352)

작성일 | In

BJO 2352 반도체 설계

n개의 포트를 다른 n개의 포트와 연결해야 할 때가 있다. 연결선이 꼬이지 않게 최대 몇개를 연결 할 수 있는지 프로그램 작성

입력값 : 첫째 줄에 최대 연결 개수 다음 줄에 차례로 1번 포트와 연결이 되어야 하는 포트번호~ 쭉 등장.

단순히 떠오르는 생각

4 2 6 3 1 5 예제를 보면 4는 4,6 2개 2는 2,3,5 3개 6은 4,6 2개 3은 2,3,5 3개 1은 1,5 2개 5는 2,3,5 3개.

즉 자신을 포함한 자기보다 큰 수가 오른쪽에 몇개 있나 세보면 되지 않을까?

코드

import sys
T = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))

max = 0
for i in range(T):
    count = 1
    for j in range(1, T-i):
        if arr[i] < arr[j]:
            count += 1
    if(max < count):
        max = count
print(max)

-> 시간초과.

LIS

질문 검색에 시간초과를 클릭해보니, 이 블로그를 참조하래서, 이 블로그를 참조한다 이런 문제를 흔히 LIS라고 하나보다. BinarySearch + dp를 이용하여 풀어야 한다고 한다.

[LIS(Longest Increasing Subsequence)]https://dyngina.tistory.com/16 LIS: 최대 부분 증가 수열이다. 단순히 예를 들어 10, 20, 40, 30, 70, 50, 60 이라는 수열이 있을 대, 10 20 30 50 60 . 즉 앞에서 뒤로 숫자를 선택해 나갈 때, 증가하는 순서대로 고를 때, 최대 길이를 갖는 수열이라고 할 수 있다. 여기서는 길이가 5인 LIS를 갖겠다.

유일한 예제는 아니다. 10 20 40 50 60 도 답이 되기 때문이다.

N^2는 누구나 코딩 가능할 정도로 단순하다.

방법은 두 가지가 있다. 간단하지만 역추적이 불가능한 LowerBound를 이용한 방법이 있고, 역추적이 가능한 Index Tree 방법이 있다.

(LowerBound =이진 탐색 기반의 탐색방법)을 이용하겠다.

리스트를 하나 생성한 뒤, LNF(나올 수 없는 가장 작은 값)을 삽입해준다. 이후 매번 수열을 볼 때마다, 리스트의 맨 뒤 원소와 현재 보고있는 수열의 원소를 비교하여, 수열의 원소가 더 클시 리스트에 push 해주고, LIS를 1 증가시켜준다.

수열의 원소가 리스트의 맨 뒤 원소보다 작을 경우, lower_bound를 이용하여, 최적의 자리를 찾은 뒤. 그 자리의 값을 해당 수열의 원소로 교체해버린다.

파이썬 bisect 알고리즘

직접 반복문을 만들어 이진 탐색 알고리즘을 구현하면 다음과 같다.

def bisect(a, x, lo=0, hi=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo

mylist = [1, 2, 3, 7, 9, 11, 33]
print(bisect(mylist, 3))

여기서 python의 bisect.bisect method를 사용하면 이 코드를 간략하게 만들 수 있다.

import bisect
mylist = [1, 2, 3, 7, 9, 11, 33]
print(bisect.bisect(mylist, 3))

풀이코드

  1. 맨 처음 값부터 하나하나 입력 받는다
  2. 입력받은 값이 벡터 안에 있는 값들 보다 크면 벡터의 맨 뒤에 넣는다.
  3. 벡터의 처음부터 검색했을 때, 입력 받은 값보다 큰 값이 있다면, 그 값과 교체한다.
  4. 벡터의 원소 갯수를 출력한다.

코드

import sys
import bisect

DP = []


def LIS(start, end, target):
    while(start < end):
        mid = (start+end)//2
        if DP[mid] > target:
            end = mid
        elif DP[mid] < target:
            start = mid + 1
        else:
            return -1
    return end


if __name__ == "__main__":
    T = int(sys.stdin.readline())
    arr = list(map(int, sys.stdin.readline().split()))

    DP.append(arr[0])
    size = 0
    for i in range(1, T):
        if arr[i] > DP[size]:
            size += 1
            DP.append(arr[i])
            # DP[size] = arr[i]
        else:
            idx = LIS(0, size, arr[i])
            if(idx != -1):
                DP[idx] = arr[i]
    print(size+1)

참고자료 [참고블로그]https://blog.encrypted.gg/452 [LIS 참고 블로그]https://jason9319.tistory.com/113 [파이썬 이진탐색]https://programmers.co.kr/learn/courses/4008/lessons/13173 [이진탐색 알고리즘]https://debuglog.tistory.com/69 [최적화된 LIS]https://jins-dev.tistory.com/entry/%EC%B5%9C%EC%A0%81%ED%99%94%EB%90%9C-LISLongest-Increasing-Subsequence-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EA%B3%BC-%ED%95%B4-%EC%B0%BE%EA%B8%B0 [bisect 사용법]https://m.blog.naver.com/PostView.nhn?blogId=wideeyed&logNo=221389084876&proxyReferer=https%3A%2F%2Fwww.google.com%2F [마지막 참고 블로그]https://m.blog.naver.com/dmsrb1002/221413242771

0%