통계러버

노션 링크 주소: 이상치 탐지 개요

노션 링크 주소 : metric 

노션 링크 주소 : 가우시안 분포

노션 링크 주소:  이산확률분포

노션 링크 주소 : Decision Theory

문제 링크 

• 더 맵게

문제 설명

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

입출력 예 설명

1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
   가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]
2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
   가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

힙

힙(heaps)

• 성질 : 최대/최소 원소를 빠르게 찾을 수 있음.
• 연산
     *   힙 구성(heapify) : O(NlogN)      # 삽입을 N번 하는 꼴로 이해하자.
     *   삽입(insert) : O(logN) : 삽입후에도 log에 비례하는 시간복잡도를 사용해서 min heap(or max heap)구조를 유지하도록 함.
    *   삭제(remove) : O(logN) : 삭제후에도 log에 비례하는 시간복잡도를 사용해서 min heap(or max heap)구조를 유지하도록 함.

코드

sol1)  min_heap을 이용한 우선순위 큐

def solution(scoville, K):
    import heapq as hq
    min_heap = []
    for i in scoville:
        hq.heappush(min_heap, i)                 #O(NlogN)
        
    cnt = 0    
    while min_heap[0] < K and len(min_heap)>1 :  # 힙구조가 되면 가장 처음값은 최솟값이 됨
        fist_min = hq.heappop(min_heap)
        second_min = hq.heappop(min_heap)
        new_sco = fist_min + second_min*2
        hq.heappush(min_heap, new_sco)
        cnt += 1
    return -1 if min_heap[0] < K else cnt

sol2) 

hq.heapify()를 이용하여 리스트를 min heap 형태(맨 앞이 항상 최솟값이 오게 됨)로 바꿔서 푸는 풀이

• hq.heapify() : 리스트를 min heap형태로 바꿈. 시간복잡도: O(logN)
• 주의! min_heap = hq.heapify(scoville) 이렇게 객체로 받아주면 안됨! 오류남

def solution(scoville, K):
    import heapq as hq
    hq.heapify(scoville)  # 리스트 scoville를 min heap으로 바꿈 
        
    cnt = 0    
    while scoville[0] < K and len(scoville)>1 :  # 힙구조가 되면 가장 처음 나오는 값은 최솟값이 됨
        fist_min = hq.heappop(scoville)
        second_min = hq.heappop(scoville)
        new_sco = fist_min + second_min*2
        hq.heappush(scoville, new_sco)
        cnt += 1
    return -1 if scoville[0] < K else cnt

sol3)

def solution(scoville, K):
    import heapq as hq
    hq.heapify(scoville)  # 리스트 scoville를 min heap으로 바꿈   O(logN)
     
    cnt = 0    
    while True:  # O(nlogn)
        fist_min = hq.heappop(scoville)  #O(logn)
        if fist_min >= K:
            break
        elif len(scoville) == 0:
            cnt = -1
            break      
        second_min = hq.heappop(scoville)  #O(logn)
        new_sco = fist_min + second_min*2
        hq.heappush(scoville, new_sco)
        cnt += 1
    return cnt

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42883

문제 설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

탐욕법인 이유

• 앞 단계에서의 선택(앞자리에 큰수)이 이후 단계에서의 동작에 의한 해(solution)의 최적성(optimality)에 영향을 주지 않음

솔루션

주어진 숫자(number)에서 왼쪽부터 하나씩 꺼내어 모으되,

1. 이때, 이미 모아둔 것 중 지금 등장하는 것보다 작은 것들은 빼낸다.
2. 단, 이때 유효한 숫자를 모두 소진할 때 까지만 뺀다.
3. 아직 뺄 개수(k)를 채우지 못한 경우 뒤에서 부터 남은 자리수만큼 뺀다.

코드

sol1) 스택을 이용한 풀이

def solution(number, k):
    stack = [number[0]]
    for num in number[1:]:
        while len(stack) > 0 and stack[-1] < num and k > 0: # 파이썬에서 문자열의 대소관계는 아스키 코드를 따라 간다. 이를 이용하면 문자열로 된 숫자를 대소비교히면 숫자일때의 대소 비교때와 같아진다.
            k -= 1
            stack.pop()
        stack.append(num)
    if k != 0:   # while문을 다 돌았는데 k가 0이 아니면 뒤에서부터 pop한다
        stack = stack[:-k]
    return ''.join(stack)

sol2) 스택을 이용한 풀이2

def solution(number, k):
    stack = []
    for x in number:
        while stack and k >0 and stack[-1] < x:  # 파이썬에서 문자열의 대소관계는 아스키 코드를 따라 간다. 이를 이용하면 문자열로 된 숫자를 대소비교히면 숫자일때의 대소 비교때와 같아진다.
            stack.pop()
            k -= 1
        stack.append(x) # 맨 처음에는 stack이 비어있으므로 while문 돌지 않고 x부터 append함
    if k!=0:
        stack = stack[:-k]
    res = ''.join(map(str, stack))  
    return res

sol3) 스택과 큐를 이용한 풀이

from collections import deque
def solution(number, k):
    cnt = 0
    q= deque(number)
    sol = []
    sol.append(q.popleft()) #number의 첫글자를 stack에 넣고 시작
    while q:
        x = q.popleft()
        while sol and x > sol[-1] and cnt !=k:  # 스택의 맨위 글자와 큐의 왼쪽 첫번째 글자를 비교해서 스택의 맨위 글자가 더 작으면 크거나 같아 질때까지 스택의 맨 위 글자를 pop한다. 이 때 pop을하다 pop의 숫자가 k가 되면 멈춘다
                                                # 또한, 스택이 비어있으면 pop을 못하므로 비게 되면 멈춘다
                                                #  파이썬에서 문자열의 대소관계는 아스키 코드를 따라 간다. 이를 이용하면 문자열로 된 숫자를 대소비교히면 숫자일때의 대소 비교때와 같아진다.
            sol.pop()
            cnt +=1 
        sol.append(x)                           
        while (not q) and (cnt != k) :         #만약 q의 원소를 모두 썼는데 cnt에 도달 못했으면 도달할때까지 뒤에서부터 빼냄
            sol.pop()
            cnt +=1
    return ''.join(sol)

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42862

문제 설명

제한사항

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

입출력 예

입출력 예 설명

예제 #1
1번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육수업을 들을 수 있습니다.

예제 #2
3번 학생이 2번 학생이나 4번 학생에게 체육복을 빌려주면 학생 4명이 체육수업을 들을 수 있습니다.

솔루션

위에 처럼 여벌의 체육복을 지닌 학생들이 오름차순으로 정렬 되어 있을때, 나보다 번호가 1번 높은 체육복이 없는 학생에게 체육복을 주면 5명이 체육복을 지니게 됨.

반면, 나보다 번호가 1번 낮은 체육복이 없는 학생에게 체육복을 주면 6명이 체육복을 지니게 됨.

따라서 여벌의 체육복을 지닌 학생이 오름차순으로 정렬되어있을때는 먼저 자신보다 번호가 1 낮은 체육복이 없는 학생에게 체육복을 주고, 번호가 1 낮은 체육복이 없는 학생이 없으면 번호가 1 높은 체육복이 없는 학생에게 체육복을 주어야 한다. 이 순서가 바뀌게 되면 체육복을 지닌 학생 수의 최댓값을 구할 수 없다.

코드

sol1)

def solution(n, lost, reserve):
    u = [1]* (n+2) # 학생수보다 2 큰 리스트를 만든다. 사람수는 n명이지만 for문을 돌면서 앞에 혹은 뒷 사람에게 체육복을 빌려주는 행위(-1)을 해야 하므로 n+2개를 만든다
    for i in reserve:  # O(n)
        u[i] +=1 # 여벌의 옷을 가지고 있는 학생들은 체육복의 수가 2임 
    for i in lost:     # O(n)
        u[i] -= 1 # 옷을 가지고 있지 않은 학생들은 체육복의 수가 0임
    
    for j in range(1,n+1): # for문은 1번부터 n번의 학생들만 돈다  # O(n)
                           # 사람이 오름차순으로 정렬되어있으므로 탐욕법을 적용하려면 나보다 번호가 1 낮은 사람이 체육복을 가지고 있는지를 먼저 살펴야 함   
        if u[ j - 1] == 0 and u[j] == 2:  # 내가 2벌을 가지고 있고 나보다 번호가 1 작은 사람이 체육복이 없다면 빌려준다
            u[j-1 : j+1] = [1,1]
        elif  u[j] == 2 and u[j + 1] ==0:  # 내가 2벌을 가지고 있고 나보다 번호가 1 큰 사람이 체육복이 없다면 빌려준다
            u[j : j+2] = [1, 1]
            
    return len([x for x in u[1:-1] if x > 0]) # 1번 부터 n번의 학생들 중에서 숫자가 1인 사람들만 모은 리스트의 길이를 구한다  # O(n)

sol2) n은 매우 큰데 여벌의 체육복을 가져온 학생수가 매우 작으면 해당 풀이가 더 적합하다.

def solution(n, lost, reserve):
    
    s = set(lost) & set(reserve)  # 여벌의 체육복을 가지고 왔지만 도난당해서 다른사람에게 빌려줄 수 없는 사람들
    lost_only = set(lost) - s # 체육복을 빌려야 하는 사람들
    reserve_only = set(reserve) - s # 여벌의 체육복을 가진 사람들
    
    for x in sorted(reserve_only):   # 여벌의 체육복을 지닌 사람들을 오름차순으로 정렬했으므로 탐욕법을 적용하려면 나보다 번호가 1 낮은 사람이 체육복을 가지고 있는지를 먼저 살펴야 함   # O(KlogK)
        if  x-1 in lost_only:
            lost_only.remove(x-1)
        elif x+1 in lost_only:
            lost_only.remove(x+1)
    return n - len(lost_only)

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges