탐욕 알고리즘(Greedy Algorithms)
-
매 순간 현재 기준으로 최선의 답을 선택해 나가는 기법
-> 빠르게 근사치를 계산할 수 있음
-> 결과적으로는 최적해가 아닐 수도 있음 -
탐욕 알고리즘의 결과가 최적해인 경우를 알아야 함
활동 선택 문제(Activity selection problem)
-
N 개의 활동과 각 활동의 시작/종료 시간이 주어졌을 때, 한 사람이 최대한 많이 할 수 있는 활동의 수 구하기
-
활동을 종료 시간 기준으로 오름차순 정렬
-
먼저 종료되는 활동부터 그리디하게 선택: 문제 조건에 따라 시간이 겹치는 경우는 제외
거스름돈 문제
- 동전의 개수가 가장 적게 거스름돈을 돌려주는 문제
- 동전의 종류가 배수로 증가하지 않을 경우, 그리디 알고리즘이 최적해가 아닐 수 있음
-> 동전의 종류: 10, 50, 100, 400, 500: 동적 계획법(DP)에서 해결 방법을 배움
그리디 알고리즘 최적해 조건
- 그리디 알고리즘은 빠르지만 최적해를 보장하지는 못함
- 두 가지 조건에 해당하는 경우 적용 가능
-> 탐욕적 선택 특성(Greedy choice property): 지금 선택이 다음 선택에 영향을 주지 않음
-> 최적 부분 구조(Optimal substructure): 전체 문제의 최적해는 부분 문제의 최적해로 이루어짐
탐욕 알고리즘 문제 풀이
1) 활동 선택 문제를 해결하세요!
각 활동이 activity[i] = [시작시간, 끝나는시간]으로 주어질 때,
시간이 겹치지 않도록 선택할 수 있는 가장 많은 활동의 수를 구하시오.
- 매개변수 형식
activity = [[1, 5], [4, 6], [3, 5], [7, 12], [5, 11], [13, 15]] - 반환값 형식
3
def solution(activity):
items = [(x[1], x[0]) for x in activity]
items.sort()
count = 0
last_end_time = 0
for event in items:
end_time, start_time = event
if start_time < last_end_time:
continue
else:
count +=1
last_end_time = end_time
return count
if __name__ == '__main__':
activity = [[1, 5], [4, 6], [3, 5], [7, 12], [5, 11], [13, 15]]
sol = solution(activity)
print(sol)2) 양의 정수가 담긴 문자열 s가 있다고 하자. 이 문자열에서 k개의 숫자를 제거해, 가장 작은 숫자를 만들고자 한다.
이렇게 만든 가장 작은 숫자를 담은 문자열을 출력하시오.
단, k개의 문자열을 제거한 결과는 앞에 불필요한 0이 포함될 수 있으며,
최종 출력에는 이 불필요한 0는 제거하여 출력하시오. (예시 입출력 참고)
- 입력 예시
s = "105990"
k = 1 - 출력 예시
"5990" - 입출력 설명
맨 앞의'1'을 제거하면"05990"이 된다. 불필요한'0'를 제거한 최종 출력은"5990"이다.
def solution(s, k):
if k >= len(s):
return "0"
if k == 0:
return s.lstrip('0')
if s[1] == '0':
return solution(s[1:].lstrip('0'), k-1)
else:
ind = 0
for i in range(1, len(s)):
if s[i-1] <= s[i]:
ind = i
else:
break
return solution(s[:ind] + s[ind+1:], k-1)
if __name__ == '__main__':
s = "105990"
k = 1
sol = solution(s, k)
print(sol)3) 숫자 num이 주어졌을 때, 최대 한번의 자릿수 교환을 통해 최대의 숫자를 만들어 내려고 한다.
즉, 자릿수를 교환하지 않았을 때가 더 큰 숫자인 경우, 원래 숫자를 그대로 출력해야 한다.
위 프로그램을 작성하시오.
- 매개변수 형식
num = 43824 - 반환값 형식
83424 - 입출력 예시 설명
0번째 인덱스의 숫자8과 2번째 인덱스의 숫자4의 자릿수를 바꾸었을 때 가장 큰 수가 된다.
def solution(num):
digits = list(map(int, list(str(num))))
inc_ind = -1
for i in range(1, len(digits)):
if digits[i] > digits[i-1]:
inc_ind = i
break
if inc_ind == -1:
return num
max_val = digits[inc_ind]
max_ind = inc_ind
for i in range(inc_ind + 1, len(digits)):
if digits[i] >= max_val:
max_val = digits[i]
max_ind = i
for i in range(inc_ind):
if digits[i] < max_val:
digits[max_ind], digits[i] = digits[i], digits[max_ind]
return int(''.join(map(str, digits)))
if __name__ == '__main__':
num = 43824
sol = solution(num)
print(sol)분할 정복(Divide and Conquer)
- 큰 문제를 작은 부분 문제로 나누어 해결하는 방법: 합병 정렬, 퀵 정렬, 이진 검색 ...
- 분할 정복 과정
-> 1) 문제를 하나 이상의 부분 문제(sub-problem)로 분할
-> 2) 부분 문제를 각각 해결
-> 3) 부분 문제의 해답을 통합하여 원래 문제를 해결
분할 정복의 장/단점
- 장점: 문제를 나누어 처리하며 어려운 문제 해결 가능, 병렬 처리에 적합한 계산 구조
- 단점: 메모리를 많이 사용(재귀 호출 구조)
분할 정복 예시
- 최대값 찾기
분할 정복 문제 풀이
1) 흰색(0)과 검은색(1)로만 이루어진 이진영상(binary image)은 다양한 방식으로 압축할 수 있다. 여러 압축 방법 중에, 당신은 쿼드트리(quad-tree) 방식으로 압축하고자 한다.
쿼드트리 압축 방식은 아래와 같다.
- 압축하려는 영상 전체가 0이면
"0", 전체가 1이면"1"로 압축한다. - 영상 전체가 같은 값이 아니라면, 영상을 동일한 크기로 4분할하여 부분 영상 별로 압축한다.
- 각 부분 영상을 압축하는 방법은 전체 영상을 압축하는 방법과 같다.
- 각각의 압축 결과를
"(좌상단 우상단 좌하단 우하단)"과 같이 출력한다. (각 문자 사이에 공백은 쓰지 않는다. ex) (0110))
아래와 같은 영상이 있다고 예를 들어보자.
0, 0, 0, 0, 1, 1, 1, 1
0, 0, 0, 0, 1, 1, 0, 0
0, 0, 0, 0, 0, 0, 1, 1
0, 0, 0, 0, 0, 0, 1, 1
1, 1, 0, 0, 0, 0, 0, 0
1, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 0
0, 0, 0, 0, 0, 0, 0, 1이 때, 압축 결과는 아래와 같다.
(0(1(1100)01)((1110)000)(000(0001)))
위 쿼드트리 압축 결과를 출력하는 프로그램을 작성하시오.
def solution(image):
def encode(i, j, n):
if n == 1:
return str(image[i][j])
first_value = image[i][j]
is_consistent = True
for k in range(i, i+n):
for l in range(j, j+n):
if image[k][l] != first_value:
is_consistent = False
break
if is_consistent:
return str(first_value)
s = '('
s += encode(i, j, n // 2)
s += encode(i, j + n // 2, n // 2)
s += encode(i + n // 2, j, n // 2)
s += encode(i + n // 2, j + n // 2, n // 2)
s += ')'
return s
return encode(0, 0, len(image))
if __name__ == '__main__':
image = [[0, 0, 0, 0, 1, 1, 1, 1],
[0, 0, 0, 0, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 1],
[0, 0, 0, 0, 0, 0, 1, 1],
[1, 1, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 1]]
sol = solution(image)
print(sol)2) 담디는 디귿(ㄷ)자 모양이 너무나도 좋아서, 2차원 배열에 숫자를 디귿자로 배치하려고 한다.
깔끔한 것을 좋아하는 담디는 정방형(높이와 너비가 같은) 2차원 배열만을 사용한다.
숫자를 채우는 구체적인 방법은 아래와 같다.
- 배열의 높이와 너비는
n으로 같으며, 항상 2의 제곱수이다. - 배열을 높이와 너비를 반반씩 나누어 4개의 부분 배열을 만든다.
- 우측 상단, 좌측 상단, 좌측 하단, 우측 하단의 순서로 숫자를 채운다. (ㄷ자를 한 붓 그리기 한 순서)
- 각 부분 배열을 채우는 방법은 이 방법을 재귀적으로 사용하여 숫자를 채운다.
즉, 예를 들면 n=2인 경우에는 아래와 같이 디귿자 모양으로 곧바로 숫자를 채운다.
n=4인 경우에는 아래와 같이 재귀적으로 순서를 정해서 숫자를 채운다.
이 때, i행 j열에 위치한 값을 반환하는 프로그램을 작성하시오. (행과 열은 0부터 시작해서 n-1까지의 값을 가진다.)
def solution(n, i, j):
def solve(offset, n, i, j):
if n == 2:
mat = [[2, 1], [3, 4]]
return offset + mat[i][j]
m = n // 2
m2 = m**2
if i < m and j >= m:
return solve(offset, m, i, j-m)
elif i < m and j < m:
return solve(offset + m2, m, i, j)
elif i >= m and j < m:
return solve(offset + 2*m2, m, i-m, j)
else:
return solve(offset + 3*m2, m, i-m, j-m)
return solve(0, n, i, j)
if __name__ == '__main__':
n = 4
i = 1
j = 3
sol = solution(n, i, j)
print(sol)3) 정수가 담긴 리스트 nums 가 주어졌다.
연속된 부분 배열의 합 중 가장 큰 값을 출력하세요.
def solution(nums):
def solve(left, right):
if left == right:
return nums[left]
mid = (left + right) // 2
sol_left = solve(left, mid)
sol_right = solve(mid + 1, right)
sol_mid = solve_mid(left, mid, right)
return max(sol_left, sol_right, sol_mid)
def solve_mid(left, mid, right):
max_left = -float('inf')
curr_sum = 0
for i in range(mid, left - 1, -1):
curr_sum += nums[i]
max_left = max(max_left, curr_sum)
max_right = -float('inf')
curr_sum = 0
for i in range(mid + 1, right + 1):
curr_sum += nums[i]
max_right = max(max_right, curr_sum)
return max_left + max_right
return solve(0, len(nums)-1)
if __name__ == '__main__':
nums = [-5, 0, -3, 4, -1, 3, 1, -5, 8]
sol = solution(nums)
print(sol)이 글은 제로베이스 데이터 취업 스쿨의 강의 자료 일부를 발췌하여 작성되었습니다
