ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.

지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.

위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다. 아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.

• 첫 번째 방법은 11개의 칸을 지나서 상대 팀 진영에 도착했습니다.

• 두 번째 방법은 15개의 칸을 지나서 상대팀 진영에 도착했습니다.

위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다.

만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.

게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.

나의 풀이( 다익스트라 활용 )

import collections
import heapq
def solution(maps):
    n , m = len(maps) , len(maps[0])
    big_map = [0] * (n+2) * (m+2)
    cur_list = []
    cursor = m + 3
    start , fin = [m+3 , (n+2)*(m+2) - m - 4]

    # 7*7 행렬제작 후 기존 maps에 한겹 더 둘러싸기
    for i in range(len(maps)):
        for j in maps[i]:
            cur_list.append(cursor)
            big_map[cursor] = j
            cursor +=1
        cursor += 2

    # 그래프 인접 리스트 구성
    graph = collections.defaultdict(list)
    for k in cur_list:
        if big_map[k] == 1:
            if big_map[k-(m+2)] == 1:  # 상
                graph[k].append(k-(m+2))
            if big_map[k-1] ==1 :  # 좌
                graph[k].append(k-1)
            if big_map[k+1] == 1:  # 우
                graph[k].append(k+1)
            if big_map[k+m+2] == 1: # 하
                graph[k].append(k+m+2) 

    # 큐 변수: [(거리, 정점)]
    Q = [(1,start)]

    dist = collections.defaultdict(int)

    # 우선순위 큐 최솟값 기준으로 도착점까지 최소 거리 판별
    while Q:
        result, node = heapq.heappop(Q)
        if node == fin:
            return result

        if node not in dist:
            dist[node] = result
            for v in graph[node]:
                alt = result + 1
                heapq.heappush(Q,(alt,v))

    return -1

• 일단 기본 제공된 maps에서 한겹을 더 둘러싼 0으로 이루어진 직사각형을 만들었다. 그리고 maps의 값들을 중간에 배치시켰다. ( 0 으로 한바퀴 감싸도록 )

• 그리고 n * m 개의 직사각형의 각각의 칸이 노드라고 생각하고 그래프 인접 리스트를 제작했다. 1이 있는 곳만 갈 수 있는 지점이라 간주하고 딕셔너리를 만들었다. (defaultdict 이용)

• 다익스트라 알고리즘을 활용하여 최단경로를 구했다.

• dist라는 딕셔너리를 활용해 이미 최단거리로 갔던 노드(칸)은 다시 방문하지 않도록 설정했고, 만약 정점이 원하는 도착지와 일치하면 그때의 최소값을 return하도록 설정했다.

• 그리고 while문이 종료되도록 도착하지 못하면, 목적지로 도착할 수 없는 것이므로 -1을 리턴했다.

최단 경로 문제는 각 간선의 가중치 합이 최소가 되는 두 정점(또는 노드) 사이의 경로를 찾는 문제다.

다익스트라 알고리즘

항상 노드 주변의 최단 경로만을 택하는 대표적인 그리디(Greedy) 알고리즘 중 하나로, 단순할 뿐만 아니라 실행 속도 또한 빠르다. 다익스트라 알고리즘은 노드 주변을 탐색할때 BFS를 이용하는 대표적인 알고리즘이다.

쉽게 설명하자면 DFS 는 미로를 한 사람이 찾아 헤매는 과정이고 BFS는 여러 명의 사람이 각기 서로 다른 갈림길로 흩어져서 길을 찾는 것이다. 이때 다익스트라 알고리즘은 먼저 도착한 사람의 실뭉치를 사용해 탈출구를 찾아 나가는 것이다.

문제 1. 네트워크 딜레이 타임

K부터 출발해 모든 노드가 신호를 받을 수 있는 시간을 계산하라. 불가능할 경우 -1을 리턴한다. 입력값(u,v,w)는 각각 출발지, 도착지, 소요 시간으로 구성되며, 전체 노드의 개수는 N으로 입력받는다.

ex)

• 입력 : times = [ [2,1,1],[2,3,1],[3,4,1]], N = 4 , K = 2
• 출력 : 2

다익스트라 알고리즘 구현을 이용한 풀이

import collections
import heapq
def networkDelayTime(times,N,K):
    graph = collections.defaultdict(list)
    # 그래프 인접 리스트 구성
    for u , v , w in times:
        graph[u].append((v,w))

    # 큐 변수 : [(소요 시간, 정점)]
    Q = [(0,K)]
    dist = collections.defaultdict(int)

    # 우선순위 큐 최솟값 기준으로 정점까지 최단 경로 삽입
    while Q:
        time, node = heapq.heappop(Q)
        if node not in dist:
            dist[node] = time
            for v, w in graph[node]:
                alt = time + w
                heapq.heappush(Q,(alt,v))

    # 모든 노드의 최단 경로 존재 여부 판별
    if len(dist) == N:
        return max(dist.values())
    return -1

• graph 는 현재 노드의 소요시간과 도착가능한 노드를 입력한 딕셔너리이다. Q는 처음 입력받은 정점인 K에서 시작하고 소요시간이 기본으로 0이기 때문에 (0,K)를 넣고 시작한다.

• heap을 통해 시간이 제일 적게 걸리는 도착지를 탐색하고 그때의 노드가 dist 딕셔너리에 있다면 그 값은 이미 최단 경로이고, 그 값은 버리게 된다. 만약 dist에 존재하지 않는다면 바로 dist값으로 time과 node의 순서가 바뀌면서 입력된다. (dist는 최소값부터 세팅되기 때문에 처음 입력값이 최솟값이다.)

• dist 딕셔너리의 키 개수가 N과 동일한지 체크하는 이유는, 전체 노드 개수만큼 dist에 있다면 모든 노드의 최단 경로를 구했다는 뜻이고 모두 시작점에서 도달 가능하다는 의미이기 때문이다. 노드가 하나라도 없으면 방문하지 않은 노드가 있는 것이므로 -1 을 리턴한다.

문제 2. K 경유지 내 가장 저렴한 항공권

시작점에서 도착점까지의 가장 저렴한 가격을 계산하되, K개의 경유지 이내에 도착하는 가격을 리턴하라. 경로가 존재하지 않을 경우 -1을 리턴한다.

ex)

• 입력 : n = 3 , edges = [[0,1,100],[1,2,100],[0,2,500]] , src = 0 , dst = 2, K = 0
• 출력 : 500

다익스트라 알고리즘 응용

import collections
import heapq
def findCheapestPrice(n,flights,src,dst,K):
    graph = collections.defaultdict(list)
    #그래프 인접 리스트 구성
    for u,v,w in flights:
        graph[u].append((v,w))

    # 큐 변수: [(가격, 정점, 남은 가능 경유지 수)]
    Q = [(0,src,K)]

    # 우선순위 큐 최솟값 기준으로 도착점까지 최소 비용 판별
    while Q:
        price,node,k = heapq.heappop(Q)
        if node == dst:
            return price

        if k>= 0 :
            for v, w in graph[node]:
                alt = price + w
                heapq.heappush(Q,(alt,v,k-1))

    return -1

• 앞서 사용했던 알고리즘과 비슷한 구조로 진행이 된다.

• 방문할 수 있는 경유지 수 k가 while문이 한번 진행될 때 마다 1씩 감소하고 k<0 이 되면 heappush 를 그만한다. ( 즉, 탐색을 중단한다. ) 그리고 while문에서 중간에 리턴이 일어나지 않을 시 K개의 경유지 내에 방문이 불가한 것이므로 -1을 리턴한다.

• node와 dst가 같을 때, 가격을 리턴하는데 heap에 의해 가격의 최소값이 출력된다.

• 밑에 예시를 본다면, 경유지 수에 따른 차이를 알 수 있다.

findCheapestPrice(3,[[0,1,100],[1,2,100],[0,2,500]],0,2,1)

500

findCheapestPrice(3,[[0,1,100],[1,2,100],[0,2,500]],0,2,1)

200

모든 부분 집합을 리턴하라.

트리의 모든 DFS 결과

def subsets(nums):
    result = []

    def dfs(index, path):
        # 매번 결과 추가
        result.append(path)

        #경로를 만들면서 DFS
        for i in range(index, len(nums)):
            dfs(i+1 , path + [nums[i]])

    dfs(0,[])
    return result

• 경로 path를 만들어 나가면서 인덱스를 1씩 증가하는 형태로 깊이 탐색하는 방법이다.
• 별도의 종료조건은 없다.
• path의 결과를 매번 result 리스트에 추가시켜 모든 부분집합을 구할 수 있다.

문제 7. 일정 재구성

[from, to]로 구성된 항공권 목록을 이용해 JFK에서 출발하는 여행 일정을 구성하라. 여러 일정이 있는 경우 사전 어휘 순으로 방문한다.

ex )

• 입력 : [ [ "MUC" , "LHR" ] , ["JFK" , "MUC" ] , [ "SFO" , "SJC" ] , ["LHR" , "SFO" ] ]

• 출력 : ["JFK" , "MUC" , "LHR" , "SFO" , "SJC" ]

DFS로 일정 그래프 구성

import collections
def findItinerary(tickets):
    graph = collections.defaultdict(list)
    #그래프 순서대로 구성
    for a,b in sorted(tickets):
        graph[a].append(b)

    route = []
    def dfs(a):
        # 첫 번째 값을 읽어 어휘 순으로 방문
        while graph[a]:
            dfs(graph[a].pop(0))
        route.append(a)

    dfs('JFK')
    #다시 뒤집어 어휘 순 결과로
    return route[::-1]

• 이 문제에서 주의할 점은 여러 일정이 겹칠 때, 알파벳 오름차순을 기준으로 먼저 방문하는 점이다.

• 일단 출발지가 key이고 도착지가 value인 딕셔너리를 제작한다. defaultdict을 통해 실제 딕셔너리에 key가 없는 값을 append해도 list를 디폴트로 생성해준다.

• 첫번째 넣는 입력 값을 'JFK'로 하고 DFS를 작동시키면, 딕셔너리에서 key가 JFK인 값의 value를 출력하고 또 이어서 그 value가 key에 해당하는 값의 value를 DFS 하고 반복하면서 graph가 빈 딕셔너리가 될 때 까지 반복한다.

• 하지만 이때 route에 append 되는 순서는 가장 최근 방문지부터 추가되고 마지막으로 JFK가 추가되므로 route[::-1]로 뒤집어 주면 우리가 원하는 결과를 얻을 수 있다.

스택 연산으로 큐 연산 최적화 시도

import collections
def findItinerary(tickets):
    graph = collections.defaultdict(list)
    #그래프 순서대로 구성
    for a,b in sorted(tickets,reverse=True):
        graph[a].append(b)

    route = []
    def dfs(a):
        # 첫 번째 값을 읽어 어휘 순으로 방문
        while graph[a]:
            dfs(graph[a].pop())
        route.append(a)

    dfs('JFK')
    #다시 뒤집어 어휘 순 결과로
    return route[::-1]

• pop(0) 함수는 pop() 에 비해 비효율적이므로, 처음 딕셔너리를 저장할때 사전어휘순의 내림차순으로 append를 하고 dfs함수에서 pop()를 통해 마지막 값부터 빼는 방식이다.

• 리스트가 크다면 효율성의 개선이 이루어 질 것이다.( pop(0) : O(1) , pop(): O(n) )

일정 그래프 반복

import collections
def findItinerary(tickets):
    graph = collections.defaultdict(list)
    #그래프 순서대로 구성
    for a,b in sorted(tickets):
        graph[a].append(b)

    route, stack = [] , ['JFK']

    while stack:
        # 반복으로 스택을 구성하되 막히는 부분에서 풀어내는 처리
        while graph[stack[-1]]:
            stack.append(graph[stack[-1]].pop(0))
        route.append(stack.pop())

    #다시 뒤집어 어휘 순 결과로
    return route[::-1]

• DFS 대신 stack을 통해 반복하는 방식이다. 안에 있는 while문은 graph 딕셔너리의 stack의 마지막 값의 value 리스트가 비어있을 때까지 진행하게 된다.

• stack에는 가장 최근 방문지가 append 되고 route에 저장되면서 빠지게 된다.

• 이 풀이도 마찬가지로 경로가 거꾸로 저장되어 있으므로 route[::-1]을 리턴한다.

문제 8. 코스 스케줄

0을 완료하기 위해서는 1을 끝내야 한다는 것을 [0,1] 쌍으로 표현하는 n개의 코스가 있다. 코스 개수 n과 이 쌍들을 입력으로 받았을 때 모든 코스가 완료 가능한지 판별하라.

ex)

• 입력 : 2 , [[1,0]]

• 출력 : true

• 2개의 코스가 있으며, 1을 완료하기 위해 0을 끝내면 된다. 따라서 가능하다.

• 입력 : 2 , [[1,0],[0,1]]

• 출력 : false

• 2개의 코스가 있으며, 1을 완료하기 위해 0을 끝내면 된다. 하지만 0을 끝내기 위해서는 1을 끝내야 한다. 따라서 불가능하다.

DFS로 순환 구조 판별

def canFinish(numCourses,prerequisites):
    graph = collections.defaultdict(list)

    #그래프 구성
    for x,y in prerequisites:
        graph[x].append(y)

    traced = set()

    def dfs(i):
        # 순환 구조이면 False
        if i in traced:
            return False

        traced.add(i)
        for y in graph[i]:
            if not dfs(y):
                return False
        #탐색 종료후 순환 노드 삭제
        traced.remove(i)

        return True

    # 순환 구조 판별
    for x in list(graph):
        if not dfs(x):
            return False

    return True

• 이 문제는 그래프가 순환구조인지를 판별하는 문제이다. ( 순환구조면 다시 제자리로 맴돌게 되므로 처리할 수 없다. )

• 이전 문제와 마찬가지로 defaultdict을 활용해 기본값이 존재하는 딕셔너리를 만들어 준다.

• 순환구조를 판별하기 위해 이미 방문했던 노드를 traced 변수에 저장한다. 이미 방문했던 곳을 중복 방문하게 된다면 순환 구조로 간주할 수 있고, 이 경우 False를 리턴하고 종료하면 된다.

• traced 는 중복값을 가지지 않으므로 set() 자료형을 활용한다. 그리고 탐색 종료 후 순환 노드를 꼭 삭제해야한다. 만약 하지 않으면 자식 노드 입장에서 순환이라고 잘못 판단할 여지가 생기기 때문이다.

• 결국 DFS 함수인 dfs() 에서 현재 노드가 이미 방문했던 노드 집합인 traced에 존재한다면 순환 구조 이므로 False를 리턴하는 방법이다.

가지치기를 이용한 최적화

def canFinish(numCourses,prerequisites):
    graph= collections.defaultdict(list)
    # 그래프 구성
    for x,y in prerequisites:
        graph[x].append(y)

    traced = set()
    visited = set()

    def dfs(i):
        # 순환 구조이면 False
        if i in traced:
            return False
        # 이미 방문했던 노드이면 False
        if i in visited:
            return True

        traced.add(i)
        for y in graph[i]:
            if not dfs(y):
                return False

        #탐색 종료 후 순환 노드 삭제
        traced.remove(i)
        # 탐색 종료 후 방문 노드 추가
        visited.add(i)

        return True

    #순환 구조 판별
    for x in list(graph):
        if not dfs(x):
            return False

    return True

• 효율성을 높이기 위해, 한 번 방문했던 그래프는 두 번 이상 방문하지 않도록 무조건 True를 리턴하는 구조로 개선했다.

• visited 라는 방문했던 곳을 담는 set()을 만든 후 겹치면 바로 True를 리턴하도록 했다.

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3 
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

나의 풀이

def solution(numbers, target):
    result = 0

    def dfs(index, path, total ):
        nonlocal result
        if path == len(numbers) :
            if total == target:
                result +=1 
            return

        for j in [-1,1]:
            dfs( index+1 , path+1 , total + (j * numbers[index]) )

    dfs(0,0,0)

    return result

• 깊이 우선 탐색(DFS) 를 활용한 풀이를 진행했다.

• index를 하나씩 더하면서 재귀문을 반복시켰는데, 한번의 dfs 함수 안에 numbers[index] 값을 +로 한번, -로 한번 더해줌으로써 모든 경우의 수를 계산할 수 있었다.

• 그 후, 만약 + - 를 통해 더한 값이 target과 일치할 경우 result의 값을 1 더해줌으로서 target과 일치하는 결과의 수를 세었다.

2에서 9까지 숫자가 주어졌을 때 전화 번호로 조합 가능한 모든 문자를 출력하라.

• 입력 : "23" -> 출력 : ["ad", "ae", "af", "bd", "be", "bf" , "cd", "ce", "cf"]

풀이 - 모든 조합 탐색

def letterCombinations(digits):
    def dfs(index, path):
        # 끝까지 탐색하면 백트래킹
        if len(path) == len(digits):
            result.append(path)
            return

        # 입력값 자릿수 단위 반복
        for i in range(index, len(digits)):
            # 숫자에 해당하는 모든 문자열 반복
            for j in dic[digits[i]]:
                dfs(i+1 , path + j)

    # 예외 처리
    if not digits:
        return []

    dic = { "2": "abc", "3":"def","4":"ghi","5":"jkl",
          "6":"mno","7":"pqrs","8":"tuv","9":"wxyz"}
    result = []
    dfs(0,"")

    return result

입력 : 23

실행결과

["ad", "ae", "af", "bd", "be", "bf" , "cd", "ce", "cf"]

• 모두 조합하는 형태로 전체를 탐색한 후 백트래킹하면서 결과를 조합할 수 있다.
• 이 함수에서 digits는 입력값이며, 각 자릿수에 해당하는 키판 배열을 DFS로 탐색하면 결과가 완성된다.

문제 3. 순열

서로 다른 정수를 입력받아 가능한 모든 순열을 리턴하라.

• 입력 : [1,2,3]
• 출력 : [ [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] ]

풀이 1 . DFS를 활용한 순열 생성

def permute(nums):
    results = []
    prev_elements = []

    def dfs(elements):
        #리프 노드일 때 결과 추가
        if len(elements) == 0 :
            results.append(prev_elements[:])
        # 순열 생성 재귀 호출
        for e in elements:
            next_elements = elements[:]
            next_elements.remove(e)

            prev_elements.append(e)

            dfs(next_elements)
            prev_elements.pop()

    dfs(nums)

    return results

• elements 의 원소가 하나도 남지 않았을 떄의 prev_elements를 results 리스트에 추가시키는 조건을 DFS 함수의 제일 처음에 놓는다.
• 그 후 재귀를 활용해 모든 조합의 순열을 구해주면 된다.

풀이 2. itertools 모듈 사용

import itertools
def permute(nums):
    return list( map( list , itertools.permutations(nums)))

• itertools 모듈에는 순열을 구하는 함수가 내장되어 있기 때문에 호출해서 사용할 수 있다.

문제 4. 조합

전체 수 n을 입력받아 k개의 조합을 리턴하라. ex)

• 입력 : n = 4 , k = 2
• 출력 : [ [2,4],[3,4],[2,3],[1,2],[1,3],[1,4], ]

DFS로 k개 조합 생성

def combine(n,k):
    results = []

    def dfs(elements, start, k):
        if k == 0:
            results.append(elements[:])

        # 자신 이전의 모든 값을 고정하여 재귀 호출
        for i in range(start, n+1):
            elements.append(i)
            dfs(elements, i+1 , k-1)
            elements.pop()

    dfs([],1,k)
    return results

• 순열에서는 자기 자신을 제외하고 모든 요소를 next_elements로 처리했으나, 조합에서는 자기 자신뿐만 아니라 앞의 모든 요소를 배제하고 next_elements를 구성한다.

• 그 후 재귀를 활용해 DFS로 모든 조합을 구해주면 된다.

itertools 모듈 사용

def combine(n,k):
    return list(map(list, itertools.combinations(range(1,n+1), k )))

• 순열과 마찬가지로 조합 또한 itertools 모듈에 내장되어 있는 함수가 있다.

문제 5. 조합의 합

숫자 집합 candidates를 조합하여 합이 target이 되는 원소를 나열하라. 각 원소는 중복으로 나열 가능하다.

ex)

• 입력 : candidates = [2,3,6,7] , target = 7
• 출력 : [ [7] , [2,2,3] ]

DFS로 중복 조합 그래프 탐색

def combinationSum(candidates,target):
    result = []

    def dfs(csum, index, path):
        #종료 조건
        if csum < 0 :
            return
        if csum == 0:
            result.append(path)
            return

        # 자신 부터 하위 원소 까지의 나열 재귀 호출
        for i in range(index, len(candidates)):
            dfs(csum - candidates[i], i, path + [candidates[i]])

    dfs(target, 0 , [])
    return result

• target 숫자에 하나씩 원소를 빼면서 DFS를 통해 모든 조합의 수를 계산해보며 csum (target이 입력되고 원소를 하나씩 빼고있는 변수) 이 0보다 작아지거나 0이되면 종료조건을 발동시킨다.

• csum 이 0이 되는경우는 조건을 제대로 찾은 것이기 때문에 path를 result에 추가시킨다.

• 순열의 합으로 문제를 해결하고 싶다면 dfs 안에 재귀문 dfs에 두번째 입력값(index)를 i 대신 0 을 넣으면 된다.

• 이를 통해 중복 조합의 합으로 만들 수 있는 target 의 조합을 구할 수 있다.

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

• 예시

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 ( 다리의 길이 ) bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

제한 사항

• 모든 트럭의 길이는 1이고, 1초에 1만큼 이동합니다.
• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

테스트 케이스

나의 풀이

import collections
def solution(bl, wei, tw):
    stack = collections.deque()
    truck = collections.deque(tw)
    time = collections.deque()
    count, total = 0, 0 

    while total >= 0 :
        if len(time)>0 and time[0] == 0 :
            time.popleft()
            total -= stack.popleft()

        count += 1

        if len(truck) != 0:
            a = truck[0]
        else:
            a = wei + 1 

        if total + a <= wei:
            truck.popleft()
            total += a
            stack.append(a)
            time.append(bl)

        for i in range(len(time)):
                time[i] -= 1

        if len(time) == 0 & (not truck) :
            total -= 1

    return count

• deque 를 활용한 stack 방법 풀이이다.

• 변수 설명: stack - 다리위에 있는 트럭을 나타내는 데크 truck - 다리에 아직 오르지 않은 대기중인 트럭의 데크 time - 다리 위에 있는 트럭의 다리를 건너는데 남은 시간의 데크 total - 현재 다리 위의 총 무게 count - 총 걸린 시간

• 기본 형식은 while 문을 활용하는데 total >= 0 일 때 작동하는 조건을 걸었다. 그리고 truck 데크의 값이 없고, 다리 위에 남아있는 트럭도 없으면 total 에 -1 을 더해서 조건문을 빠져나왔다.

• while문은 1초가 지날때마다 한번씩 돌아가도록 설정되어있고 (count 를 1씩 더해줌), 트럭은 1초에 1씩 움직이므로 time 데크의 모든 값들은 while문이 한번 진행될 때마다 1씩 뺀다.

• time 데크의 첫값이 0이 된다면, time 과 stack의 첫번째 값을 popleft() 를 통해 제거해주고 total에도 그 첫번째 값만큼 빼준다.

• 그러므로 조건문이 끝났을 때의 count 값은 총 걸린 시간이 된다.

객체의 일부 쌍들이 '연관되어' 있는 객체 집합 구조

그래프 이론의 시작에는 대표적으로 오일러 경로와 해밀턴 경로가 있다.

• 오일러 경로는 정점과 그 정점들을 잇는 간선이 존재하고 모든 간선을 한번씩 지나는 경로를 뜻한다. 우리나라에서는 어렸을 때 주로 했던 '한붓그리기'라고 생각하면 쉽다.

• 해밀턴 경로는 각 정점을 한 번씩 방문하는 무향 또는 유향 그래프 경로를 말한다.

• 오일러 경로와 해밀턴 경로의 차이점을 들자면, 오일러 경로는 간선을 기준으로 하고 해밀턴 경로는 정점을 기준으로 한다는 점이다.

코딩 테스트를 진행할 때 대부분의 그래프 탐색은 DFS( 깊이 우선 탐색, Depth-First Search )를 주로 사용할 예정이다.

그래프를 표현하는 방법에는 인접 리스트와 인접 행렬이 있다. 인접 리스트로 표현하면 파이썬의 딕셔너리 자료형으로 나타낼 수 있다.

<예시 그래프 >

DFS ( 깊이 우선 탐색 )

일반적으로 DFS 는 스택으로 구현하며, 재귀를 이용하면 좀 더 간단하게 구현할 수 있다. 코딩 테스트 시에도 재귀 구현이 더 선호되는 편이다.

재귀 구조로 표현

graph = {
    1:[2,3,4],
    2:[5],
    3:[5],
    4:[],
    5:[6,7],
    6:[],
    7:[3],
    }



# 정점 v의 모든 인접 유향 간선들을 반복
def recursive_dfs(v,discovered=[]):
    discovered.append(v)
    for w in graph[v]:
        if not w in discovered:
            discovered = recursive_dfs(w,discovered)
    return discovered

예시 그래프 실행 f'recursive dfs:{recursive_dfs(1)}'

예시 그래프 DFS 결과

'recursive dfs: [1,2,5,6,7,3,4]'

• graph 는 예시 그래프를 인접 리스트로 표현한 것이다.
• DFS 수도코드를 파이썬 버전으로 바꾼 방식이다.
• 탐색이 총 3번에 걸쳐 진행됐는데, 1->2->5->6 까지 진행하고 , 되돌아 갔다가 7->3 , 다시 도될아 나가 마지막으로 4 를 탐색하는 결과가 도출되었다.

스택을 이용한 반복 구조로 구현

def iterative_dfs(start_v):
    discovered= []
    stack = [start_v]
    while stack:
        v = stack.pop()
        if v not in discovered:
            discovered.append(v)
            for w in graph[v]:
                stack.append(w)

    return discovered

f'iterative dfs:{iterative_dfs(1)}'

'iterative dfs: [1,4,3,5,7,6,2]'

같은 DFS 인데 재귀 구조와 스택 구조가 결과가 다른 이유는 재귀 DFS 는 사전식 순서로 방문한 데 반해 반복 DFS 는 역순으로 방문했기 때문이다. 스택을 구현했기 때문에 가장 마지막에 삽입된 노드부터 꺼내서 반복하게 된다.

BFS ( 너비 우선 탐색 )

다음은 BFS를 구현해보자. BFS는 DFS에 비해 쓰임새는 적지만 최단 경로를 찾는 다익스트라 알고리즘 등에 매우 유용하게 쓰인다.

큐를 이용한 반복 구조로 구현

BFS 는 재귀를 이용해 구할 수 없고 오직 큐를 이용하는 반복 구현만 가능하다.

def iterative_bfs(start_v):
    discovered = [start_v]
    queue = [start_v]
    while queue:
        v = queue.pop(0)
        for w in graph[v]:
            if w not in discovered:
                discovered.append(w)
                queue.append(w)

    return discovered

f'iterative bfs:{iterative_bfs(1)}'

'iterative bfs: [1,2,3,4,5,6,7]'

• 1 부터 순서대로 각각의 인접 노드를 우선으로 방문하는 너비 우선 탐색이 잘 실행됐음을 확인할 수 있다.

백트래킹

백트래킹은 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되는 즉시 후보를 포기해 정답을 찾아가는 범용적인 알고리즘으로 제약 충족 문제에 특히 유용하다.

DFS 를 이야기 하면 항상 같이 나오는 백트래킹은 탐색을 하다가 더 갈 수 없으면 왔던 길을 되돌아가 다른 길을 찾는다는 데서 유래했다. 백트래킹은 DFS와 같은 방식으로 탐색하는 모든 방법을 뜻하며, 기본적으로 모두 DFS의 범주에 속한다.

백트래킹은 가보고 되돌아오고를 반복해 브루트 포스와 유사하지만 , 한번 방문 후 가능성이 없는 경우에는 즉시 후보를 포기한다는 점에서 매번 같은 경로를 방문하는 브루스 포스보다는 훨씬 효율적인 방식이다.

• 제약 충족 문제 : 수많은 제약 조건을 충족하는 상태를 찾아내는 수학 문제. ex) 스도쿠 , 십자말 풀이, 4색 문제 등등

문제 1 . 섬의 개수

1을 육지로 , 0을 물로 가정한 2D 그리드 맵이 주어졌을 때, 섬의 개수를 계산하라. ( 연결되어 있는 1의 덩어리 개수를 구하라.)

ex ) 입력 :
11110 11010 11000 00000

출력 : 1

DFS로 그래프 탐색

def numIslands(grid):
    def dfs(i,j):
        # 더 이상 땅이 아닌 경우 종료
        if i < 0 or i >= len(grid) or \
        j < 0 or j >= len(grid[0]) or \
        grid[i][j] != '1':
            return

        grid[i][j] = 0
        # 동서남북 탐색
        dfs(i+1, j)
        dfs(i-1 , j)
        dfs(i,j+1)
        dfs(i, j-1)

    count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':
                dfs(i,j)
                # 모든 육지 탐색 후 카운트 1 증가
                count += 1

    return count

• 동서남북이 모두 연결된 그래프로 가정하고 동일한 형태로 처리할 수 있으며, 네 방향 각각 DFS 재귀를 이용해 탐색을 끝마치면 1이 증가하는 형태로 육지의 개수를 파악할 수 있다.
• 먼저 중첩함수부터 설명을 하자면, 일단 땅이 아닌 경우 ( i 또는 j가 인덱스를 벗어나거나 값이 1이 아닌경우 ) 종료를 시킨다.
• 동서남북을 모두 탐색하면서 재귀호출하고 , 이렇게 재귀 호출이 백트래킹으로 모두 빠져 나오면 섬 하나를 발견한 것으로 간주한다. 이때 이미 방문했던 곳은 1이 아닌 값으로 마킹한다.
• 지금 여기서는 0으로 마킹을 했는데, 0이 아니어도 #이나 * 같은 1만 아닌 값을 넣으면 된다.
• 그리고 모든 육지 탐색 후 count 를 1 증가 시켜주면 된다.

중복 문자가 없는 가장 긴 부분 문자열의 길이를 리턴하라.

• ex ) 입력 : "abcabccbb" -> 출력 : 3 ( len(abc) -> 3 )
• ex ) 입력 : "bbbb" -> 출력 : 1

풀이 (슬라이딩 윈도우와 투 포인터로 사이즈 조절)

def lengthOfLongestSubstring(self,s):
    used={}
    max_length , start = 0,0
    for index, char in enumerate(s):
        # 이미 등장했던 문자라면 'start' 위치 갱신
        if char in used and start <= used[char]:
            start = used[char] + 1
        else:
            max_length = max(max_length, index - start + 1)

        #현재 문자의 위치 삽입
        used[char] = index

    return max_length 

• 두개의 포인터 모두 왼쪽에서 출발한다.
• 만약 char가 used 안에 있다면, 이미 등장했던 단어이므로 start 를 used 딕셔너리의 key가 char에 해당하는 value에 1을 더해 저장한다.
• 하지만 만약 처음 등장하는 단어라면, index - start + 1와 현재의 max_length 값을 비교하고 더 큰 값을 max_length 에 저장해주면 된다.
• used[char] 는 현재 문자를 키로 하는 해시 테이블이다.
• 그러므로 , start는 이미 등장했던 문자인 경우에는 왼쪽 포인터인 start를 현재 위치까지 옮기고 아닌 경우에는 현재위치 + 1 의 위치로 옮긴다.

문제 4. 상위 K 빈도 요소

k번 이상 등장하는 요소를 추출하라.

• ex ) 입력 : nums = [1,1,1,2,2,3] , k = 2 -> 출력 [1,2]

풀이 1. Counter를 이용한 음수 순 추출

import heapq
import collections
def topKFrequent( nums,k):
    freqs = collections.Counter(nums)
    freqs_heap = []
    # 힙에 음수로 삽입
    for f in freqs:
        heapq.heappush(freqs_heap , (-freqs[f],f))

    topk = list()
    #k번 만큼 추출, 최소 힙이므로 가장 작은 음수 순으로 추출

    for _ in range(k):
        topk.append(heapq.heappop(freqs_heap)[1])

    return topk

• Counter 를 이용하여 리스트 안에 있는 원소들의 개수를 세었다.
• heapq에 원소를 키/값을 바꾸어서 음수로 넣었다. 음수를 사용하면 가장 빈도 수가 높은 값이 가장 큰 음수가 된다. 그렇다면 최소 힙으로도 빈도 수가 가장 높았던 값을 추출할 수 있다.

파이썬다운 방식

def topKFrequent(nums,k):
    return list(zip(*collections.Counter(nums).most_common(k)))[0]

• zip은 여러개의 리스트를 한개의 튜플로 묶어주는 함수이다.
• • 을 통해서 언패킹해줄 수 있다.
• ex )

  fruits = ['lemon' , 'pear' ,'watermelon']
  for f in fruits:
    print(f, end=' ')

  lemon pear watermelon

print(*fruits)

lemon pear watermelon

• 같은 결과가 나오는 것을 알 수 있다.
• 그러므로 [(1,3),(2,2)] 가 [(1,2),(3,2)]로 바뀌는 것을 알 수 있다.

해시 함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수.

즉 , ABC , 1245BC , AF32B 가 있어도 해시 함수를 통해 2바이트의 고정 크기 값으로 매핑 실킬 수 있다.

해시 함수에는 저장 방법에 따라 2가지 방식으로 나눌 수 있다.

• 개별 체이닝 방식과 오픈 어드레싱 방식
• 개별 체이닝 방식은 충돌 발생시 연결 리스트를 통해 연결하는 방식.
• 오픈 어드레싱은 충돌 발생 시 탐사를 통해 빈 공간을 찾아나서는 방식.
• C++ 와 자바는 개별 체이닝 방식이고, python은 오픈 어드레싱 방식이다.
• "해시 테이블로 구현된 파이썬의 자료형은?" 바로 딕셔너리이다.

문제 1. 해시맵 디자인

다음의 기능을 제공하는 해시맵을 디자인하라.

• put(key,value) : 키, 값을 해시맵에 삽입한다. 만약 이미 존재하는 키라면 업데이트한다.
• get(key) : 키에 해당하는 값을 조회한다. 만약 키가 존재하지 않는다면 -1을 리턴한다.
• remove(key) : 키에 해당하는 키, 값을 해시맵에서 삭제한다.

개별 체이닝 방식으로 해시 테이블 구현

class ListNode:
    def __init__(self, key=None, value = None):
        self.key = key
        self.val = value
        self.next = None

class MyHashMap:
    # 초기화
    def __init__(self):
        self.size = 1000
        self.table = collections.defaultdict(ListNode)

    # 삽입
    def put(self,key):
        index = key % self.size
        #인덱스에 노드가 없다면 삽입 후 종료
        if self.table[index].value is None:
            self.table[index] = ListNode(key,value)
            return

        #인덱스에 노드가 존재하는 경우 연결 리스트 처리
        p = self.table[index]
        while p:
            if p.key == key :
                p.value = value
                return
            if p.next in None:
                break
            p= p.next
        p.next = ListNode(key,value)

    # 조회
    def get(self,key):
        index = key % self.size
        if self.table[index].value is None:
            return -1

        # 노드가 존재할 때 일치하는 키 탐색
        p = self.table[index]
        while p:
            if p.key == key:
                return p.value
            p = p.next
        return -1

    # 삭제
    def remove(self,key):
        index = key % self.size
        if self.table[index].value is None:
            return

        # 인덱스의 첫 번째 노드일 때 삭제 처리
        p = self.table[index]
        if p.key == key:
            self.table[index] = ListNode() if p.next is None else p.next
            return

        # 연결 리스트 노드 삭제
        prev = p
        while p:
            if p.key == key:
                prev.next = p.next
                return
            prev , p = p , next

• 기본 초기화 설정부터 , 조회 , 삽입 ,삭제 순으로 메서드가 정리되어있다.
• defaultdict 은 존재하지 않는 인덱스로 조회를 할 경우, 에러를 내지 않고 바로 디폴트 객체를 만들어 준다.
• 해당 인덱스에 노드가 존재하는 경우는 충돌하는 경우를 말한다.

2. 보석과 돌

J는 보석이며, S는 갖고 있는 돌이다. S에는 보석이 몇 개나 있을까? 대소문자는 구분한다.

• ex) 입력이 J="aA" , S = "aAAbbbb" 라면 3이 출력된다.

해시 테이블을 이용한 풀이

def numJewelsInStones(self, J,S):
    freqs = {}
    count = 0

    # 돌(S)의 빈도 수 계산
    for char in S:
        if char not in freqs:
            freqs[char] = 1
        else:
            freqs[char] += 1

    # 보석(J)의 빈도 수 합산
    for char in J:
        if char in freqs:
            count += freqs[char]

    return count

• J 라는 해시테이블을 만들고 , 돌의 빈도수를 계산한다.
• 돌의 빈도수는 for 문을 통해 원소의 개수를 해시테이블에 계산하는 방식이다.
• 그리고 보석만의 빈도 수를 더해주면 된다.

defaultdict를 이용한 비교 생략

def numJewelsInStones(self, J,S):
    freqs = collections.defaultdict(int)
    count = 0

    # 비교 없이 돌(S)의 빈도 수 계산
    for char in S:
        freqs[char] +=1

    # 비교 없이 보석(J)의 빈도 수 합산
    for char in J:
        count += freqs[char]

    return count

• defaultdict을 이용하면 사전에 값이 없는 경우 자동으로 디폴트 (0) 의 값이 설정된다.
• 코드가 깔끔해진다.

Counter로 계산 생략

def numJewelsInStones(self, J,S):
    freqs = collections.Counter(S) #돌 빈도 수 계산
    count = 0

    for char in J:
        count += freqs[char]

    return count

• collections.Counster() 를 사용하면 개수 계산을 손쉽고 빠르게 진행할 수 있다.

파이썬 다운 방식

def numJewelsInStones(self, J,S):
    return sum(s in J for s in S)

• 리스트 컴프리헨션으로 한 줄의 코드로 풀이가 가능하다.
• [s for s in S] 는 각 문자를 리스트화 시킨 것을 의미하고, [ s in J for s in S ] 는 각 문자를 하나씩 출력하고 J에 들어 있는지 여부를 True 혹은 False로 출력해주는 리스트 컴프리헨션이다.

라디오를 자주 듣는 네오는 라디오에서 방금 나왔던 음악이 무슨 음악인지 궁금해질 때가 많다. 그럴 때 네오는 다음 포털의 '방금그곡' 서비스를 이용하곤 한다. 방금그곡에서는 TV, 라디오 등에서 나온 음악에 관해 제목 등의 정보를 제공하는 서비스이다.

네오는 자신이 기억한 멜로디를 가지고 방금그곡을 이용해 음악을 찾는다. 그런데 라디오 방송에서는 한 음악을 반복해서 재생할 때도 있어서 네오가 기억하고 있는 멜로디는 음악 끝부분과 처음 부분이 이어서 재생된 멜로디일 수도 있다. 반대로, 한 음악을 중간에 끊을 경우 원본 음악에는 네오가 기억한 멜로디가 들어있다 해도 그 곡이 네오가 들은 곡이 아닐 수도 있다. 그렇기 때문에 네오는 기억한 멜로디를 재생 시간과 제공된 악보를 직접 보면서 비교하려고 한다. 다음과 같은 가정을 할 때 네오가 찾으려는 음악의 제목을 구하여라.

• 방금그곡 서비스에서는 음악 제목, 재생이 시작되고 끝난 시각, 악보를 제공한다.
• 네오가 기억한 멜로디와 악보에 사용되는 음은 C, C#, D, D#, E, F, F#, G, G#, A, A#, B 12개이다.
• 각 음은 1분에 1개씩 재생된다. 음악은 반드시 처음부터 재생되며 음악 길이보다 재생된 시간이 길 때는 음악이 끊김 없이 처음부터 반복해서 재생된다. 음악 길이보다 재생된 시간이 짧을 때는 처음부터 재생 시간만큼만 재생된다.
• 음악이 00:00를 넘겨서까지 재생되는 일은 없다.
• 조건이 일치하는 음악이 여러 개일 때에는 라디오에서 재생된 시간이 제일 긴 음악 제목을 반환한다. 재생된 시간도 같을 경우 먼저 입력된 음악 제목을 반환한다.
• 조건이 일치하는 음악이 없을 때에는 “(None)”을 반환한다.

입력 형식

입력으로 네오가 기억한 멜로디를 담은 문자열 m과 방송된 곡의 정보를 담고 있는 배열 musicinfos가 주어진다.

• m은 음 1개 이상 1439개 이하로 구성되어 있다.
• musicinfos는 100개 이하의 곡 정보를 담고 있는 배열로, 각각의 곡 정보는 음악이 시작한 시각, 끝난 시각, 음악 제목, 악보 정보가 ','로 구분된 문자열이다.

• 음악의 시작 시각과 끝난 시각은 24시간 HH:MM 형식이다.

• 음악 제목은 ',' 이외의 출력 가능한 문자로 표현된 길이 1 이상 64 이하의 문자열이다.

• 악보 정보는 음 1개 이상 1439개 이하로 구성되어 있다.

나의 풀이

def solution(m,musicinfos):
    music_info = []
    time = []
    music_name = []

    #악보 만들기
    for i in musicinfos:
        start , last , name , melody = i.split(',')
        # 시간 구하기 ( 분 기준으로 )
        s_hour , s_min = start.split(":")
        l_hour , l_min = last.split(":")
        total = int(l_hour) * 60 + int(l_min)-int(s_hour) * 60 - int(s_min)
        #  melody 길이와 시간 비교를 통해 총 들린 악보 구하기
        melody = melody.replace('C#','c').replace("D#","d").replace("F#","f").replace("G#","g").replace("A#","a")
        a,b = divmod(total,len(melody))
        music = melody * a + melody[:b]

        # 음악정보
        music_info.append(music)
        music_name.append(name)
        time.append(total)

    answer = []
    cc = len(music_info)
    m= m.replace("C#","c").replace("D#","d").replace("F#","f").replace("G#","g").replace("A#","a")

    # 음악 찾기
    for l in range(len(music_info)):
        cc -=1
        if m in  music_info[l]:
            answer.append([l, music_name[l],cc])
    if len(answer) == 0:
        return "(None)"
    else:
        ans = sorted(answer, key = lambda x : (time[x[0]],x[2]))
        return ans[-1][1]

• 라디오에서 방송된 음악의 멜로디, 시간, 이름을 각각의 리스트로 저장했다.
• split(',')을 통해 음악 정보를 나눈 후, 시간의 경우에는 시작의 (hour * 60 + min) 에서 종료 시간의 ( hour * 60 + min) 을 빼서 구했다.
• 멜로디는 #이 길이를 구할 때 1을 차지하므로, C# 은 c로 D#은 d로 바꾸는 등 그에 해당하는 소문자로 치환시켰다.
• 그 이후 음악을 찾을 때는 기억하는 멜로디도 # 들어간 음을 소문자로 치환시킨 후, music_info 라는 리스트의 원소에 속해있는 지 확인 후 있다면 answer 리스트에 넣었다.
• answer 리스트가 비어있다면, 해당하는 곡이 없는 것이므로 (None)을 반환시키고, 아니라면 key = lambda 를 통한 정렬을 통해, 첫번째 기준으로는 time[ x[0] ] ( 방송된 음악의 길이 ) , 두번째 기준으로는 (전체길이 - 입력된 순서)로 오름차순 설정했다. 그러므로 마지막에 있는 값이 조건에 맞는 값이다.

문제 설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다. Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

나의 풀이

import heapq
def solution(sco, k):
    heapq.heapify(sco)
    count = 0

    while (sco[0]  < k) :
        if len(sco) <= 1 :
            return -1 
        first = heapq.heappop(sco)
        second = heapq.heappop(sco)
        mix_food = first + (second * 2 )
        heapq.heappush(sco, mix_food)
        count += 1 


    return count

• 우선순위 큐에 자주 사용되는 heap을 사용한 풀이이다.
• heapq 모듈을 import해야 사용할 수 있다.
• 기본적으로 heapify 를 이용하면 하나씩 heappush를 하지 않아도, 리스트를 한번에 힙으로 변환할 수 있다.
• heap[0] - 힙의 0번째 인덱스를 조회하면 가장 작은 값이 조회된다.
• heappop 을 통해 가장 작은 값을 조회 및 팝(꺼내오기) 시킬 수 있다.
• heappush를 통해 힙에 원소를 하나씩 넣을 수 있다.
• 힙의 젤 작은 값이 K보다 작다면 계속 while 문이 돌아가고 count는 1씩 더해지는 구조이다.
• 하지만 만약 while문의 조건문을 통과했고 sco (힙) 의 길이가 1보다 같거나 작다면, 원소가 하나밖에 없으므로 더 이상 섞기를 진행하지 못하는 상태를 뜻하므로 -1을 반환시킨다.
• while문을 정상적으로 통과한다면 sco[0] >= k가 성립한 것이므로 count 를 반환한다.

1. 우유와 요거트가 담긴 바구니

CART_PRODUCTS 테이블은 장바구니에 담긴 상품 정보를 담은 테이블입니다. CART_PRODUCTS 테이블의 구조는 다음과 같으며, ID, CART_ID, NAME, PRICE는 각각 테이블의 아이디, 장바구니의 아이디, 상품 종류, 가격을 나타냅니다.

데이터 분석 팀에서는 우유(Milk)와 요거트(Yogurt)를 동시에 구입한 장바구니가 있는지 알아보려 합니다. 우유와 요거트를 동시에 구입한 장바구니의 아이디를 조회하는 SQL 문을 작성해주세요. 이때 결과는 장바구니의 아이디 순으로 나와야 합니다.

풀이

SELECT B.CART_ID FROM 
(SELECT A.CART_ID FROM CART_PRODUCTS AS A
WHERE NAME = 'Milk' OR NAME = 'Yogurt'
GROUP BY CART_ID HAVING COUNT(DISTINCT NAME)>=2) AS B
ORDER BY CART_ID

• 장바구니의 아이디를 조회를 조건이 걸려있는 서브쿼리로 부터 추출하는 것이 이 풀이의 핵심이다.
• 서브쿼리는 NAME 컬럼이 'Milk' 혹은 'Yogurt' 이고, GROUP BY를 통해 그룹화를 시켰을 때 2개 이상의 고유값을 가진 CART_ID를 조회하는 쿼리이다.
• 서브쿼리는 B 라는 이름을 가지고, 이름이 고유값 2개 이상을 가진다는 것은 우유와 요거트를 둘 다 포함한다는 의미를 가진다. ( 우유와 요거트만 조회했기 때문에 )
• 장바구니의 아이디 컬럼을 기준으로 오름차순 정렬했다.

2. 헤비 유저가 소유한 장소

PLACES 테이블은 공간 임대 서비스에 등록된 공간의 정보를 담은 테이블입니다. PLACES 테이블의 구조는 다음과 같으며 ID, NAME, HOST_ID는 각각 공간의 아이디, 이름, 공간을 소유한 유저의 아이디를 나타냅니다. ID는 기본키입니다.

이 서비스에서는 공간을 둘 이상 등록한 사람을 "헤비 유저"라고 부릅니다. 헤비 유저가 등록한 공간의 정보를 아이디 순으로 조회하는 SQL문을 작성해주세요.

풀이

SELECT ID , NAME , HOST_ID FROM PLACES
WHERE HOST_ID 
IN (SELECT  HOST_ID FROM PLACES
    GROUP BY HOST_ID HAVING COUNT(NAME) >= 2 )
ORDER BY ID

• 공간을 둘 이상 등록한 사람인 헤비 유저를 조회하는 서브쿼리를 조건절에 넣고, 그 조건에 맞는 데이터를 조회하는 풀이 방법이다.
• 서브쿼리는 HOST_ID 컬럼을 기준으로 그룹화시켰을 때, 2개 이상의 행을 가진 HOST_ID를 조회한다.
• ID를 기준으로 오름차순 정렬했다.

문제설명

ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디, 생물 종, 보호 시작일, 보호 시작 시 상태, 이름, 성별 및 중성화 여부를 나타냅니다.

ANIMAL_OUTS 테이블은 동물 보호소에서 입양 보낸 동물의 정보를 담은 테이블입니다. ANIMAL_OUTS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, NAME, SEX_UPON_OUTCOME는 각각 동물의 아이디, 생물 종, 입양일, 이름, 성별 및 중성화 여부를 나타냅니다. ANIMAL_OUTS 테이블의 ANIMAL_ID는 ANIMAL_INS의 ANIMAL_ID의 외래 키입니다.

1. 없어진 기록 찾기 (LEVEL 3)

천재지변으로 인해 일부 데이터가 유실되었습니다. 입양을 간 기록은 있는데, 보호소에 들어온 기록이 없는 동물의 ID와 이름을 ID 순으로 조회하는 SQL문을 작성해주세요.

풀이

SELECT OUTS.ANIMAL_ID, OUTS.NAME
FROM ANIMAL_OUTS AS OUTS
LEFT JOIN ANIMAL_INS AS INS
ON INS.ANIMAL_ID = OUTS.ANIMAL_ID
WHERE INS.ANIMAL_ID IS NULL

• LEFT JOIN을 통해서 ANIMAL_INS 와 ANIMAL_OUTS 테이블을 ANIMAL_ID를 기준으로 병합시켰습니다. ( ANIMAL_OUTS를 토대로 병합시킴, 그러므로 ANIMAL_OUTS의 모든 데이터가 포함되어있다. )
• 그 후 INS.ANIMAL_ID 값이 결측치인 값이 입양을 간 기록은 있는데 보호소에 들어온 기록이 없는 동물이다.
• 풀이와 같이 JOIN을 할 때, ON을 통해서 어떤 컬럼을 기준으로 병합시킬지 결정할 수 있다.
  
  

2. 있었는데요 없었습니다 (LEVEL 3)

관리자의 실수로 일부 동물의 입양일이 잘못 입력되었습니다. 보호 시작일보다 입양일이 더 빠른 동물의 아이디와 이름을 조회하는 SQL문을 작성해주세요. 이때 결과는 보호 시작일이 빠른 순으로 조회해야합니다.

풀이

SELECT INS.ANIMAL_ID , INS.NAME FROM ANIMAL_OUTS AS OUTS
INNER JOIN ANIMAL_INS AS INS
ON OUTS.ANIMAL_ID = INS.ANIMAL_ID
WHERE OUTS.DATETIME < INS.DATETIME
ORDER BY INS.DATETIME

• ANIMAL_INS 테이블과 ANIMAL_OUTS 테이블을 INNER JOIN( 교집합 ) 으로 ANIMAL_ID 를 기준으로 병합시켰다.
• 보호 시작일은 ANIMAL_INS 테이블의 DATETIME 컬럼이고, 입양일은 ANIMAL_OUTS 테이블의 DATETIME 컬럼이다. 그래서 보호시작일보다 입양일이 더 빠르다는 것은 INS.DATETIME > OUTS.DATETIME 을 뜻한다. ( 날짜는 늦을수록 큰 값을 계산됨 )
• 보호 시작일이 빠른 순으로 조회하라고 되어있으므로 , ORDER BY 를 통해 INS.DATETIME 컬럼을 오름차순으로 정렬했다.

3. 오랜 기간 보호한 동물 (LEVEL 3)

아직 입양을 못 간 동물 중, 가장 오래 보호소에 있었던 동물 3마리의 이름과 보호 시작일을 조회하는 SQL문을 작성해주세요. 이때 결과는 보호 시작일 순으로 조회해야 합니다.

풀이

SELECT INS.NAME , INS.DATETIME FROM ANIMAL_INS AS INS
LEFT JOIN ANIMAL_OUTS AS OUTS
ON INS.ANIMAL_ID = OUTS.ANIMAL_ID
WHERE OUTS.DATETIME IS NULL 
ORDER BY INS.DATETIME LIMIT 3

• 입양을 못 간 동물을 구하기 위해서, ANIMAL_INS 테이블과 ANIMAL_OUTS 테이블을 ANIMAL_ID를 기준으로 병합(LEFT JOIN)시킨 후 OUTS.DATETIME 컬럼이 비어있는 동물을 조회했다.
• 가장 오래 보호소에 있던 동물을 구하기 위해서 INS.DATETIME을 기준으로 오름차순으로 정렬했다.
• LIMIT 3 을 통해서 가장 오래 보호소에 있었던 동물 3마리를 구했다.

4. 보호소에서 중성화한 동물 (LEVEL 4)

보호소에서 중성화 수술을 거친 동물 정보를 알아보려 합니다. 보호소에 들어올 당시에는 중성화되지 않았지만, 보호소를 나갈 당시에는 중성화된 동물의 아이디와 생물 종, 이름을 조회하는 아이디 순으로 조회하는 SQL 문을 작성해주세요. (중성화를 거치지 않은 동물은 성별 및 중성화 여부에 Intact, 중성화를 거친 동물은 Spayed 또는 Neutered라고 표시되어있습니다. )

풀이

SELECT OUTS.ANIMAL_ID , OUTS.ANIMAL_TYPE , OUTS. NAME
FROM ANIMAL_OUTS AS OUTS
INNER JOIN ANIMAL_INS AS INS
ON OUTS.ANIMAL_ID = INS.ANIMAL_ID
WHERE (OUTS.SEX_UPON_OUTCOME NOT LIKE '%Intact%' )
AND (INS.SEX_UPON_INTAKE LIKE '%Intact%')

• ANIMAL_INS 테이블과 ANIMAL_OUTS 테이블을 ANIMAL_ID 를 기준으로 INNER JOIN 시켜 준 후, ANIMAL_OUTS 테이블의 SEX_UPON_OUTCOME 컬럼이 Intact 를 포함하고 있지 않은 조건과 ( Intact, Neutered, Spayed 3개 중 하나는 무조건 포함하고 있음 ) ANIMAL_INS 테이블의 SEX_UPON_INTAKE 컬럼이 Intact 조건을 둘 다 만족시키는 데이터를 찾으면 된다.
• Intact 를 포함하지 않으면 Neutered 와 Spayed 중 하나이기 때문에 중성화 수술을 한 동물임을 이용했다.

• 더블 엔디드 큐(Double-Ended Queue)의 줄임말로, 글자 그대로 양쪽 끝을 모두 추출할 수 있는, 큐를 일반화한 형태의 추상 자료형(ADT)이다.
• 데크는 양쪽에서 삭제와 삽입을 모두 처리할 수 있으며, 스택과 큐의 특징을 모두 갖고 있다.

문제 1. 원형 데크 디자인

다음 연산을 제공하는 원형 데크를 디자인하라.

• MyCircularDeque(k): 데크 사이즈를 k로 지정하는 생성자다.
• insertFront(): 데크 처음에 아이템을 추가하고 성공할 경우 true 리턴
• insertLast():데크 마지막에 아이템을 추가하고 성공할 경우 true 리턴
• deleteFront():데크 처음에 아이템을 삭제하고 성공할 경우 true 리턴
• deleteLast():데크 마지막에 아이템을 삭제하고 성공할 경우 true 리턴
• getFront():데크 첫 번째 아이템을 가져온다.데크가 비어 있다면 -1을 리턴
• getRear():데크 마지막 아이템을 가져온다.데크가 비어 있다면 -1을 리턴
• isEmpty(): 데크가 비어 있는지 여부를 판별한다.
• isFull(): 데크가 가득 차 있는지 여부를 판별한다.

이중 연결 리스트를 이용한 데크 구현 풀이

class MyCircularDeque:
    def __init__(self,k):
        self.head , self.tail = ListNode(None), ListNode(None)
        self.k, self.len = k , 0
        self.head.right , self.tail.left = self.tail, self.head

    # 이중 연결 리스트에 신규 노드 삽입
    def _add(self, node, new):
        n = node.right
        node.right = new
        new.left, new.right = node , n
        n.left = new

    def _del(self,node):
        n = node.right.right
        node.right = n
        n.left = node

    def insertFront(self,value):
        if self.len == self.k:
            return False
        self.len += 1
        self._add(self.head, ListNode(value))
        return True

    def insertLast(self,value):
        if self.len == self.k:
            return False
        self.len +=1
        self._add(self.tail.left, ListNode(value))

    def deleteFront(self):
        if self.len == 0:
            return False
        self.len -= 1
        self._del(self.head)
        return True

    def deleteLast(self):
        if self.len == 0 :
            return False
        self.len -= 1
        self._del(self.tail.left.left)
        return True

    def getFront(self):
        return self.head.right.val if self.len else -1

    def getRear(self):
        return self.tail.left.val if self.len else -1

    def isEmpty(self):
        return self.len == 0

    def isFull(self):
        return self.len == self.k

• 최대 길이 정보는 k 이고, head 와 taile 은 각각 왼쪽, 오른쪽 인덱스 역할이다.
• 현재 길이 정보를 담는 변수인 len에는 0을 담는다.
• 새로운 노드 삽입 시 최대 길이에 도달했을 때는 False를 리턴하고, 이외에는 _add() 메서드를 이용해 head 위치에 노드를 삽입한다.
• 뒤 쪽에 추가하는 insertLast() 도 같은 방법으로 진행하면 된다.
• 삭제의 경우에는 _add() 메서드를 _del() 메서드로 바꿔준다.

우선순위 큐

• 우선순위 큐는 큐 또는 스택과 같은 추상 자료형과 유사하지만 추가로 각 요소의 '우선순위'와 연관되어 있다.
• 우선순위 큐는 어떠한 특정 조건에 따라 우선순위가 가장 높은 요소가 추출되는 자료형이다. 예를 들면 최솟값을 추출하는 우선순위 큐에서는 [1,4,5,3,2] 를 넣으면 1,2,3,4,5 순으로 추출된다. ( 큐는 가장 먼저 삽입된 요소를 먼저 추출하고, 스택은 가장 나중에 삽입한 요소가 추출됨 )

문제 2. k개 정렬 리스트 병합

k개의 정렬된 리스트를 1개의 정렬된 리스트로 병합하라.

• ex ) [ 1->4->5 , 1->3->4 , 2->6 ] 이 입력된다면 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 이 출력된다. ( 여기서 k는 3이다. )

우선순위 큐를 이용한 리스트 병합

def mergeKLists(self,lists):
    root = result = ListNode(None)
    heap = []

    # 각 연결 리스트의 루트를 힙에 저장
    for i in range(len(lists)):
        if lists[i]:
            heapq.heappush(heap, (lists[i].val, i , lists[i]))

    # 힙 추출 이후 다음 노드는 다시 저장
    while heap :
        node = heapq.heappop(head)
        idx = node[1]
        result.next = node[2]

        result = result.next
        if result.next:
            heapq.heappush(heap, (result.next.val, idx, result.next))

    return root.next

• 파이썬에서는 우선순위 큐 풀이에 거의 항상 heapq 율을 사용한다.
• heappush 함수를 이용해 힙에 넣으면, heappop()으로 값을 추출했을 때 가장 작은 노드의 연결 리스트부터 차례대로 나오게 된다.

문제설명

ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디, 생물 종, 보호 시작일, 보호 시작 시 상태, 이름, 성별 및 중성화 여부를 나타냅니다.

1. 루시와 엘라 찾기 (LEVEL 2)

동물 보호소에 들어온 동물 중 이름이 Lucy, Ella, Pickle, Rogan, Sabrina, Mitty인 동물의 아이디와 이름, 성별 및 중성화 여부를 조회하는 SQL 문을 작성해주세요.

풀이

SELECT ANIMAL_ID , NAME , SEX_UPON_INTAKE FROM ANIMAL_INS
WHERE NAME IN ('Lucy','Pickle','Ella','Rogan','Sabrina','Mitty')
ORDER BY ANIMAL_ID

• 찾는 이름을 ()안에 String 형태로 넣어주고 IN 을 통해 안에 들어있는 지 확인해주면 된다.
  
  

  2. 이름에 el이 들어가는 동물 찾기 (LEVEL 2)

  보호소에 돌아가신 할머니가 기르던 개를 찾는 사람이 찾아왔습니다. 이 사람이 말하길 할머니가 기르던 개는 이름에 'el'이 들어간다고 합니다. 동물 보호소에 들어온 동물 이름 중, 이름에 "EL"이 들어가는 개의 아이디와 이름을 조회하는 SQL문을 작성해주세요. 이때 결과는 이름 순으로 조회해주세요. 단, 이름의 대소문자는 구분하지 않습니다.

풀이

SELECT ANIMAL_ID , NAME FROM ANIMAL_INS
WHERE ANIMAL_TYPE = 'Dog' AND LOWER(NAME) LIKE '%el%'
ORDER BY NAME

• 'el'이 이름의 처음, 중간,끝 모두에 들어갈 수 있으므로 %el% 를 하고 LIKE를 통해 조건절에서 단어가 들어가는지 조회한다.
• 대소문자를 구분하지 않기 때문에 이름을 전부 소문자화 시키고 비교를 진행한다.
• 마지막으로 이름순으로 오름차순 정렬해준다.

3. 중성화 여부 파악하기 (LEVEL 2)

보호소의 동물이 중성화되었는지 아닌지 파악하려 합니다. 중성화된 동물은 SEX_UPON_INTAKE 컬럼에 'Neutered' 또는 'Spayed'라는 단어가 들어있습니다. 동물의 아이디와 이름, 중성화 여부를 아이디 순으로 조회하는 SQL문을 작성해주세요. 이때 중성화가 되어있다면 'O', 아니라면 'X'라고 표시해주세요. SQL문을 실행하면 다음과 같이 나와야 합니다.

풀이

SELECT ANIMAL_ID , NAME, 
    CASE 
    WHEN
    SEX_UPON_INTAKE LIKE '%Neutered%' 
    OR SEX_UPON_INTAKE LIKE '%Spayed%' THEN 'O'
    ELSE 'X'
    END AS 중성화
FROM ANIMAL_INS

• CASE - WHEN - THEN - END 를 사용해서 문제를 풀이했다.
• SEX_UPON_INTAKE 컬럼이 'Neutered' 혹은 'Spayed'를 포함하고 있는지 조회한 후 맞으면 O를 틀리면 X를 출력하는 방법이다.
  
  

4. DATETIME에서 DATE로 형 변환 (LEVEL 2)

ANIMAL_INS 테이블에 등록된 모든 레코드에 대해, 각 동물의 아이디와 이름, 들어온 날짜1를 조회하는 SQL문을 작성해주세요. 이때 결과는 아이디 순으로 조회해야 합니다.

풀이

SELECT ANIMAL_ID , NAME , DATE_FORMAT(DATETIME,"%Y-%m-%d") FROM ANIMAL_INS
ORDER BY ANIMAL_ID

• DATE_FORMAT( , "") 를 통해 날짜 형식을 지정할 수 있다.

• 이와같은 방법으로 표현이 가능하다.
  
  

5. 오랜 기간 보호한 동물 (LEVEL 3)

ANIMAL_OUTS 테이블은 동물 보호소에서 입양 보낸 동물의 정보를 담은 테이블입니다. ANIMAL_OUTS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, NAME, SEX_UPON_OUTCOME는 각각 동물의 아이디, 생물 종, 입양일, 이름, 성별 및 중성화 여부를 나타냅니다. ANIMAL_OUTS 테이블의 ANIMAL_ID는 ANIMAL_INS의 ANIMAL_ID의 외래 키입니다.

입양을 간 동물 중, 보호 기간이 가장 길었던 동물 두 마리의 아이디와 이름을 조회하는 SQL문을 작성해주세요. 이때 결과는 보호 기간이 긴 순으로 조회해야 합니다.

풀이

SELECT ANIMAL_ID, INS.NAME FROM ANIMAL_INS AS INS
INNER JOIN ANIMAL_OUTS
USING (ANIMAL_ID)
ORDER BY DATEDIFF(ANIMAL_OUTS.DATETIME,INS.DATETIME) DESC
LIMIT 2

• 우선 ANIMAL_INS 와 ANIMAL_OUTS를 ANIMAL_ID 를 기준으로 INNER JOIN 시켜줍니다. 그렇다면 입양을 간 동물만 남게됩니다.
• 그 후 , DATEDIFF를 통해 입양간 날짜와 보호시작 날짜의 차이를 구하면 이것이 보호기간이 됩니다.
• 보호기간을 기준으로 내림차순 정렬하고 LIMIT 2를 통해 가장 보호기간이 긴 2개의 데이터를 구할 수 있습니다.

문제설명

• 매일의 화씨 온도 리스트 T를 입력받아서, 더 따뜻한 날씨를 위해서는 며칠을 더 기다려야하는지를 출력하라.

• ex) 입력 T = [73,74,75,71,69,72,76,73] -> 출력: [1,1,4,2,1,1,0,0]

스택을 이용한 풀이

def dailyTemp(T):
    answer = [0] * len(T)
    stack = []
    for i, cur in enumerate(T):
        # 현재 온도가 스택 값보다 높다면 현재 인덱스 - stack 인덱스
        while stack and cur > T[stack[-1]]:
            last = stack.pop()
            answer[last] = i - last
        stack.append(i)

    return answer

• 현재의 인덱스를 계속 스택에 쌓고, 이전보다 상승하는 지점이 나타난다면 현재 온도와 스택에 쌓아둔 인덱스 지점의 온도 차이를 비교해서 더 높다면 기존 스택의 값은 팝으로 꺼내고 현재 인덱스와 스택에 쌓아둔 인덱스의 차이를 정답으로 처리한다.
• while stack : 은 stack 리스트 안에 값이 하나라도 있을 경우 참이 된다.

문제 2. 큐를 이용한 스택 구현

큐

• 큐는 FIFO(선입선출) 로 처리되는 상대적으로 스택에 비해서는 쓰임새가 적은 자료구조이다. 하지만 데크나, 우선순위 큐, 너비 우선 탐색(BFS) 등 널리 쓰인다.
• 파이썬의 리스트는 큐의 모든 연산을 지원한다.
• 데크는 좀 더 나은 성능을 가지고, 양방향 삽입 삭제가 모두 가능하다.

문제 설명

큐를 이용해 다음 연산을 지원하는 스택을 구현하라.

• push(x) : 요소 x를 스택에 삽입한다.
• pop() : 스택의 첫 번째 요소를 삭제한다.
• top() : 스택의 첫 번째 요소를 가져온다.
• empty(): 스택이 비어 있는지 여부를 리턴한다.

풀이

class MyStack:
    def __init__(self):
        self.q = collections.deque()

    def push(self,x):
        self.q.append(x)
        # 요소 삽입 후 맨 앞에 두는 상태로 재정렬
        for _ in range(len(self.q) - 1) :
            self.q.append(self.q.popleft())

        def pop(self):
            return self.q.popleft()

        def top(self):
            return self.q[0]

        def empty(self):
            return len(selq.q) == 0

• push의 경우를 제외하면 간단한 코드이다.
• push는 맨 뒤에 요소를 삽입 후 , 삽입한 값을 맨 앞으로 두기 위해서 삽입한 값을 제외한 모든 값을 popleft()를 통해서 맨 뒤로 한 개씩 붙이는 작업을 추가한다.

문제 3. 스택을 이용한 큐 구현

문제 설명

스택을 이용해 다음 연산을 지원하는 큐를 구현하라.

• push(x) : 요소 x를 큐 마지막에 삽입한다.
• pop() : 큐의 첫 번째 요소를 제거한다.
• peek() : 큐의 첫 번째 요소를 조회한다.
• empty(): 큐가 비어 있는지 여부를 리턴한다.

스택 2개 사용하여 풀이

class MyQueue:
    def __init__(self):
        self.input = []
        self.output = []

    def push(self,x):
        self.input.append(x)

    def pop(self):
        self.peek()
        return self.output.pop()

    def peek(self):
        #output이 없으면 모두 재입력
        if not self.output:
            while self.input:
                self.output.append(self.input.pop())
        return self.output[-1]

    def empty(self):
        return self.input == [] and self.output == []

• peek과 pop은 같은 데이터를 불러오기 때문에, pop을 구현할 때 peek을 통해 데이터를 불러오고 pop으로 제거하는 알고리즘이다.
• peek의 경우에는 output 리스트가 비어있으면 input리스트에 있는 값들을 전부 역순으로 output에 입력하고, output 리스트의 마지막 값을 리턴한다. ( 즉, input 값의 첫번째 값을 return 한다. )

문제 4. 원형 큐 디자인

문제 설명

원형 큐를 디자인하라.

• 원형 큐는 FIFO 구조를 지닌다는 점에서 기존의 큐와 동일하다. 그러나 마지막 위치가 시작 위치와 연결되는 원형 구조를 가진다.
• 링 버퍼(Ring Buffer) 라고도 한다.
• 동작하는 원리는 투 포인터와 비슷하다. 기존의 큐는 공간이 꽉 차게 되면 더 이상 요소를 추가할 수 없지만, 원형 큐는 앞쪽에 공간이 남아있다면 동그랗게 연결해 앞쪽으로 추가할 수 있도록 재활용이 가능한 구조이다.

풀이

class MyCircularQueue:
    def __init__(self,k):
        self.q = [None] * k
        self.p1 = 0
        self.p2 = 0

    # enQueue(): rear포인터 이동
    def enQueue(self, value) :
        if selq.q[self.p2] is None:
            self.q[self.p2] = value
            self.p2 = (self.p2 + 1) % self.maxlen
            return True
        else:
            return False

    # deQueue(): front 포인터 이동
    def deQueue(self):
        if self.q[self.p1] is None:
            return False
        else:
            self.q[self.p1] = None
            self.p1 = (self.p1 +1)% self.maxlen
            return True

    def Front(self):
        return -1 if self.q[self.p1] is None else self.q[self.p1]

    def Rear(self):
        return -1 if self.q[self.p2 - 1 ] is None else self.q[self.p2 - 1]

    def isEmpty(self):
        return self.p1 == self.p2 and self.q[self.p1] is None

    def isFull(self):
        return self.p1 == self.p2 and self.q[self.p1] is not None

• 초기화시 큐의 크기k를 입력받고, 최대 길이인 maxlen으로 지정한다. p1 은 front의 포인터, p2는 rear의 포인터로 초기값은 0으로 지정했다.
• enQueue를 통해 rear 포인터를 이동시킨다. 해당 포인터가 가리키는 지점의 값이 None이면 value를 넣고 포인터를 앞으로 이동한다. ( maxlen 의 값을 넘는 걸 방지하기 위해 maxlen의 나머지 값으로 포인터 값일 지정해준다. 그리고 비정상적인 경우에는 False 를 리턴한다.
• deQueue의 경우에는 enQueue와는 같은 방식이지만 넣는 값을 반대로 진행하면 된다. ( front 포인터를 움직여 값을 비우는 작업이기 때문이다.)
• Front() , Rear() 연산은 해당 포인터 지점의 값을 가져오는 연산이다. 그러므로, Front()는 첫 번째 요소를 조회하는 연산이다.
• isEmpty() 와 isFull() 은 큐가 비었는지, 혹은 가득 채워져 있는지 조회하는 연산이다.

ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디, 생물 종, 보호 시작일, 보호 시작 시 상태, 이름, 성별 및 중성화 여부를 나타냅니다.

1. 이름이 없는 동물의 아이디 (LEVEL1)

동물 보호소에 들어온 동물 중, 이름이 없는 채로 들어온 동물의 ID를 조회하는 SQL 문을 작성해주세요. 단, ID는 오름차순 정렬되어야 합니다.

풀이

SELECT ANIMAL_ID FROM ANIMAL_INS
WHERE NAME IS NULL
ORDER BY ANIMAL_ID

• WHERE 조건 절에 NAME IS NULL 조건을 넣어주면, 이름 열이 결측치인 데이터를 찾아준다.

2. 이름이 있는 동물의 아이디 (LEVEL 1)

동물 보호소에 들어온 동물 중, 이름이 있는 동물의 ID를 조회하는 SQL 문을 작성해주세요. 단, ID는 오름차순 정렬되어야 합니다.

풀이

SELECT ANIMAL_ID FROM ANIMAL_INS
WHERE NAME IS NOT NULL
ORDER BY ANIMAL_ID

• 1번 문제에서 NOT을 추가해 IS NOT NULL을 사용하면 결측치가 아닌 데이터를 출력할 수 있다.

3. NULL 처리하기 (LEVEL 2)

입양 게시판에 동물 정보를 게시하려 합니다. 동물의 생물 종, 이름, 성별 및 중성화 여부를 아이디 순으로 조회하는 SQL문을 작성해주세요. 이때 프로그래밍을 모르는 사람들은 NULL이라는 기호를 모르기 때문에, 이름이 없는 동물의 이름은 "No name"으로 표시해 주세요.

풀이

SELECT ANIMAL_TYPE ,
        CASE
        WHEN NAME IS NULL THEN "No name"
        ELSE NAME 
        END, SEX_UPON_INTAKE
FROM ANIMAL_INS

• CASE WHEN ~ THEN ~ ELSE ~ END 문을 통해 상황에 따른 조건 지정을 해줄 수 있다. 이번 경우는 결측치일 경우 "No name"이 출력되도록 설정하고 나머지는 원래 값을 출력하도록 한 것이다.
• 끝났을 때 꼭 END를 써주어야한다.

문제설명

ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디, 생물 종, 보호 시작일, 보호 시작 시 상태, 이름, 성별 및 중성화 여부를 나타냅니다.

1. 고양이와 개는 몇 마리 있을까? (LEVEL 2)

동물 보호소에 들어온 동물 중 고양이와 개가 각각 몇 마리인지 조회하는 SQL문을 작성해주세요. 이때 고양이를 개보다 먼저 조회해주세요.

풀이

SELECT ANIMAL_TYPE, COUNT(*) FROM ANIMAL_INS
WHERE ANIMAL_TYPE IN ('Cat','Dog')
GROUP BY ANIMAL_TYPE  
ORDER BY ANIMAL_TYPE

• GROUP BY 문은 지정된 열을 기준으로 데이터들을 그룹화해주는 함수이다.
• 동물 보호소에 고양이와 개 이외의 다른 동물이 있을 수 있으므로 WHERE를 통해 고양이와 개만을 조건으로 지정해주고, 그룹화하고, 고양이부터 나오도록 ORDER BY문을 통해 정렬해주면 된다.

2. 동명 동물 수 찾기 (LEVEL 2)

동물 보호소에 들어온 동물 이름 중 두 번 이상 쓰인 이름과 해당 이름이 쓰인 횟수를 조회하는 SQL문을 작성해주세요. 이때 결과는 이름이 없는 동물은 집계에서 제외하며, 결과는 이름 순으로 조회해주세요.

풀이

SELECT NAME, COUNT(*) FROM ANIMAL_INS
GROUP BY NAME HAVING COUNT(NAME) >=2
ORDER BY NAME

• GROUP BY 에서 HAVING을 사용하면 그룹화 결과 출력될 조건을 지정해 줄 수 있다. HAVING 과 WHERE의 차이는 HAVING은 조건 필터링을 그룹화를 하고난 후에 진행하고, WHERE는 조건 필터링을 그룹화 전에 한다.
• 지금의 경우와 같이 그룹화를 하고 그 결과가 2개이상인 대상을 출력하는 문제에서는 HAVING을 활용하는 것이 맞다.

3. 입양 시각 구하기(1) (LEVEL 2)

ANIMAL_OUTS 테이블은 동물 보호소에서 입양 보낸 동물의 정보를 담은 테이블입니다. ANIMAL_OUTS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, NAME, SEX_UPON_OUTCOME는 각각 동물의 아이디, 생물 종, 입양일, 이름, 성별 및 중성화 여부를 나타냅니다.

보호소에서는 몇 시에 입양이 가장 활발하게 일어나는지 알아보려 합니다. 09:00부터 19:59까지, 각 시간대별로 입양이 몇 건이나 발생했는지 조회하는 SQL문을 작성해주세요. 이때 결과는 시간대 순으로 정렬해야 합니다.

풀이

SELECT HOUR(DATETIME) AS HOUR , COUNT(*) AS COUNT FROM ANIMAL_OUTS
GROUP BY HOUR HAVING  HOUR BETWEEN 9 AND 19
ORDER BY HOUR

• HOUR 함수를 이용해, DATETIME 열에서 시간 정보만을 추출한 후 HOUR 라는 이름으로 선언을 했다.
• 그 이후 HOUR를 기준으로 그룹화를 시킨다. HAVING절의 조건문을 통해 9~19사이의 데이터만을 추출하도록 조건을 지정해 주었다.
• BETWEEN A AND B 를 사용해 A~B 사이의 조건을 지정해 줄 수 있다.

4. 입양 시각 구하기(2) (LEVEL 4)

보호소에서는 몇 시에 입양이 가장 활발하게 일어나는지 알아보려 합니다. 0시부터 23시까지, 각 시간대별로 입양이 몇 건이나 발생했는지 조회하는 SQL문을 작성해주세요. 이때 결과는 시간대 순으로 정렬해야 합니다. SQL문을 실행하면 다음과 같이 나와야 합니다.

SELECT TEMP.HOUR, COUNT(HOUR(ANIMAL_OUTS.DATETIME)) AS COUNT FROM TEMP LEFT JOIN ANIMAL_OUTS ON TEMP.HOUR = HOUR(ANIMAL_OUTS.DATETIME) GROUP BY TEMP.HOUR ORDER BY TEMP.HOUR ;

```

• 데이터가 20시 이후부터는 존재하지 않지만, 23시 데이터까지 출력해야하기 때문에 임시 테이블을 생성하고 LEFT JOIN을 통해 병합하는 방법을 이용했다.
• WITH RECURSIVE 를 이용해 재귀쿼리를 이용한 가상의 테이블을 만들 수 있다. 초기값이 0인 HOUR에 1씩 더해서 WHERE절을 만족하는 23까지 반복한다.
• 그러므로 TEMP라는 테이블에는 0~23까지의 숫자가 담겨있다.
• JOIN(교집합) 후에 출력학 형태를 SELECT를 통해 지정해준다. 여러개의 테이블이 사용되는 연산의 경우 열앞에 원래 테이블을 써주어야 한다.
• TEMP와 ANIMAL_OUTS를 LEFT JOIN 시켜준다. LEFT JOIN 은 왼쪽에 존재하는(처음 언급한) 테이블을 기준으로 ON 뒤에 나와있는 조건에 맞게 병합시키는 함수이다.
• LEFT JOIN은 왼쪽에 나와있는 테이블은 전부 다 출력되고 그에 맞게 오른쪽 테이블을 병합시킨다고 생각하면 편하다.

문제설명

ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디, 생물 종, 보호 시작일, 보호 시작 시 상태, 이름, 성별 및 중성화 여부를 나타냅니다.

1. 최대값 구하기 (LEVEL 1)

가장 최근에 들어온 동물은 언제 들어왔는지 조회하는 SQL 문을 작성해주세요.

풀이

SELECT MAX(DATETIME) AS 시간 FROM ANIMAL_INS

• SELECT 뒤에 MAX(DATETIME) 을 넣어, 날짜의 최대값을 구한다. 날짜는 시간이 지날수록 큰 값으로 간주되기 때문에 최대값을 활용한다.
• AS 를 활용해서 출력될 컬럼명을 '시간' 으로 바꿔준다.

2. 최솟값 구하기 (LEVEL 2)

동물 보호소에 가장 먼저 들어온 동물은 언제 들어왔는지 조회하는 SQL 문을 작성해주세요.

풀이

SELECT MIN(DATETIME) AS 시간 FROM ANIMAL_INS

• 1번에서 MAX를 MIN으로 바꿔주면 된다.

3. 동물 수 구하기 (LEVEL 2)

동물 보호소에 동물이 몇 마리 들어왔는지 조회하는 SQL 문을 작성해주세요.

풀이

SELECT COUNT(*) AS count FROM ANIMAL_INS

• COUNT(*) 를 이용해서 전체 데이터의 수를 출력할 수 있다.
• COUNT(컬럼명)을 이용해서 구할 수 있지만, 만약 그 특정 컬럼에 결측치가 존재할 경우 그 데이터를 제외하고 COUNT하기 때문에 *을 사용하는 것이 안전하다.

4. 중복 제거하기 (LEVEL 2)

동물 보호소에 들어온 동물의 이름은 몇 개인지 조회하는 SQL 문을 작성해주세요. 이때 이름이 NULL인 경우는 집계하지 않으며 중복되는 이름은 하나로 칩니다.

풀이

SELECT COUNT( DISTINCT NAME ) AS count FROM ANIMAL_INS

• DISTINCT 옵션을 이용할 경우 중복 값을 제거한 유일한 값만을 COUNT할 수 있다.
• 이름 열의 결측치인 경우 집계하지 않기 때문에 COUNT() 함수 안에 NAME이라는 특정 컬럼명을 집어넣는다.

문제 설명

ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디, 생물 종, 보호 시작일, 보호 시작 시 상태, 이름, 성별 및 중성화 여부를 나타냅니다.

1. 모든 레코드 조회하기 (LEVEL 1)

동물 보호소에 들어온 모든 동물의 정보를 ANIMAL_ID순으로 조회하는 SQL문을 작성해주세요. SQL을 실행하면 다음과 같이 출력되어야 합니다.

풀이

SELECT * FROM ANIMAL_INS
ORDER BY ANIMAL_ID

• SQL의 기본 문제이다. SELECT는 출력할 컬럼을 고르는 작업이다. 뒤에 * 을 넣으면 전체 정보를 출력해준다. ORDER BY 를 통해 정렬할 수 있다. 디폴트는 오름차순이다.
  
  

2. 역순 정렬하기 (LEVEL 1)

동물 보호소에 들어온 모든 동물의 이름과 보호 시작일을 조회하는 SQL문을 작성해주세요. 이때 결과는 ANIMAL_ID 역순으로 보여주세요. SQL을 실행하면 다음과 같이 출력되어야 합니다.

풀이

SELECT NAME , DATETIME FROM ANIMAL_INS
ORDER BY ANIMAL_ID DESC

• NAME과 DATETIME 을 SELECT 해주고 ORDER BY 옵션을 통해 정렬을 해주면 해결된다. 정렬할 때 DESC를 통해 내림차 순 정렬을 해야한다.

3. 아픈 동물 찾기 (LEVEL 1)

동물 보호소에 들어온 동물 중 아픈 동물의 아이디와 이름을 조회하는 SQL 문을 작성해주세요. 이때 결과는 아이디 순으로 조회해주세요. 아픈 동물은 INTAKE_CONDITION 컬럼값이 Sick 값을 가진다.

풀이

SELECT ANIMAL_ID , NAME FROM ANIMAL_INS
WHERE INTAKE_CONDITION = "Sick"

• WHERE 를 통해 출력될 데이터의 조건을 지정해준다. 아픈 동물을 찾아야 하기 때문에, INTAKE_CONDITION = "Sick" 라고 써주면 된다.
• Sick 은 문자기 때문에 따옴표를 써주어야 한다.

4. 어린 동물 찾기 (LEVEL 1)

동물 보호소에 들어온 동물 중 젊은 동물의 아이디와 이름을 조회하는 SQL 문을 작성해주세요. 이때 결과는 아이디 순으로 조회해주세요. ( INTAKE_CONDITION 컬럼 값이 Aged가 아닌 값을 가진 데이터가 어린 동물이다. )

풀이

SELECT ANIMAL_ID, NAME FROM ANIMAL_INS
WHERE INTAKE_CONDITION != "Aged"
ORDER BY ANIMAL_ID

5. 동물의 아이디와 이름 (LEVEL 1)

동물 보호소에 들어온 모든 동물의 아이디와 이름을 ANIMAL_ID순으로 조회하는 SQL문을 작성해주세요. SQL을 실행하면 다음과 같이 출력되어야 합니다.

풀이

SELECT ANIMAL_ID , NAME FROM ANIMAL_INS
ORDER BY ANIMAL_ID

• ANIMAL_ID 순으로 정렬을 해야하기 때문에 ORDER BY 를 통해 ANIMAL_ID 를 오름차순으로 정렬해 주면 된다.

6. 여러 기준으로 정렬하기 (LEVEL 1)

동물 보호소에 들어온 모든 동물의 아이디와 이름, 보호 시작일을 이름 순으로 조회하는 SQL문을 작성해주세요. 단, 이름이 같은 동물 중에서는 보호를 나중에 시작한 동물을 먼저 보여줘야 합니다.

풀이

SELECT ANIMAL_ID , NAME, DATETIME FROM ANIMAL_INS
ORDER BY NAME , DATETIME DESC

• ORDER BY 뒤에 컬럼명을 여러 개를 사용하면 여러 기준으로 정렬 기능을 이용할 수 있다. 또한, 각각 오름차순으로 정렬할지 내림차순으로 정렬할지 지정할 수도 있다.
  
  

  7. 상위 n개 레코드 (LEVEL 1)

  동물 보호소에 가장 먼저 들어온 동물의 이름을 조회하는 SQL 문을 작성해주세요.

풀이 1

SELECT NAME FROM ANIMAL_INS ORDER BY DATETIME LIMIT 1

• LIMIT를 사용한 방법이다. ORDER BY를 통해 데이터를 날짜순으로 정렬하고 LIMIT 1을 사용해 가장 먼저 들어온 동물의 이름을 출력할 수 있다.

풀이 2

SELECT NAME FROM ANIMAL_INS 
WHERE DATETIME = (SELECT MIN(DATETIME) FROM ANIMAL_INS)

• 서브쿼리를 사용한 방법이다. 조건절 WHERE를 이용해 날짜가 최소값인 서브쿼리와 일치하는 결과를 출력하는 방법이다.