• 링크: https://programmers.co.kr/learn/courses/30/lessons/43105

def solution(triangle):
    n_layer = len(triangle)
    memory = [[0 for j in range(len(triangle[i]))] for i in range(n_layer)]


    for layer in range(n_layer-1, -1, -1):
        if layer == n_layer-1:
            for idx, node in enumerate(triangle[layer]):
                memory[layer][idx] = node
        else:
            for idx, node in enumerate(triangle[layer]):
                memory[layer][idx] = node + max(memory[layer+1][idx], memory[layer+1][idx+1])

    return memory[0][0]

• 메모이제이션으로 풀이했다. 삼각형의 밑바닥부터 시작해서 왼쪽과 오른쪽 노드 중 큰 값을 판별해서 자기 자신 값과 더한 후, 그 값을 메모리의 해당 인덱스에 저장했다. 그런 방식으로 풀면 memory[0][0]에는 정답이 들어가게 된다.
• 일단 트라이앵글의 모양이 이진트리와 유사한 것을 이용해서 문제를 분할해보려 했다. 왼쪽 삼각형에서 최대 합, 오른쪽 삼각형에서 최대합을 구한 뒤, 그 중에서 더 큰 값을 자기 자신과 더하는 방식으로 재귀적으로 풀 수 있을 것 같았다. 그 후 재귀적 풀이를 메모이제이션으로 변형했다.

• 링크: https://programmers.co.kr/learn/courses/30/lessons/49189

from collections import deque, defaultdict
def solution(n, vertex):
    graph = defaultdict(list)
    distance = {i:0 for i in range(1, n + 1)}
    queue = deque([[1, 0]])

    for a, b in vertex:
        graph[a].append(b)
        graph[b].append(a)

    while queue:
        node, dist = queue.popleft()
        if distance[node] == 0:
            distance[node] = dist

            for i in graph[node]:
                queue.append([i, dist+1])

    distance[1] = 0
    distance = list(distance.values())
    max_dist = max(distance)

    return distance.count(max_dist)

• BFS를 이용해서 1번 노드와 다른 노드들 간의 최소 거리를 구한 후 가장 먼 노드의 갯수를 세었다.
• 처음엔 최소힙을 이용한 다익스트라 알고리즘을 이용해서 풀이하려고 했는데 오히려 시간초과가 났다. 일반 BFS보다 다익스트라 알고리즘이 더 효율적이라고 생각해왔었는데 오히려 더 효율적이지 못했던 것이다. 찾아보니 노드 간의 거리가 모두 똑같은 경우 BFS가 더 효율적일 수 있다고 한다.

• 링크: https://programmers.co.kr/learn/courses/30/lessons/42895

def solution(N, number):
    if N == number:
        return 1

    candidate = {1:[N, -N]}
    key = 2

    while True:
        new_candidate = set()
        new_candidate.add(int(str(N) * key))
        new_candidate.add(-int(str(N) * key))

        for i in range(1, key):
            lst_x = candidate[i]
            lst_y = candidate[key - i]

            for x in lst_x:
                for y in lst_y:
                    new_candidate.add(x + y)
                    if y != 0:
                        new_candidate.add(x // y)
                    new_candidate.add(x * y)
                    new_candidate.add(x - y)

        candidate[key] = list(new_candidate)

        if number in candidate[key]:
            return key

        key += 1

        if key > 8:
            return -1

• 다이나믹프로그래밍 중 메모이제이션을 사용해서 풀었다. N을 k번 사용해서 나올 수 있는 모든 값을 N(k)라고 할 때, N(k)는 <N(1), N(k-1)>, <N(2), N(k-2)>... 등의 조합으로 구할 수 있다. 따라서 N(k)는 더 하위 문제의 값들을 조합해서 만들어지는 분할정복이 가능한 문제라는 뜻이다.

• 이 코드에서 사용한 풀이는 N을 1번 써서 나올 수 있는 값, 2번 써서 나올 수 있는 값.. 을 딕셔너리에 저장하고 N을 3번 써서 나올 수 있는 값들을 구해야할 때엔 1번써서 나올 수 있는 값 리스트와 2번 써서 나올 수 있는 값 리스트를 불러와 조합하는 방식이다.

• N == number인 경우를 고려하지 못하여 생각보다 푸는 시간이 길어졌다.

• 이 코드에선 조합이 뒤집어지는 경우를 빼지 않았기 때문에 예를 들어 key가 3일 경우 (1, 2), (2, 1) 같은 식으로 두번씩 값을 구하게 되기 때문에 시간적으론 완전히 효율적이지 않다. key가 8일 경우까지만 고려하면 되기에 고치지 않았으나 이 부분을 고치면 더 완벽한 답이 될 것 같다.

링크: https://www.acmicpc.net/problem/11047

N, K = map(int, input().split())
coins = []
answer = 0

for i in range(N):
    value = int(input())
    coins.append(value)

for value in coins[::-1]:
    n, K = divmod(K, value)
    answer += n

print(answer)

• 동전문제를 그리디 방식으로 풀이하는 것은 전에 파이썬 알고리즘 리뷰 책으로 공부를 했을 때에도 해본 것이라 어려운 문제는 아니었다. 다시 한번 그 책의 내용을 생각해보면 동전의 액수가 서로 배수 관계일 때만 그리디 방식으로 이 문제를 풀 수 있다. 동전의 액수가 배수 관계가 아닌 동전이 하나라도 있을 경우 그리디 방식으로 풀 수 없다.
• 구현은 어렵지 않았지만 뒷부분에서 약간 실수가 있어 첫 제출은 시간 초과가 났다. 그 코드는 동전의 갯수를 세는 방식을 반복문을 사용했는데 시간초과가 나서 그 다음 제출한 코드는 위처럼 divmod를 사용하여 나눗셈의 몫과 나머지를 이용했다.

시간초과가 난 풀이

N, K = map(int, input().split())
coins = []
answer = 0

for i in range(N):
    value = int(input())
    coins.append(value)

for value in coins[::-1]:
    while K >= value:
        K -= value
        answer += 1

print(answer)

링크: https://www.acmicpc.net/problem/1003

def fibonacci(n):
    if n == 0:
        return 1, 0
    elif n == 1:
        return 0, 1

    prev_0, prev_1 = 1, 0
    present_0, present_1 = 0, 1

    for i in range(n - 1):
        prev_0, prev_1, present_0, present_1 = present_0, present_1, present_0 + prev_0, present_1 + prev_1

    return present_0, present_1

n = int(input())

for i in range(n):
    input_n = int(input())
    answer = fibonacci(input_n)
    print(answer[0], answer[1])

• 동적계획법을 사용하는 피보나치 풀이는 워낙 많이 봐서 외운지라 어렵지 않게 풀었다. 다만 이 문제는 피보나치 수열을 직접 구현하는 것이 아니라 0과 1을 호출하는 횟수를 구하는 문제라 조금은 신선했던 것 같다.
• 나는 0을 호출하는 횟수와 1을 호출하는 횟수를 따로따로 변수로 선언해서 prev_0, prev_1, present_0, present_1로 4개의 변수를 사용했는데 좀 더 간결한 풀이가 있지 않을까 싶어 아쉬운점이 있다.

링크: https://www.acmicpc.net/problem/15649

from collections import deque
n, m = map(int, input().split())

lst = [str(i) for i in range(1, n + 1)]
queue = deque([[str(i)] for i in lst])
answer = []

while queue:
    pop = queue.popleft()

    if len(pop) == m:
        print(' '.join(pop))
        continue

    for i in lst:
        if i not in pop:
            temp = pop + [i]
            queue.append(temp)

• 사실 파이썬에는 itertools 패키지에 permutation을 만들 수 있는 메소드가 있어 직접 구현할 필요는 없으나 BFS를 연습해볼 생각으로 일부러 BFS로 풀이했다.
• collections의 deque를 사용하여 큐를 만들고 그 안에 시작할 수 있는 모든 노드를 시작점으로 한 route를 리스트로 넣어 구현했다.

정렬

K 번째 수

• start와 end를 input으로 받아 sorted하고 k번째 수를 인덱싱으로 뽑는다.

def solution(array, commands):
    answer = []
    for command in commands:
        # start, end 저장
        start = command[0] - 1
        end = command[1]
        k = command[2] - 1

        # 자른 배열 sorted
        temp = sorted(array[start:end])
        answer.append(temp[k])
    return answer

가장 큰 수

• 처음엔 정렬로 접근했지만 numbers에 들어오는 숫자의 자릿수가 모두 다를 가능성이 있어서 잘 풀리지 않았다. 예를 들어 3, 30이 들어올경우 330이 맞는 답이지만 단순히 정렬로 풀면 303이 되어버린다.
• 검색을 통해 다른 사람들의 풀이를 참고하니 functools.cmp_to_key 메소드를 쓴 풀이가 눈에 띄었다.
• cmp_to_key는 sorted와 같은 정렬 함수의 key 매개변수에 함수를 전달할 때 사용되는 함수로, 두개의 인수를 받아들이고 첫번째 인수를 기준으로 그들을 비교하여 작으면 음수, 같으면 0, 크면 양수를 반환하는 비교함수여야 한다.

cmp-to-key 예시

import functools

def xy_compare(n1, n2):
    if n1[1] > n2[1]:         # y 좌표가 크면
        return 1
    elif n1[1] == n2[1]:      # y 좌표가 같으면
        if n1[0] > n2[0]:     # x 좌표가 크면
            return 1
        elif n1[0] == n2[0]:  # x 좌표가 같으면
            return 0
        else:                 # x 좌표가 작으면
            return -1
    else:                     # y 좌표가 작으면
        return -1

src = [(0, 4), (1, 2), (1, -1), (2, 2), (3, 3)]
result = sorted(src, key=functools.cmp_to_key(xy_compare))
print(result)

• cmp_to_key는 정렬을 할 때, 대소관계를 새로 정의할 수 있는 유용한 함수로 꼭 암기해둬야겠다고 생각했다.

# 모범 답안
import functools

def comparator(a,b):
    t1 = a+b
    t2 = b+a
    return (int(t1) > int(t2)) - (int(t1) < int(t2)) #  t1이 크다면 1  // t2가 크다면 -1  //  같으면 0

def solution(numbers):
    n = [str(x) for x in numbers]
    n = sorted(n, key=functools.cmp_to_key(comparator),reverse=True)
    answer = str(int(''.join(n)))
    return answer

H-Index

• citations를 내림차순으로 정렬하여 반복문을 돌면서 h번 이상 인용된 논문의 갯수가 몇개 포함되어 있는지 체크할 수 있도록 한다.
• max를 이용해 h를 계속 최댓값으로 업데이트하여 최댓값을 리턴하도록 한다.

def solution(citations):
    # 내림차순 정렬
    citations.sort(reverse=True)
    h = 0 

    # 반복문을 돌면서 h값 최대화
    for i in range(len(citations)):
        if citations[i] >= i+1: 
            h = max(h, i+1)
    return h

힙(Heap)

더 맵게

• 배열을 heapq로 만든 뒤, 문제 조건에 따라 두번 heappop을 하고 새 값을 만들어 배열에 다시 heappush하는 것을 반복한다.
• 다만 계속 반복해도 모든 음식의 스코빌 지수가 K 이상으로 올라가지 않을 경우 -1을 리턴해야 하므로 heap에 마지막 남은 원소하나가 K보다 큰지 작은지 판별하는 예외처리를 추가한다.

def solution(scoville, K):
    import heapq
    # 힙 만들기
    heapq.heapify(scoville)

    # 예외 처리(배열이 비어있을 경우)
    if sum(scoville) == 0 and K > 0:
        return -1

    cnt = 0
    # 과정 반복(배열에 원소가 하나만 남을때까지)
    while len(scoville) > 1:
        p = heapq.heappop(scoville)
        # 최솟값이 K보다 작을 경우(모든 음식이 K 이상이 아님)
        if p < K:
            q = heapq.heappop(scoville)
            heapq.heappush(scoville, p+2*q)
            cnt += 1
        # 모든 음식이 K 이상임 -> break
        else:
            break

    # 모든 과정을 거쳤음에도 K 이상이 되지 않으면 -1 리턴
    if scoville[0] < K:
        return -1

    return cnt

디스크 컨트롤러

• 이 문제의 목적은 작업 요청부터 종료까지 걸린 시간의 평균을 최소화해야 하므로, 작업 요청부터 종료까지의 시간을 계산하여 heap에 넣은뒤, heappop으로 처리한 작업을 없애는 식으로 구현한다.

import heapq
def solution(jobs):
    # 먼저 요청한 작업이 맨 뒤로 가게 정렬
    jobs.sort(reverse=True)
    result = 0
    length = len(jobs)

    # 요청받은 작업을 담아두는 heap
    on_request = []
    # 걸린 시간을 저장하는 변수
    time = 0

    # 모든 작업을 처리할때까지 반복문
    while jobs or on_request:
        # on_request에 해당 시간에 요청받은 작업 heappush
        while (not on_request) or (jobs and time >= jobs[-1][0]):
            job = jobs.pop()
            # 걸리는 시간을 기준으로 heappush
            heapq.heappush(on_request, [job[1], job[0]])

        # 처리할 작업을 heappop
        work = heapq.heappop(on_request)

        # 만약 요청받은 시간이 현재 시간보다 뒷 시간일 경우, time을 요청받은 시간으로 변경해주기
        if time < work[1]:
            time = work[1]

        # 걸린 시간을 time에 더해주고, 평균 시간을 구하기 위해 result에 요청부터 종료까지의 시간을 더해주기
        time += work[0]
        result += time - work[1]

    return int(result / length)

이중 우선순위 큐

• 최솟값을 pop할때는 heapify, heappop을 이용하고, 최댓값을 pop할때는 sort와 pop을 사용한다.
• heapify + heappop의 시간복잡도는 O(n) + O(1) = O(n), sort + pop의 시간복잡도는 O(n log n) + O(1) = O(n log n) 이므로, 전체 알고리즘의 시간복잡도는 평균적으로 추출 명령의 수가 K일때, O(K * n log n)일 것이다.
• 두개의 배열을 사용하는 방법도 생각해봤지만 두 배열에서 동일한 값을 지우는 과정에서 더 많은 시간이 소요될 것 같아 이 방식으로 변경했다.

import heapq
def solution(operations):
    q = []

    for op in operations:
        op = op.split()
        if op[0] == 'I':
            q.append(int(op[1]))
        elif op[0] == 'D':
            if q:
                if op[1] == '1':
                    q.sort()
                    q.pop()
                else:
                    heapq.heapify(q)
                    heapq.heappop(q)

    if not q:
        return [0, 0]

    return [max(q), min(q)]

DFS & BFS

타겟 넘버

• root가 0이고 그 아래로 + number와 - number 해준 것들이 가지로 달려있는 트리 형태의 그래프로 생각한다.
• dfs를 이용해 모든 경우의 수를 탐색하고 그 갯수를 센다.

def solution(numbers, target):
    n_numbers = len(numbers)

    # dfs 구현
    def dfs(index, csum):
        cnt = 0

        if index == n_numbers:
            # target이면 1, target 아니면 0
            return int(csum == target)

        # cnt에 모두 더해주기
        cnt += dfs(index + 1, csum + numbers[index])
        cnt += dfs(index + 1, csum - numbers[index])

        return cnt

    return dfs(0, 0)

네트워크

• input을 이용해서 그래프 맵을 그리고 그래프 맵을 DFS로 순회하며 방문하는 노드들을 visited에 append한다. 그 후 DFS가 끝날 때 카운트를 하여 네트워크의 갯수를 센다.

from collections import defaultdict
def solution(n, computers):
    graph, stack = defaultdict(list), []
    visited = []

    # 그래프 맵 만들기
    for i in range(n):
        for j in range(n):
            if computers[i][j] == 1:
                graph[i].append(j)

    # dfs 구현
    def dfs(a):
        stack.append(a)
        visited.append(a)
        while stack:
            for i in graph[stack.pop()]:
                if i not in visited:
                    stack.append(i)
                    visited.append(i)

    # 네트워크 순회가 끝나면 count + 1
    count = 0
    for i in list(graph):
        if i not in visited:
            dfs(i)
            count += 1

    return count

단어 변환

• 한 글자만 다른 단어 사이가 연결된 그래프라고 생각하고 BFS로 타겟 단어까지 가는 최단 경로를 찾는 문제로 치환하여 푼다.

from collections import defaultdict, deque
import sys

def solution(begin, target, words):
    graph = defaultdict(list)
    queue = deque()
    answer = []
    words.append(begin)

    # 그래프 맵 만들기
    for i in words:
        for j in words:
            if i != j:
                for idx in range(len(i)):
                    if i[:idx] + i[idx + 1:] == j[:idx] + j[idx + 1:]:
                        graph[i].append(j)

    # BFS 구현
    def bfs(w):
        min_step = sys.maxsize
        traced = []
        queue.append((0, w))
        while queue:
            step, temp = queue.popleft()
            if temp == target:
                # step 수를 세어 최소 step인지 확인
                min_step = min(step, min_step)

            for word in graph[temp]:
                # 최단경로를 알아내야하므로 이미 방문한 노드는 방문 하지 않음
                if word not in traced:
                    traced.append(word)
                    queue.append((step + 1, word))

        return min_step

    answer = bfs(begin)

    # 최소 step이 나오지 않았으면 0 리턴
    if answer == sys.maxsize:
        return 0
    else:
        return answer

여행경로

• 사전 순서로 방문해야하므로 공항 이름을 정렬하여 그래프 맵으로 만들고, DFS로 그래프에서 해당 공항을 pop해가면서 모든 노드를 순회하는 루트를 찾는다.

def solution(tickets):
    from collections import defaultdict
    graph = defaultdict(list)

    # 그래프 맵 만들기(알파벳 순서로 방문하기 위해 sorted)
    for a, b in sorted(tickets, reverse=True):
        graph[a].append(b)

    route = []

    # dfs 구현
    def dfs(a):
        while graph[a]:
            # 알파벳 순서로 방문하기 위해 pop
            dfs(graph[a].pop())
        route.append(a)


    dfs('ICN')

    # 나중에 방문한 곳이 배열의 앞에 위치하게 되므로 뒤집기
    return route[::-1]

백준 단계별로 풀기 - 스택

10828번

• https://www.acmicpc.net/problem/10828
• 스택을 구현하는 문제다. 파이썬의 경우 리스트가 스택의 모든 기능을 제공하므로 리스트를 이용ㅎ면 쉽게 구현할 수 있다.
• 자꾸 시간 초과가 나서 코드가 잘못 되었나 했더니 백준에서는 input()대신 sys.stdin.readline()를 사용해야 시간초과를 막을 수 있다고 한다.

import sys

# 스택 개체 구현
class stack():
    def __init__(self):
        self.stk = []
        self.count = 0

    def empty(self):
        return int(self.count == 0)

    def size(self):
        return self.count

    def push(self, n):
        self.stk.append(n)
        self.count += 1

    def pop(self):
        if self.empty() == 0:
            self.count -= 1
            return self.stk.pop()
        else:
            return -1

    def top(self):
        if self.empty() == 0:
            return self.stk[-1]
        else:
            return -1

n = int(input())

stack = stack()

for i in range(n):
    command = sys.stdin.readline().split()
    if command[0] == 'push':
        stack.push(int(command[1]))
    elif command[0] == 'pop':
        print(stack.pop())
    elif command[0] == 'empty':
        print(stack.empty())
    elif command[0] == 'top':
        print(stack.top())
    elif command[0] == 'size':
        print(stack.size())

10773번

• https://www.acmicpc.net/problem/10773
• 입력값이 들어오면 stack에 push하고 0이 입력될 때 마다 stack에서 pop한 뒤, stack 값들의 합계를 출력하면 되는 문제다.

import sys
k = int(input())

stack = []
for i in range(k):
    n = int(sys.stdin.readline())

    # 0이 입력될 경우
    if n == 0:
        stack.pop()
    # 다른 입력값이 들어왔을 경우
    else:
        stack.append(n)

print(sum(stack))

9012번

• https://www.acmicpc.net/problem/9012
• 괄호 입력값을 차례대로 스택에 쌓다가 ')'이 들어오면 stack의 마지막 값을 확인 한 뒤 '('이면 stack에서 pop을 한다. 그 후 모든 문자열을 확인하고 스택이 비어있으면 올바른 괄호 문자열, 비어있지 않으면 올바르지 않은 괄호 문자열이다.

t = int(input())
map_ = {'(':')'}

for i in range(t):
    s = list(input())
    stack = []
    for letter in s:
        if stack and stack[-1] in map_ and map_[stack[-1]] == letter:
            stack.pop()
        else:
            stack.append(letter)

    if stack:
        print('NO')
    else:
        print('YES')

4949번

• https://www.acmicpc.net/problem/4949
• 9012번과 비슷하나, 문자열에 괄호가 아닌 문자가 섞여있고, 소괄호와 대괄호가 섞여있다. 나는 문자열을 스캔하면서 대괄호 혹은 소괄호 일때는 스택에 push하고, )나 ]가 들어왔을 때, 스택의 마지막값을 확인해서 (나 [이면 스택에서 pop하는 것으로 구현했다.
• 처음엔 대괄호와 소괄호를 각각 다른 스택에 담는 것으로 구현했는데 이 경우 '([)]'와 같은 경우를 걸러낼 수가 없어서 다시 한 개의 스택으로 바꿨다. 괄호 내부의 문자열도 균형잡힌 문자열이어야 한다는 조건을 잊어버리는 실수를 했다.

string = input()
map_ = {'(':')', '[':']'}

while string != '.':
    stack = []
    for s in string:
        if s in ['[', ']', '(', ')']:
            if stack and stack[-1] in map_ and map_[stack[-1]] == s:
                stack.pop()
            else:
                stack.append(s)


    if stack:
        print('no')
    else:
        print('yes')

    string = input()

1874번

• https://www.acmicpc.net/problem/1874
• 숫자를 입력받아 입력받은 값이 push되지 않은 값보다 크면, 해당 입력값이 나올때까지 stack에 push하고 입력값을 pop한다. push와 pop을 할때마다 answer 리스트에 '+'와 '-'를 삽입한다. 그러나 입력받은 값이 push되지 않은 값보다 작을 경우 push를 통해서는 해당 값을 찾을 수 없으므로 is_false 변수를 1로 바꿈으로써 불가능한 경우라는 것을 표시한다. 마지막단에서 answer을 출력할 때는 is_false가 1일 경우 'NO'를 출력하고 0일 경우 한줄마다 '+'와 '-'를 하나씩 출력한다.
• 최소 한번의 push는 해야하므로 answer엔 '+'를 넣어놓았고 stack에는 1을 넣어놓았다. push되지 않은 수를 뜻하는 p는 2부터 시작하는 것으로 했다.

n = int(input())
answer = ['+']
stack = [1]
is_false = 0
p = 2

for i in range(n):

    k = int(input())

    if not stack:
        stack.append(p)
        answer.append('+')
        p += 1

    while stack[-1] != k:
        if stack[-1] < k:
            stack.append(p)
            answer.append('+')
            p += 1
        elif stack[-1] > k:
            is_false = 1
            break

    stack.pop()
    answer.append('-')

if is_false == 1:
    answer = ['NO']

for i in answer:
    print(i)

17298번

• https://www.acmicpc.net/problem/17298
• 파이썬 알고리즘 인터뷰에서 나온 '일일 온도'(https://littledatascientist.tistory.com/17?category=981837) 문제와 비슷하다고 느꼈다. 값 대신 인덱스를 스택에 쌓으면서 전보다 큰 값이 나올 경우 stack의 마지막 인덱스의 해당 값이 현재 값보다 클때까지 pop한다. 그 후 answer 리스트에는 pop된 인덱스마다 현재의 값을 저장한다.
• 스택에 인덱스를 push한다는 아이디어가 중요한 것 같다.

n = int(input())
A = list(map(int, input().split()))
answer = ['-1'] * n
stack = []

for i, cur in enumerate(A):
    while stack and cur > A[stack[-1]]:
        last = stack.pop()
        answer[last] = str(cur)
    stack.append(i)
print(' '.join(answer))