Greed 탐욕 법 (프로그래머스)

그리디 알고리즘

- 동적 프로그래밍 사용시 지나치게 많은 일을 한다, 그래서 보완하는 개념으로 나옴 

미래를 생각하지 않고 최선의 선택을 하는 방법, 즉 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 최종 해답에 도달하는 문제 해결 방식

 

 

1번. 체육복

코딩테스트 연습 - 체육복

# greedy_1.py
n = 5               # 전체 학생
lost = [2, 4]       # 잃어버림
reserve = [1, 3, 5]     # 여벌


def solution(n, lost, reserve):
    l = [l for l in lost if l not in reserve]
    r = [r for r in reserve if r not in lost]

    for res in r:
        if res-1 in l:
            l.remove(res-1)
        elif res+1 in l:
            l.remove(res+1)

    return n - len(l)


print(solution(n, lost, reserve))

 

 

2번. 조이스틱

코딩테스트 연습 - 조이스틱

테스트 케이스가 강화되고 꽤나 신경써야 하는 문제로 바꿘거 같다.

# greedy_2.py
# name = "JEROEN"
name = "ABABAAAAAAABA"
# name = "JAZ"
# 아스키 값 이용하면 될듯? ord
# 1  2  3  4  5  6  7  8  9 10 11 12 13
# A, B, C, D, E, F, G, H, I, J, K, L, M,
# N, O, P, Q, R, S, T, U, V, W, X, Y, Z


def solution(name):
    def check_char(ch):
        if ch == "N":
            return 13
        elif ord(ch) < 78:
            return ord(ch) - 65
        else:
            return 91 - ord(ch)

    def check_move(name):
        right_list = [i for i, ch in enumerate(name) if ch != 'A']
        left_list = [-(i-len(name)) for i in right_list]
        # print(right_list, left_list)
        max_val = 0
        max_loc = 0
        max_index = 0
        for i in range(len(right_list)-1):
            if max_val < right_list[i+1] - right_list[i]:
                max_loc = right_list[i]
                max_index = i
                max_val = right_list[i+1] - right_list[i]

        # print(max_index, max_val, max_loc)
        return min(right_list[-1], left_list[0],
                   (max_loc*2)+left_list[max_index + 1],
                   (left_list[max_index + 1]*2) + max_loc)

    answer = 0
    check_move(name)

    for i in range(len(name)):
        answer += check_char(name[i])
    return answer + check_move(name)


print(solution(name))

 

3번. 큰 수 만들기

코딩테스트 연습 - 큰 수 만들기

# greedy_3.py
number = "1924"     # 1231234 4177252841
k = 2       # 3 4


def solution(number, k):
    max_num = [number[0]]
    for num in number[1:]:
        # 핵심 코드 [ 4 2 ] < - 7 들어오면 [] + 7
        while len(max_num) > 0 and max_num[-1] < num and k > 0:
            k -= 1
            max_num.pop()

        max_num.append(num)

    if k != 0:
        max_num = max_num[:-k]
    return ''.join(max_num)


print(solution(number, k))

 

4번. 구명보트

코딩테스트 연습 - 구명보트

# greedy_4.py
people = [70, 50, 80, 50]
limit = 100


def solution(people, limit):
    people.sort()
    answer = 0
    i, j = 0, len(people) - 1
    while i <= j:
        answer += 1
        if people[j] + people[i] <= limit:
            i += 1
        j -= 1
    return answer


print(solution(people, limit))

 

5번. 섬 연결하기

코딩테스트 연습 - 섬 연결하기

크루스칼 써도 됨 

# greedy_5.py
n = 5       # 1 이상 100 이하
# cost 의 길이는 ((n-1) * n) / 2
# costs = [[0, 1, 1],     # 0 <-> 1  비용 1
#          [0, 2, 2],     # 0 <-> 2  비용 2
#          [1, 2, 5],     # 1 <-> 2  비용 5
#          [1, 3, 1],     # 1 <-> 3  비용 1
#          [2, 3, 8]]     # 2 <-> 3  비용 8
costs = [[0, 1, 1],
         [0, 2, 2],
         [1, 2, 5],
         [1, 3, 3],
         [2, 3, 8],
         [3, 4, 1]]


def solution(n, costs):
    answer = 0      # 최소 비용의 합 return
    max_cost = int((((n-1) * n) / 2)+1)
    visit = [max_cost] * n
    costs = sorted(costs, key=lambda x: x[2])

    for cost in costs:
        if visit[cost[0]] == max_cost or visit[cost[1]] == max_cost:
            temp_min = min(visit[cost[0]], visit[cost[1]])
            if temp_min == max_cost:        # 둘다 초기상태일때
                _min = min(cost[0], cost[1])
                visit[cost[0]] = _min
                visit[cost[1]] = _min
            else:           # 둘 중 하나면 초기상태일때
                visit[cost[0]] = temp_min
                visit[cost[1]] = temp_min
            answer += cost[2]
        else:       # 둘다 초기 상태가 아닐 때
            if visit[cost[0]] != visit[cost[1]]:
                _max = max(visit[cost[0]], visit[cost[1]])
                _min = min(visit[cost[0]], visit[cost[1]])
                answer += cost[2]
                for i in range(len(visit)):
                    if visit[i] == _max:
                        visit[i] = _min
            else:
                print("이어져 있음")

    return answer


print(solution(n, costs))


# 크루스칼 <- 보기 
# def ancestor(node, parents):
#     if parents[node] == node:
#         return node
#     else:
#         return ancestor(parents[node], parents)
#
# def solution(n, costs):
#     answer = 0
#     edges = sorted([(x[2], x[0], x[1]) for x in costs])
#     parents = [i for i in range(n)]
#     bridges = 0
#     for w, f, t in edges:
#         if ancestor(f, parents) != ancestor(t, parents):
#             answer += w
#             parents[ancestor(f, parents)] = t
#             bridges += 1
#         if bridges == n - 1:
#             break
#     return answer

 

 

6번. 단속카메라

코딩테스트 연습 - 단속카메라

# greedy_6.py
# 차량의 경로 -30,000 ~ 30,000
routes = [[-20, 15],    # 이동 경로 -20 진입 지점, 15 빠져나간 지점
          [-14, -5],
          [-18, -13],
          [-5, -3]]


# 차량의 수 - 1 ~ 10000
def solution(routes):
    answer = 0
    overlap = -30001
    routes = sorted(routes, key=lambda x: x[1])
    for r in routes:
        if r[0] > overlap:
            answer += 1
            overlap = r[1]

    return answer


print(solution(routes))