알고리즘(Python) 그리디

문제링크

구명보트

원래 시도

def solution(people, limit):
    people.sort()
    cnt = 0
    while people:
        sum = 0
        for ind, i in enumerate(people):
            # print(ind)
            sum += i
            if ind == 2:
                break
            if sum > limit:
                break
        # print('del {}'.format(people[:ind]))
        if ind==0:
            # print('del {}'.format(people[ind]))
            del people[ind]
        del people[:ind]
        cnt += 1
  return cnt

작은 수부터 더해나가는 것
2개만 더해야하기때문에 큰 수부터 제일 대척점에 있는 작은 수와 조합을 봐야됌

새로운 시도

def solution(people, limit):

    people.sort()
    cnt = 0
    while people:
        i = len(people) - 1
        if len(people) == 1:
            cnt += 1
            break
        elif people[i-len(people)+1] + people[i] <= limit:
            people = people[i-len(people)+2 : i]
        else:
            people = people[:i]
        cnt += 1
        i -= 1
    return cnt

큰수부터 제일 차이나는 수와 합해서 비용보다 작거나 같은 지 본다..!!

정확성은 만족!
효율성은 불만족^^

정답

from collections import deque
def solution(people, limit):
    people.sort()
    people = deque(people)
    cnt = 0
    while people:
        i = len(people) - 1
        if len(people) == 1:
            cnt += 1
            break
        elif people[i-len(people)+1] + people[i] <= limit:
            people.pop()
            people.popleft()
        else:
            people.pop()
        cnt += 1
        i -= 1
    return cnt

• deque 사용해서 pop, popleft사용!

섬 연결하기

응 모르겠어~ 다익스트라 아니야~

크루스칼 알고리즘이라는 게 있다고 한다.
크루스칼 알고리즘 설명

def solution(n, costs):
    # kruskal algorithm
    ans = 0
    costs.sort(key = lambda x: x[2]) # cost 기준으로 오름차순 정렬
    routes = set([costs[0][0]]) # 집합, cost의 첫번째 노드가 시작 노드
    while len(routes)!=n:
        for i, cost in enumerate(costs): # cost가 적은 것부터
            if cost[0] in routes and cost[1] in routes: # 사이클을 만들지 않기 위해서
                continue
            if cost[0] in routes or cost[1] in routes:
                routes.update([cost[0], cost[1]])
                ans += cost[2] 
                costs[i] = [-1, -1, -1] # 넣어준 노드는 무효처리
                break
    return ans

참고링크