과제1
문제
Max Heap 자료구조를 이용하면 최대값을 O(logN)의 시간복잡도로 찾을 수 있다. Max Heap을 이용하면 우선순위 값이 낮은 자료를 먼저 출력하는 Priority Queue를 구현할 수 있다. Max Heap을 이용한 Priority Queue는 아래와 같은 특징을 가진다.
-
Max Heap을 이용한 Priority Queue의 특징
- 자료를 입력하는 동작과 출력하는 동작 모두
O(logN)으로 이루어진다. - 우선순위 값이 낮은 자료를 먼저 출력하되, 우선순위 값이 같은 자료끼리는 순서를 고려하지 않는다.
- 다음과 같은 Method들을 구현한다.
is_empty(): Queue가 비어있으면 True, 비어있지 않으면 False를 출력한다.put(): Priority Queue에 자료를 입력한다. 자료는 길이가 2인 Tuple로,(우선순위, 자료)형태로 입력받는다.get(): Priority Queue에서 자료를 출력한다. 출력한 데이터는 Priority Queue에서 삭제한다. 더이상 출력할 데이터가 없는 경우 None을 출력한다.peek(): Priority Queue에서 자료를 출력한다. 출력한 데이터는 Priority Queue에 그대로 유지한다. 더이상 출력할 데이터가 없는 경우 None을 출력한다.
class PriorityQueue: def __init__(self): pass def is_empty(self): pass def put(self, data): pass def get(self): pass def peek(self): pass - 자료를 입력하는 동작과 출력하는 동작 모두
나의 풀이
소스
class PriorityQueue:
def __init__(self):
self.que = []
def is_empty(self):
if len(self.que) == 0:
return True
else:
return False
def move_up(self, inserted_idx):
if inserted_idx <= 0:
return False
parent_idx = inserted_idx // 2
if self.que[inserted_idx] > self.que[parent_idx]:
return True
else:
return False
def put(self, data):
if len(self.que) == 0:
self.que.append(data)
return
self.que.append(data)
inserted_idx = len(self.que) - 1
parent_idx = inserted_idx // 2
if inserted_idx <= 0:
return
while self.que[inserted_idx][0] > self.que[parent_idx][0]:
self.que[inserted_idx], self.que[parent_idx] = self.que[parent_idx], self.que[inserted_idx]
inserted_idx = parent_idx
parent_idx = inserted_idx // 2
def move_down(self, popped_idx):
left_child_popped_idx = popped_idx * 2
right_child_popped_idx = popped_idx * 2 + 1
# case1: 왼쪽 자식 노드도 없을 때
if left_child_popped_idx >= len(self.que):
return False
# case2: 오른쪽 자식 노드만 없을 때
elif right_child_popped_idx >= len(self.que):
if self.que[popped_idx][0] < self.que[left_child_popped_idx][0]:
return True
else:
return False
# case3: 왼쪽, 오른쪽 자식 노드 모두 있을 때
else:
if self.que[left_child_popped_idx][0] > self.que[right_child_popped_idx][0]:
if self.que[popped_idx][0] < self.que[left_child_popped_idx][0]:
return True
else:
return False
else:
if self.que[popped_idx][0] < self.que[right_child_popped_idx][0]:
return True
else:
return False
def get(self):
if self.is_empty():
return None
returned_data = self.que[0]
self.que[0] = self.que[-1]
del self.que[-1]
popped_idx = 0
while self.move_down(popped_idx):
left_child_popped_idx = popped_idx * 2
right_child_popped_idx = popped_idx * 2 + 1
# case2: 오른쪽 자식 노드만 없을 때
if right_child_popped_idx >= len(self.que):
if self.que[popped_idx][0] < self.que[left_child_popped_idx][0]:
self.que[popped_idx], self.que[left_child_popped_idx] = self.que[left_child_popped_idx], self.que[popped_idx]
popped_idx = left_child_popped_idx
# case3: 왼쪽, 오른쪽 자식 노드 모두 있을 때
else:
if self.que[left_child_popped_idx][0] > self.que[right_child_popped_idx][0]:
if self.que[popped_idx][0] < self.que[left_child_popped_idx][0]:
self.que[popped_idx], self.que[left_child_popped_idx] = self.que[left_child_popped_idx], self.que[popped_idx]
popped_idx = left_child_popped_idx
else:
if self.que[popped_idx][0] < self.que[right_child_popped_idx][0]:
self.que[popped_idx], self.que[right_child_popped_idx] = self.que[right_child_popped_idx], self.que[popped_idx]
popped_idx = right_child_popped_idx
return returned_data[1]
def peek(self):
if self.is_empty():
return None
return self.que[0][1]설명
그냥 힙 구현에서 배운그대로의 알고리즘을 적용시키면서 다른점이 있다면 값 비교를 self.queue[idx] 끼리만 비교하였다면 우선순위큐로 적용시키면서 self.queue[idx][0] 이렇게 우선순위로 비교하도록 하였다.
과제2
문제
오름차순으로 정렬된 N개의 정수를 가진 List가 주어져있을 때, 해당 List에 존재하는 서로 다른 값이 몇 가지인지 알아내는 알고리즘을 구현하라. 알고리즘의 제약사항은 아래와 같다. (알고리즘은 1 <= N <= 10000에서 테스트된다.)
- 추가 메모리 사용은
O(1)으로 제한된다. 따라서 set()와 dict() 등의 자료구조를 사용할 수 없다. - 알고리즘의 시간복잡도는
O(N)이하로 제한된다.
def countUniques(a):
pass
print(countUniques([-1, 1, 1, 1, 1, 4, 4, 4, 4, 10, 14, 14])) # 5
print(countUniques([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1])) # 2나의 풀이
소스
def countUniques(a):
count = 1
prev_num = a[0]
for i in range(1, len(a)):
cur_num = a[i]
if cur_num != prev_num:
prev_num = cur_num
count += 1
return count설명
그냥 리스트의 크기 (N)번 만큼 순회하면서 다른값이 나오면 카운팅에 1추가하는 방식이다.
과제3
문제
N개의 문자열로 이루어진 List에서 전체 문자열이 앞 n개 문자열이 같다고 할때, 가장 큰 n을 출력하는 알고리즘을 구현하라.
def solution(a):
return 0
print(solution(['abcd', 'abce', 'abchg', 'abcfwqw', 'abcdfg'])) # 3
print(solution(['abcd', 'gbce', 'abchg', 'abcfwqw', 'abcdfg'])) # 0나의 풀이
소스
def solution(a):
compare_str = a[0]
for i in range(len(a) - 1):
next_str = a[i + 1]
if len(compare_str) < len(next_str):
compare_str = compare_str[0:len(next_str)]
# compare_str을 하나씩 줄여가면서 비교
while len(compare_str) > 0:
if compare_str == next_str[0:len(compare_str)]:
break
else:
compare_str = compare_str[0:len(compare_str) - 1]
# 가지치기 (빠른 종료)
if len(compare_str) == 0:
return 0
return len(compare_str)설명
앞 n개 문자열이 같은걸 찾으므로 맨 처음 문자열을 비교하고 아니면 맨 뒷글자를 줄여가는 방식으로 구현하였다. 그리고 비교문자열을 저장하면서 틀리면 줄여나가면서 찾는다.
과제4
문제
자연수 중, 각 자리수를 제곱한 것을 더하는 과정을 반복했을 때 1으로 끝나는 수를 ‘행복한 수’라고 한다. ‘행복한 수’가 아닌 경우 이 과정이 1에 도달하지 못하고 같은 수열이 반복되는 무한 루프에 빠지게 된다. 자연수를 입력받았을 때 ‘행복한 수’인지 판별하는 알고리즘을 작성하라.
‘행복한 수’를 찾는 과정의 예
19이 행복한 수인지 확인하는 과정
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1 --> Truedef solution(n):
return True
print(solution(19)) # True
print(solution(61)) # False나의 풀이
소스
def solution(n):
try:
if n == 1:
return True
next_num = 0
while(n > 0):
next_digit = n % 10
n = n // 10
next_num += next_digit ** 2
return solution(next_num)
except RecursionError:
return False설명
재귀함수로 구현하였으며 무한루프(재귀애러)에 빠지면 except로 잡아서 false처리하도록 하였다.
