웨일의 블로그 웨일의 블로그

문제 - 타겟 넘버 문제링크 문제 설명 이렇게 numbers와 target이 입력으로 주어지면, numbers의 모든 숫자들을 각각 더하든지 빼든지 해서 target값을 만들어내는 경우의 수를 구하는 문제입니다. 첫번째 예시 입력에 대해 다음과 같은 경우의 수들이 있습니다. 이런식으로 각 숫자 앞에 +를 붙일건지 -를 붙일건지 선택해서 다 계산한 결과가 target이면 됩니다. 풀이 과정 각 숫자에는 부호가 할당되어야 합니다. 그리고 각 숫자마다 붙는 부호는 다른 숫자들과 독립적입니다. 이러면 각 숫자마다 +-의 두가지 경우가 있습니다. 모든 숫자에 대해 +-를 붙이는 경우의 수를 구하는 데 좋은 알고리즘은 DFS가 있습니다. """ 각 숫자에 대해 -, + 할당 dfs(order, val) """ de..

머지소트는 분할 정복 카테고리에 속합니다. 숫자로 이루어진 수열이 반씩 나눠지며 하나만 남게 되는 과정이 분할이고, 각 파티션끼리 합쳐지는 과정이 정복입니다. 머지 소트의 시간복잡도는 O(NlogN)이라고 잘 알려져 있습니다. 왜 O(NlogN)일까요? 우선, 분할과정을 살펴봅시다. 단순히 생각해서 7개의 숫자로 이루어진 수열에서 숫자를 하나씩 떼어내려면 총 6번을 하나씩 떼어내야 합니다. 7보다 1만큼 작은 이유는 마지막에 숫자 두개만 남았을 때 한번만 떼어내면 되기 때문입니다. 숫자가 N개 있으면 N-1번 떼어내야 합니다. 따라서 N에 대해 선형적이므로 분할 과정은 O(N)입니다. 이제 정복 과정을 살펴봅시다. 정복은 같은 레벨의 파티션들을 쌍을 이룬 후, 정렬하며 하나의 파티션으로 병합하는 과정입니..

오늘 배운 점 갑자기 떠오른 아이디어가 실마리가 될 수 있습니다. 빠를거라고 예상한 풀이가 예상외로 느릴 수 있습니다. 문제 - 디펜스 게임 문제링크 문제 설명 병사 n명으로 enemy([n1, n2, n3,...])을 상대해야 합니다. 1라운드에는 n1, 2라운드에는 n2... 이런식으로 각 라운드마다 상대해야 하는 적의 수가 enemy에 담겨 있습니다. 그리고 병사와 적은 1대1 교환비로 적을 처리할 수 있습니다. k개의 무적권이 주어지는데, 무적권 1개를 사용하면 해당 라운드는 병사를 사용하지 않고 다음 라운드로 넘어갈 수 있습니다. 이때, 승리할 수 있는 최대 라운드를 구하면 됩니다. 제약 조건 n이 10억인 점은 문제가 되지 않지만 enemy가 100만이기 때문에 O(N)이나 O(NlogN) 과..

문제 - 등산코스 정하기 문제링크문제 설명산이 있고 산에는 지점들이 있습니다. 지점은 여러 개의 출발지와 여러 개의 정상, 그리고 일반 지점들이 있습니다. 출발지에서 시작해서 정상을 찍고 다시 원래 출발지로 돌아오는 경로가 있을 때, 해당 경로는 시작 출발지와 끝 출발지는 같고, 중간에 다른 출발지를 거치지 않고, 정상은 무조건 한번만 거쳐야 합니다. 이때, 위 조건을 만족하는 모든 경로 각각에서 각 지점을 건너는데 걸리는 시간 중 가장 긴 시간이 있을텐데 이를 intensity라 하고, 모든 경로를 통틀어 최소 intensity를 구하는 문제입니다. 풀이 과정처음에는 같은 지점을 여러번 반복해서 방문할 수 있으므로, 비트마스킹을 이용헤서 중복 경로 체크를 해야 하는 줄 알았습니다. 하지만 이전에 방문한..

문제 - 무인도 여행 문제링크 문제 설명 2차원 격자 maps가 주어지고, 격자는 바다를 의미하는 'X'와 1~9 사이의 숫자로 이루어져 있습니다. 해당 칸이 숫자라면 땅을 의미하고, 상하좌우로 서로 연결된 땅은 하나의 섬입니다. maps 내의 모든 섬에 방문할 때, 각 섬에 적혀있는 모든 숫자를 다 더한 값을 담아 반환하면 됩니다. 풀이 과정 일반적인 BFS 섬 찾기 문제입니다. maps를 2중 for 문 순회하며 섬을 찾아 마킹하며 숫자를 더한 후 BFS가 끝나면 더한 값을 저장해 놓다가 모든 순회가 끝나면 반환하면 됩니다. from collections import deque def solution(maps): answer = [] n = len(maps) m = len(maps[0]) dx = [..

문제 - 택배상자 문제링크 오늘 배운 점스택의 활용도는 무궁무진하고 어렵습니다. 획기적인 풀이가 답이 될 수 있는 이유를 알고 넘어가는건 재밌습니다. 문제 설명메인 컨베이어 벨트에 1부터 n의 번호가 달린 상자가 n,n-1,...3,2,1 이런식으로 정렬되어 왼쪽에서 오른쪽으로 이동하고 있습니다. 그리고, 택배원은 자기가 생각한 순서대로 상자를 트럭에 실어야 합니다. 택배원은 보조 컨베이어벨트에 상자를 차곡차곡 옮길 수도 있습니다. 보조 컨베이어벨트는 스택같은 LIFO 구조라고 보면 됩니다. 이때 택배원은 최대 몇개의 상자를 트럭에 실을 수 있는지 구하는 문제입니다. 풀이 과정세 가지 경우로 나누어 풀이했습니다. 1. 메인 컨베이어 벨트의 맨 앞 상자가 자신이 처리해야 하는 상자와 같을 때 2. 보조 컨..

오늘 배운 점 중복코드는 함수화해보자. 문제1 - 이중 우선순위 큐 문제링크 문제 설명 이중 우선순위 큐를 구현해야 한다. 이중 우선순위큐란 큐 내의 최댓값과 최솟값을 모두 구할 수 있는 자료구조입니다. 3가지 연산이 주어집니다. 풀이 과정 일단, 우선순위 큐 하나만 가지고는 최대힙이나 최소힙 하나만 구현할 수 있을거라고 생각해서 최대힙, 최소힙을 각각 하나씩 가지는 Depq 클래스를 만들었습니다. 이후 숫자를 삽입할 땐 양 쪽 힙에 모두 넣어주고, 최댓값을 제거할 땐 최대힙에서 pop하고, 최솟값을 제거할 땐 최소힙에서 pop하면 되겠다고 생각했습니다. 하지만 이대로 코드를 작성한다면 한쪽 힙에서 제거한 숫자가 여전히 다른쪽 힙에 남아있게 되기 때문에 추가 작업이 필요했습니다. 그래서 각각의 힙에서 삭..

문제 - 피로도 문제링크 오늘 배운 점 일단 최적화 신경쓰지 말고 풀어놓고 생각하자 문제 설명 최대한 많은 던전을 탐험해야 하는 문제입니다. 던전 정보 리스트 dungeons는 [[최소 필요 피로도, 소모 피로도], ...]로 주어지며 현재 가지고 있는 피로도 k가 최소 필요 피로도 이상이어야 소모 피로도를 소비하고 던전에 입장할 수 있습니다. 가지고 있는 피로도k와 던전 리스트dungeons가 주어질 때, 최대 던전 탐험 횟수를 구하면 됩니다. 풀이 과정 처음 이 문제를 봤을 때는 DFS 풀이가 생각났습니다. 생각난 대로 풀면 되는데 뭔가 최적화를 하고싶어서 뭔가 피로도를 정렬한 후 for문과 힙을 사용하면 스케쥴러나 철로문제처럼 풀 수 있지 않을까 싶어 더 생각해보았지만 예외케이스를 처리할 방법이 생..