프로그래머스 인공지능 데브코스 3기 수업내용 정리 #4(코딩테스트 연습2)

코딩 테스트 연습2

힙(Heap) 대표 문제풀이 : 더맵게

문제는 다음과 같다.
https://programmers.co.kr/learn/courses/30/lessons/42626

문제 해석, 예제 패턴 분석

• Scoville = [1, 2, 3, 9, 10, 12]
  K = 7
  return 2

• 규칙에 따라 새로운 음식의 스코빌 지수는

1 + 2 * 2 = 5
3 + 5 * 2 = 13

으로 만들어진다.

알고리즘의 구상과 복잡도 탐색

• 최악의 경우
  마지막 음식까지도 기준을 충족하지 못하는 경우에 n-1회 계산
• 계산량
  새로 만들어진 음식을 정렬하는 과정은 전수 조사이므로 O(n)의 시간 복잡도를 가진다. 따라서 매 단계에서 O(n)을 거친다면 전체 계산은 O(n^2)의 시간 복잡도를 가질 수 있다.
• 힙을 활용한 개선방법
  힙 자료구조를 활용한다면 최대/최소 원소를 빠르게 찾을 수 있기 때문에 정렬에 필요한 계산의 시간 복잡도를 O(logN)으로 낮출 수 있다. 참고로 힙을 구성하는 heapify의 경우에 탐색에 logN의 시간이 N개의 원소에 이루어지므로 시간 복잡도는 O(NlogN)이 된다.

파이썬에서 힙의 활용

import heapq
heapq.heapify(list) #list를 min heap으로 구성
heapq.heappop(list) #min heap list에서 최소값 삭제 및 반환
heapq.heappush(list,x) #min heap list에 원소 x삽입

코드 구현

import heapq

def solution(scoville, k):
    answer = 0
    heapq.heapify(scoville) #리스트를 min heap으로
    while True: #while pop구문을 활용
        min1 = heapq.heappop(scoville) #최소값을 꺼내서
        if min1 >= K: #기준값을 넘겼으면 멈추고(마치 재귀함수의 종료선언문과 같다)
            break
        elif len(scoville) == 0: #기준값을 못넘기고 마지막 값을 꺼냈다면 또 멈춘다.
            answer = -1
            break
        min2 = heapq.heappop(scoville)
        new_scoville = min1 + 2 * min2
        heapq.heappush(scoville, new_scoville)
        answer += 1
    return answer

알고리즘의 시간 복잡도

• while문이 코드의 중심을 이루고 있다. heappop이 2회 heapapush가 1회 이루어지고 있으며 최악의 경우 while문 자체가 리스트 안의 모든 원소를 탐색하기 위해 반복되기 때문에
  전체 계산은 O(NlogN)의 시간 복잡도를 가지게 된다.

동적계획법(Dynamic Programming) 대표문제풀이 : N으로 표현

문제는 아래와 같다.
https://programmers.co.kr/learn/courses/30/lessons/42895

동적계획법(Dynamic Programming)

• 주어진 최적화 문제를 재귀적인 방식으로 보다 작은 부분 문제로 나누어 부분 문제를 풀어, 이 해를 조합하여 전체 문제의 해답에 이르는 방식
• 알고리즘의 진행에 따라 탐색해야할 범위를 동적으로 결정함으로써 탐색 범위를 한정할 수 있다.
• 피보나치 수열과 knapsack problem이 동적계획법을 적용한 대표적인 예이다.

문제 해석, 예제 패턴 분석

• N = 5
  number = 12
  return 4

동적계획법을 사용한 알고리즘의 구상

• N을 한 번 사용해서 만들 수 있는 수(들) -> A1
  N을 두 번 사용해서 만들 수 있는 수(들) -> A2
  N을 세 번 사용해서 만들 수 있는 수(들) -> A3
  .
  .
  .
  N을 n-1 번 사용해서 만들 수 있는 수(들) -> An-1

• 위 예시를 통해 N을 n 번 사용해서 만들 수 있는 수들은 그 전까지의 값들을 모두 안다는 가정하에, N을 1번 사용한 A1 부터 n-1번 사용한 An-1까지를 각각 대응하는 An-1부터 A1까지를 사칙연산으로 계산해주는 경우의 수 + 1(N을 n번 나열한 숫자)이 된다는 것을 알 수 있다.

구상한 알고리즘의 복잡도

• 숫자의 사용 횟수가 늘어남에 따라 만들어지는 경우의 수가 늘어난다. 문제에서 제한한 최대의 사용 횟수인 8의 경우 만들어지는 경우의 수는 11,853,949개가 된다고 한다. 하지만 실제 실행에서는 set를 활용하여 겹치는 것을 고려하지 않기 때문에 최대 경우의 수를 모두 고려하는 경우는 생기지 않는다.

코드 구현

def solution(N, number):
    if N == number:
        return 1
    s = [set() for x in range(8)]
    for i, x in enumerate(s, start=1):
        x.add(int(str(N) * i))
        
    for i in range(1, 8):
        for j in range(i):
            for op1 in s[j]:
                for op2 in s[i - j - 1]:
                    s[i].add(op1 + op2)
                    s[i].add(op1 - op2)
                    s[i].add(op1 * op2)
                    if op2 != 0:
                        s[i].add(op1 // op2)
        if number in s[i]:
            answer = i + 1
            break
    else:
        answer = -1
        
    return answer

알고리즘의 시간 복잡도

• 시간 복잡도는 입력값에 상관없이 최악의 경우에 8번의 계산으로 정해져 있기 때문에 O()표기법으로 따로 구하지는 않는다.

깊이/너비 우선탐색(DFS/BFS) 대표 문제 풀이 : 여행경로

문제는 아래와 같다.
https://programmers.co.kr/learn/courses/30/lessons/43164

배경지식

• 그래프
  정점(vertex, node)과 간선(edge, link)
  유향(directed)그래프와 무향(undirected)그래프
  스택과 큐에 대한 지식이 필요

깊이 우선 탐색(DFS; Depth First Search)

• 노드의 아래, 자식 노드를 다 탐색한 후 옆으로, 형제 노드를 탐색하는 탐색법
  스택을 이용해서 방문한 노드와 방문할 노드를 기억하는 알고리즘이다.

너비 우선 탐색(BFS; Breadth First Search)

• 한 정점에서 인접한 모든 정점을 방문하고, 방문한 각 인접 정접을 기준으로 또다시 너비 우선 탐색을 행하는 알고리즘
  형제 노드 우선 탐색 방법이다.
  큐를 이용해서 진행하는 알고리즘이다.

문제 해석, 예제 패턴 분석

• tickets [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]
  return ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]
  문제는 한 붓 그리기와 같다. 다만 문제는 최소거리로서 더 빠른 알파벳 순으로 공항을 정렬하는 경우를 제한 조건으로 두었다. 문제가 요구하는 것은 모든 정점을 방문하는 것이 아니고, 모든 간선을 거치는 것이다.

알고리즘의 구상

• 스택을 이용해서 재귀적인 '한 붓 그리기' 로 접근하여 DFS를 응용하여 문제를 해결한다. dict를 활용해서 방향이 있는 간선을 구현한다. 위 예제에서는 ICN : [ATL, SFO], ATL : [ICN, SFO], SFO : [ATL]와 같이 작성할 수 있다.

코드 구현

def solution(tickets):
    routes = {}
    for t in tickets:
        routes[t[0]] = routes.get(t[0], []) + [t[1]]
    print(routes)
    for r in routes:
        routes[r].sort(reverse=True)
    
    stack = ['ICN']
    path = []
    while len(stack) > 0:
        top = stack[-1]
        if top not in routes or len(routes[top]) == 0
            path.append(stack.pop())
        else:
            stack.append(routes[top][-1])
            routes[top] = routes[top][:-1]
            
    return path[::-1]

알고리즘의 복잡도

• 정렬된 딕셔너리를 활용하여 탐색 자체가 상수의 시간이 걸리므로 알고리즘의 시간 복잡도는 정렬의 시간 복잡도인 O(NlogN)으로 수렴하게 된다.