학습 주제
그리디 알고리즘 코드 구현

학습 내용

탐욕법 (Geedy) - 체육복

풀이 코드

def solution(n, lost, reserve):
    # 허깨비 2개를 생성하기 위해 추가로
    u = [1] * (n + 2)
    # 맨 왼쪽, 맨 오른쪽에 허깨비들을 세워야 함 탐욕적으로 검색할 때 필요
    for i in reserve:
        u[i] += 1
    for i in lost:
        u[i] -= 1
    for i in range(1, n + 1):
        # 앞에서 뒤로 스캔하기 때문에, 탐욕탐색도 앞부터
        if u[i - 1] == 0 and u[i] == 2:
            # 리스트에 있는 여러 값을 슬라이스를 이용해서 이렇게 넣을 수 있음. 새로 배움
            u[i - 1:i + 1] = [1, 1]
        elif u[i] == 2 and u[i + 1] == 0:
            u[i:i + 2] = [1, 1]
            # 허깨비엔 각각 1씩 들어가 있기 때문에, 위의 코드가 단순화 될 수 있음. u[i+1] u[0]의 바운더리를 체크하지 않아도 됨.


        # 유효한 숫자 중, x >0 인 배열들의 길이가 정답.
        # 리스트 컴프리헨션을 사용하는데
        # 범위는 1:-1 [0], [-1]은 제외함.
        # 슬라이스의 오른쪽은 포함하지 않음.
    return len([x for x in u[1:-1] if x > 0])

정확성 테스트를 모두 통과한 모습을 볼 수 있다.

복잡도 계산

• 첫번째 for -> 길이 reserve 길이에 비례 O(n)

• 두번째도 n에 비례

• 세번째 for 정확히 n 회 반복함. 학생을 모두 순회하면서 탐욕 탐색을 시작.

• 전체 알고리즘은 n에 비례하는 복잡도

• 리스트 컴프리헨션도 1부터 -2까지 n에 비례함.

• O(n)의 복잡도를 가진 알고리즘이라 할 수 있다.

만약에

• 최대학생수가 10만명, 여벌의 학생이 2명인 경우, 전체 학생 수를 순회하는 것은 비효율 적일 수 있음.
• 다른 방법을 고안해야함

풀이 코드 2

def solution(n, lost, reserve):
    #set 이용 hash 이용
    #dict 와 다른 점은. value는 없고, 어떤 원소가 이 집합에 있는지 없는지만 상관하는 자료구조
    # set은 중복값을 갖지 않는 점을 이용
    # 두 집합의 교집합 & (차집합 계산용)
    s = set(lost) & set(reserve)
    # 체육복을 도난당한 학생인데, reserve에도 들어있어서 이번 알고리즘에서 사실 의미가 없는 학생을 빼줌
    # 차집합을 구함
    l = set(lost) - s
    # 여벌의 체육복을 가져왔고, 도난당하지도 않은 (차집합) 집합을 구함.
    r = set(reserve) - s
    # 빌려줄 수 있는 학생들을 정렬해야함
    for x in sorted(r):
        # 나보다 바로 앞번호 학생이 체육복을 도난당한 학생 중 한명이면,
        if x - 1 in l:
            l.remove(x - 1)
        # 나보다 바로 뒤ㅛ번호 학생이 체육복을 도난당한 학생 중 한명이면,
        elif x + 1 in l:
            l.remove(x + 1)
    # 저 loop을 돌게되면 빌려야하나 빌리지 못한 학생 집합(l)이 남게 된다.

    # 전체학생 수 - 빌리지 못한 학생 수
    return n - len(l)

set을 이용한 구현.
빌려줄 수 있는 학생을 오름차순으로 정렬하였기 때문에, 탐욕법을 적용할 때도 나보다 앞번호를 먼저 탐색, 그 다음 자기 뒷번호를 탐색하는 순으로 진행 한다.

복잡도 계산

• 집합 r 에 들어있는 사람만큼 반복, 그러나
• sorted(r) -> klogk
  -> 전체 klogk 복잡도
• 또한 set을 만들때도 복잡도가 소요됨. 배열의 길이에 비례함
• 학생수가 많고, 즉 n이 매우 크지만, k값이 작을 경우 효율적