과제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 --> True
def 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처리하도록 하였다.