탐욕법 (Greedy)

  • 탐욕적인 방법이란?
    결정 할 때마다 그 순간에 가장 좋다고 생각되는 것을 선택하며 최적의 해답에 도달하는 것
    탐욕적인 방법은 그 순간에는 최적이지만, 전체적인 관점에서 최적이라는 보장이 없기 때문에 반드시 검증해야 한다.

체육복

1차 답안

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def solution(n, lost, reserve):
    tmp = lost.copy()
    
    for i in lost:
        if i in reserve:
            tmp.remove(i)
            reserve.remove(i)

        elif i - 1 in reserve:
            tmp.remove(i)
            reserve.remove(i-1)
        
        elif i + 1 in reserve and i + 1 not in lost:
            tmp.remove(i)
            reserve.remove(i+1)
        
    return  n - len(tmp)

tmp = lost.copy()
초기에 tmp = lost로 리스트 자체를 복사했더니
tmp.remove(value)를 해버리니 lost의 값도 삭제가 되는 문제가 발생했다.

단순복사 vs 얕은복사 vs 깊은복사

단순 복사

단순 복사는 완전히 동일한 객체를 복사합니다.

1
2
3
4
5
6
7
8
a = [1, [2, 3, 4]]
b = a
b[0] = 100
b[1][0] = 100
print(a)
# [100, [100, 3, 4]]
print(b)
# [100, [100, 3, 4]]

얕은 복사(shallow copy)

  • 복합개체 ([1, [2, 3, 4]])만 새로운 객체로 복사하고 내부객체 ([2, 3, 4])는 동일한 객체를 참조합니다.
1
2
3
4
5
6
7
8
9
10
a = [1, [2, 3, 4]]
b = a.copy()

b[0] = 100
b[1][0] = 100

print(a)
# [1, [100, 3, 4]]
print(b)
# [100, [100, 3, 4]]

깊은 복사(deep copy)

  • 깊은복사는 복합객체와 내부객체를 재귀적으로 복사합니다.
  • 둘다 완전 다른 객체로 기존 객체의 값 변경에 영향 받지 않습니다. (객체 전체를 복사하여 새로운 객체를 만듭니다.)
1
2
3
4
5
6
7
8
9
10
a = [1, [2, 3, 4]]
b = a.copy()

b[0] = 100
b[1][0] = 100

print(a)
# [1, [2, 3, 4]]
print(b)
# [100, [100, 3, 4]]

복사방식이 두가지인 이유는?

  • 자기 자신을 참조하는 객체를 복사하면 recursive loop가 발생할 수 있기 때문입니다.
  • 깊은 복사는 원본과 공유해야 하는 데이터까지 새로운 객체로 복사하기 때문입니다.

큰 수 만들기

1차 답안

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from itertools import permutations

def solution(number, k):
    list_num = list(number)
    idx = -1
    max_num = 0
    answer_list = []
    
    for i in range(len(list_num) - k, 0 , -1):

        max_num = max(list_num[idx+1: len(list_num) - i +1])
        
        idx = list_num.index(max_num)
        
        for i in range(idx+1):
            list_num[i] = 0

        answer_list.append(max_num)
    
    return ''.join(answer_list)

효율성 문제로 실패

2차 답안

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from itertools import permutations
import operator

def solution(number, k):
    list_num = list(map(int, number))

    idx = -1
    max_num = 0
    answer_list = []

    for i in range(len(list_num) - k, 0 , -1):
        idx, max_num, = max(enumerate(list_num[idx+1: len(list_num) - i +1], idx+1), key=operator.itemgetter(1))
        answer_list.append(str(max_num))

    return ''.join(answer_list)

enumerate를 사용해서 해당 max인 값의 idx와 max_num을 가져와 저장 -> 0으로 초기화했던 값들 해결

테스트 케이스 10 시간초과로 통과 x

테스트 케이스 10 : 99999999999999999999999999999999 , 9999999999999 -> max를 사용하다면 시간초과 발생

3차 답안

max 함수를 사용하게 된다면 시간초과가 발생함 (테스트 케이스 10 통과 불가)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def solution(number, k):
    answer = ''
    stack=''
    while k!=0:
        if number!='':
            stack+=number[0]   
            number=number[1:]   
            len_stack=len(stack)
            for i in reversed(range(len_stack)):
                if number=='':
                    break
                if number[0]>stack[i]:
                    stack=stack[:i]
                    k-=1
                    if k==0:
                        break
                else:
                    break
        else:
            stack=stack[:-1]
            k-=1
    answer=stack+number
    return answer

조이스틱

1차 답안

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
def solution(name):

    idx , answer = 0, 0
    str_Alpabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

    # 모두 A로 이루어진 이름이라면 움직일 필요 X
    if name  == "A" * len(name):
        pass
    else:
        # 오른쪽으로 갈지 왼쪽으로 갈지 나타내주는 지표
        l_index = 0 #1이면 왼쪽방향

        for i in range(len(name)):

            if i == 0:
                idx = str_Alpabet.index(name[i])

                if idx < len(str_Alpabet) / 2: 
                    answer += idx
                # z에 더 가까울 경우
                else: 
                    idx = len(str_Alpabet) - idx
                    answer += idx

                
                if name[i-1] == name[i+1]:
                    answer += 1
                    l_index = 0
                elif name[i+1] == 'A':
                # 왼쪽으로 커서 이동
                    answer += 1
                    l_index = 1
                else:
                # 오른쪽으로 커서 이동
                    answer += 1
                    l_index = 1

            elif l_index == 0:
                idx = str_Alpabet.index(name[i])

                if idx  < len(str_Alpabet) / 2:
                    answer += idx
                # z에 더 가까울 경우
                else: 
                    idx = len(str_Alpabet) - idx
                    answer += idx

                # 커서 이동
                if i == len(name) -1 and name[i+1] == "A":
                    # 1. 마지막 요소가 A일 경우 옮기지 않아도 완성
                    break
                elif i == len(name) -1:
                    # 마지막요소일 경우 + 1 하지 않는다.
                    break
                else:
                    # 오른쪽으로 커서 1
                    answer += 1

            elif l_index == 1:
                idx = str_Alpabet.index((name[len(name)-i]))
                if idx < len(str_Alpabet) / 2: 
                    answer += idx
                else: 
                    idx = len(str_Alpabet) - idx
                    answer += idx

                # 왼쪽으로 커서 이동
                if i == len(name) -2 and name[len(name)-i -1] == "A":
                    break
                elif i == len(name) - 1:
                    # 마지막 요소일 경우 + 1 안한다. 
                    break
                else:
                    # 왼쪽 으로 커서 이동
                    answer += 1

    return answer

테스트 케이스 10, 11 통과 X

name = "AZAAAAAAAZZ" 일 경우 오른쪽으로 처리 후 왼쪽으로 돌아가 처리를 하는 것이 효율적이다.

1
2
3
A▶(1) Z▼(2) ◀◀(4) Z▼(5) ◀(6) Z▼(7)

A▶(1) Z▼(2) ▶▶▶▶▶▶▶(9) Z▼(10) ▶(10) Z▼(11)

2차 답안

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def solution(name):
    answer = 0
    name=list(name)
    index=0
    while(True):
        right=1
        left=1
        if name[index] != 'A': 
            updown = min(ord(name[index])-ord('A'),(ord('Z')-ord(name[index])+1))
            answer += updown
        name[index] = 'A'
        if name == ["A"]*len(name): break
        for i in range(1,len(name)):
            if name[index+i]=="A": right+=1
            else: break
        for i in range(1,len(name)):
            if name[index-i]=="A": left+=1
            else: break
        if right>left:
            answer+=left
            index-=left
        else:
            answer+=right
            index+=right
    return answer

ord()
특정 한 문자를 아스키 코드 값으로 변환해 주는 함수

cf) chr()
아스키 코드 값을 문자로 변환해 주는 함수

1
2
3
4
5
6
7
8
9
10
11
12
13
print(ord('A'))
# 65
print(ord('a'))
# 97
print(hex(ord('b')))
# 0x62

print(chr(65))
# 'A'
print(chr(97))
# 'a'
print(chr(0x62))
# 'b'

구명보트

  1. 한 번에 최대 2명씩 밖에 탈 수 없고
  2. 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.

-> 한번에 최대 2명이 탄다 -> 정렬 후 최소값과 최대값을 더해 limit 보다 작다면 2명타고 크다면 1명만 타도록 알고리즘 구현

1차 답안

1
2
3
4
5
6
7
8
9
10
11
def solution(people, limit):
    people.sort()
    cnt = 0
    i, j = 0, len(people) -1
    while(i <= j):
        cnt += 1
        if people[j] + people[i] <= limit:
            i+=1
        j -= 1

    return cnt

통과

섬 연결하기

Kruskal 알고리즘

  • 탐욕적인 방법(greedy method) 을 이용하여 가중치를 간선에 할당한 그래프(네트워크)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것

Kruskal 전재조건

  1. 최소 비용 신장 트리(MST)가 최소 비용의 간선으로 구성되었는가
  2. 사이클을 포함하지 않음 의 조건에 근거하여 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택 한다.

img

참고URL

1차답안

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def solution(n, costs):
    answer = 0

# 순서대로  (거리순)
    costs.sort(key = lambda x : x[2])

    # 연결된 섬 리스트
    islands = []
    cost_islands = []
    while n != len(islands):
        for cost in costs:
            print(cost)
            # 아예 두 요소가 islands에 없다면 두요소의 최솟값 더하고 섬연결  
            if cost[0] not in islands and cost[1] not in islands:
                islands.append(cost[0])
                islands.append(cost[1])
                answer += cost[2]
                cost_islands.append(cost)
            # cost[0] 가 없다면 cost[0 넣고]
            elif cost[0] not in islands:
                islands.append(cost[0])
                answer += cost[2]
                cost_islands.append(cost)
            elif cost[1] not in islands:
                islands.append(cost[1])
                answer += cost[2]
                cost_islands.append(cost)
                
    return answer

테스트케이스 2,3,4,5,6,7 통과 불가 25점…

1
2
n = 5
costs = [[0, 1, 1], [2, 3, 1], [3, 4, 2], [1, 2, 2], [0, 4 100]]

위 와 같은 사례에 [024] [13] 두 영역이 연결된 상태가 아니지만 다 연결되었다고 표시가 되어 오류가 발생한다.

2차 답안

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
parent = {}
rank = {}


def make_set(v):
    parent[v] = v
    rank[v] = 0


def find_root(v):
    if parent[v] != v:
        parent[v] = find_root(parent[v])
    return parent[v]


def union(r1, r2):
    if r1 != r2:
        if rank[r1] > rank[r2]:
            parent[r2] = r1
        else:
            parent[r1] = r2
            if rank[r1] == rank[r2]:
                rank[r2] += 1


def solution(n, costs):
    for i in range(n):
        make_set(i)
    s = 0
    costs = sorted(costs, key=lambda x: x[2])
    for j in costs:
        v, u, w = j
        r1 = find_root(v)
        r2 = find_root(u)
        if r1 != r2:
            union(r1, r2)
            s += w
    return s

2차 답안은 Union의 개념을 코드로 적용하기 힘들어
Kruskal 알고리즘 코드를 참고해서 작성했다..

다른사람 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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

Kruskal 알고리즘에서 Rank 개념을 삭제해 더 간소한 코드를 작성했다.