코딩테스트 연습문제

---

힙(heap) - 더 맵게

힙은 이진트리의 한 종류로 루트노드가 언제나 최댓값또는 최솟값을 가집니다.

day2에서 배운 힙을 이용한 코딩문제에요!

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.(자세한 내용은 밑에 링크에!)
https://school.programmers.co.kr/learn/courses/30/lessons/42626

문제 풀이

• 알고리즘의 복잡도 리스트로 문제를 풀었을 때 알고리즘의 시간 복잡도는 최악의 경우 수 가 하나 남을 때까지 섞어야 하는 경우(n-1)
  각 단계(섞는일)에서 요구되는 계산량은 정렬된 리스트에 순서 맞추어 원소를 삽입한다. O(n)
  총 계산량 O(n^2)

보다 나은 방법을 위해 힙 연산을 사용했습니다.

import heapq as hq

def solution(scoville, K):

    hq.heapify(scoville)#힙 생성
    answer = 0
    while True:
        first = hq.heappop(scoville)#힙의 첫 번째 데이터 꺼냄
        if first >= K:#K보다 크면 반복문 종료
            break
        if len(scoville) == 0:#힙 안의 원소 다 섞었을 때도 안 만들어졌으면 -1반환
            return -1
        second = hq.heappop(scoville)
        hq.heappush(scoville, first + second*2)
        answer += 1#섞을 때마다 +1

    return answer

동적계획법(Dynamic Programming) - N으로 표현

---

동적계획법이란 주어진 최적화 문제를 재귀적인 방식으로 적운 부분 문제로 나누어 부분 문제를 풀어 이 해를 조합하여 전체 문제의 해답을 이루는 방식

📒동적계획법은 알고리즘의 진행에 따라 탐색해야 할 범위를 동적으로 결정함으로써 탐색 범위를 한정할 수 있습니다.

문제풀이

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.
자세한 내용은 밑에 링크에
https://school.programmers.co.kr/learn/courses/30/lessons/42895

def solution(N, number):
    s = [set() for x in range(8)]#숫자 사용횟수 최대 8번
    for i, x in enumerate(s, start=1):
        x.add(int(str(N)*i))
    for i in range(len(s)):#i=0일 때는 N을 한번만 사용하고 사칙연산을 적용하지 않은 경우
        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]:#경우의 수를 저장한 set에서 number이 존재하면 i+1
            answer = i+1
            break
    else:#없으면 -1반환
        answer = -1
    return answer

한 번 반복해서 사용했을 때의 경우의수를 만들고 이를 통해 2번 반복했을 때의 모든 경우의 수, 이걸 점점 늘려나가며 N번 반복했을 때의 모든 경우의 수를 set을 통해 중복 없이 저장한 후에 number이 존재하면 반환을 하고 없으면 -1을 반환하게 하였습니다.

DFS/BFS - 여행경로

---

DFS 한 정점에서 인접한(아직 방문하지 않은)정점을 방문하되, 각 인접 정점을 기준으로 깊이 우선 탐색을 끝낸 후 다음 정점을 진행

BFS 한 정점에서 인접한(아직 방문하지 않은)정점을 방문하고, 방문한 각 인접 정점을 기준으로(방문한 순서에 따라_ 또 다시 너비 우선 탐색을 행함

문제풀이

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.
자세한 내용은 밑에 링크에
https://school.programmers.co.kr/learn/courses/30/lessons/43164

def solution(tickets):
    routes = {}
    for t in tickets:
        routes[t[0]] = routes.get(t[0],[])+[t[1]]
    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(n)의 시간 복잡도를 가지고 힙을 이용했을 때 힙의 push는 O(logn)의 시간 복잡도를 가져 더 시간적인 효율을 가져갈 수 있다는 것을 깨달았습니다.