매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.
섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)
Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다. Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.
제한 사항
scoville의 길이는 1 이상 1,000,000 이하입니다.
K는 0 이상 1,000,000,000 이하입니다.
scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.
힙을 이용해 최대/최소 원소를 빠르게 찾자!
연산
힙 구성(heapify)
삽입(insert) - O(logn)
삭제(remove) - O(logn)
코드 구현
import heapq
def solution(scoville, K):
#heapq.heapify(L)
#리스트 L로부터 min heap 구성
#m = heapq.heappop(L)
#min heap L에서 최소값 삭제(반환)
#heapq.heappush(L, x)
#min heap L에 원소 x 삽입
answer = 0
heapq.heapify(scoville)
while True:
min1 = heapq.heappop(scoville)
if min1>=K:
break
elif len(scoville)==0:
return -1
else:
min2 = heapq.heappop(scoville)
new_scoville = min1 + 2*min2
heapq.heappush(scoville, new_scoville)
answer+=1
return answer
5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다. 이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.
제한사항
N은 1 이상 9 이하입니다.
number는 1 이상 32,000 이하입니다.
수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
최솟값이 8보다 크면 -1을 return 합니다.
동적계획법(Dynamic Programming)
동적 계획법? 주로 최적화 문제를 재귀적인 방식으로
보다 작은 부분 문제로 나눠 부분 문제를 풀어, 이 해를 조합하여
전체 문제의 해답에 이르는 방식
알고리즘 진행에 따라 탐색해야 할 범위를 동적으로 결정함으로써 탐색 범위를 한정할 수 있다.
동적계획법 적용 예 - 피보나치 수열
재귀함수로 구현한다면?
f(4) = f(3) + f(2)
f(3) = f(2) + f(1) + f(1) + f(0)
f(2) = f(1) + f(0) + f(1) + f(1) + f(0)
복잡도가 지수함수의 형태로 나타나게 된다.
동적 계획법을 적용한다면?
f(0) = 0, f(1) =1
f(2) = f(1) + f(1) = 2
f(3) = f(2) + f(1) = 2
f(4) = f(3) + f(2) = 3
복잡도가 선형함수의 형태로 나타나게 된다.
동적계획법 적용 예 - Knapsack Problem
=> 가장 높은 값을 가지도록 물건들을 골라 배낭에 담으시오.
코드 구현
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, len(s)):
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
깊이/너비 우선 탐색(DFS/BFS)
여행경로
주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.
항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.
제한사항
모든 공항은 알파벳 대문자 3글자로 이루어집니다.
주어진 공항 수는 3개 이상 10,000개 이하입니다.
tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
주어진 항공권은 모두 사용해야 합니다.
만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.
그래프 (graphs)
정점(vertex, node)과 간선(edge, link)
유향(directed) 그래프와 무향(undirected) 그래프
스택으로 구현했을 때와 큐로 구현했을 때를 알아두면 좋음.
알고리즘 설계
스택을 이용하여 재귀적 '한 붓 그리기' 문제를 해결
DFS를 응용한 문제
코드 구현
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]
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.
제한사항
마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
completion의 길이는 participant의 길이보다 1 작습니다.
참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
참가자 중에는 동명이인이 있을 수 있습니다.
해시란? 해시 테이블이라고 불리우는 저장공간에다 키들이 어느 위치에 있을지 정해 해시 테이블에 값을 저장하는 것.
값들의 위치를 결정하는데에는 hash function이 이용된다. 해시 테이블의 각각의 저장공간을 hash bucket이라고 한다.
코드 구현
def solution(participant, completion):
d = {}
for x in participant:
d[x] = d.get(x,0) +1 #get(x,0) x가 존재하면 키에 해당하는 값을, 존재하지 않으면 0을 return
for x in completion:
d[x] -= 1
dnf = [k for k, v in d.items() if v > 0]
answer = dnf[0]
return answer
시간복잡도 : O(n)
탐욕법
체육복
점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.
전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.
제한사항
전체 학생의 수는 2명 이상 30명 이하입니다.
체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.
탐욕법이란? 알고리즘의 각 단계에서 그 순간 최적이라고 생각되는 것을 선택
현재의 선택이 마지막 해답의 최적성을 해치지 않을 때 탐욕법 활용 가능
코드 구현
def solution(n, lost, reserve):
u = [1]*(n+2)
for i in reserve:
u[i]+=1
for i in lost:
u[i]-=1
for i in range(1, n+1):
if u[i-1]==0 and u[i]==2:
u[i-1:i+1]=[1,1]
elif u[i] == 2 and u[i+1] == 0:
u[i:i+2]=[1,1]
return len([x for x in u[1:-1] if x > 0])
시간복잡도 : O(n)
def solution(n, lost, reserve):
s = set(lost) & set(reserve)
l = set(lost) - s
r = set(reserve) - s
for x in sorted(r):
if x-1 in l:
l.remove(x-1)
elif x+1 in l:
l.remove(x+1)
return n-len(l)
시간복잡도 : O(klogk)
정렬
가장 큰 수
0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.
제한 사항
numbers의 길이는 1 이상 100,000 이하입니다.
numbers의 원소는 0 이상 1,000 이하입니다.
정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.
문제 해결 방법
빈 문자열로 수 초기화
수 목록을 (크게 만드는 것 우선) 정렬
목록에서 하나씩 꺼내 현재 수에 이어 붙인다.
모든 수를 다 사용할 때까지 반복
알고리즘 설계
대소 관계 비교를 위한 기준 마련
기준을 이용해 주어진 배열 정렬
정렬된 배열을 이용해 문자열 표현 완성
코드 구현
def solution(numbers):
numbers = [str(x) for x in numbers]
numbers.sort(key=lambda x : (x*4)[:4], reverse=True)
if numbers[0]=='0':
answer='0'
else:
answer = ''.join(numbers)
return answer
시간복잡도 : O(nlogn) (정렬하면서..)
탐욕법
큰 수 만들기
어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.
문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.
제한 조건
number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
k는 1 이상 number의 자릿수 미만인 자연수입니다.
문제 해결 방법
큰 수가 앞 자리에, 작은 수가 뒷 자리에 놓이도록 한다.
알고리즘 설계
주어진 숫자로부터 하나씩 꺼내 모은다.
이 때, 이미 모아둔 것 중 지금 등장한 것보다 작은 것들은 빼낸다.
모은 숫자들을 자릿수 맞춰 반환한다.
아직 뺄 개수를 채우지 못한 경우를 고려한다.
코드 구현
def solution(number, k):
collected = []
for i, num in enumerate(number):
while len(collected)>0 and collected[-1]<num and k>0:
#아직까지 빼낼 게 남아있고 (k>0)
#마지막 글자가 현재 글자보다 작고 (collected[-1]<num)
#collected의 길이가 0보다 클 때동안 (len(collected)>0)
collected.pop()
k-=1
if k==0:
collected += list(number[i:])
break
collected.append(num)
collected = collected[:-k] if k>0 else collected
#만약 k가 0보다 크면 즉, 잘라야 할 문자가 남았다면 맨 뒤부터 남은 문자 갯수만큼 잘라준다.
return ''.join(collected)
출력 연산자이면 스택에서 이보다 높거나 같은 우선순위 것들을 pop, 출력 그리고 이 연산자는 스택에 push
스택에 남아 있는 연산자는 모두 pop, 출력
코드 구현
class ArrayStack:
def __init__(self):
self.data = []
def size(self):
return len(self.data)
def isEmpty(self):
return self.size() == 0
def push(self, item):
self.data.append(item)
def pop(self):
return self.data.pop()
def peek(self):
return self.data[-1]
prec = {
'*': 3, '/': 3,
'+': 2, '-': 2,
'(': 1
}
def solution(S):
opStack = ArrayStack()
answer=''
for i in S:
if i not in prec and i!=')': #비연산자면 바로 출력
answer+=i
else:
if opStack.isEmpty() or i=='(': #스택이 비어있거나 '('연산자일 시 바로 스택에 push
opStack.push(i)
else:
if i==')': #'('가 나올때까지 스택에서 pop
while opStack.peek()!='(':
answer+=opStack.pop()
opStack.pop() #'('빼기
else:
while opStack.size()!=0 and prec[opStack.peek()]>=prec[i]:
answer+=opStack.pop()
opStack.push(i)
for i in range(opStack.size()):
answer+=opStack.pop()
return answer
후위 표기 수식 계산
후위 표기된 수식을 계산하기
알고리즘 설계
후위 표현식을 왼쪽부터 한 글자씩 읽는다
피연산자면 스택에 push한다
연산자를 만나면 스택에서 pop한다. =>(1)
또 pop한다. =>(2)
(2) 연산 (1)을 계산한다. 이 결과를 스택에 push한다.
수식의 끝에 도달하면 스택에서 pop한다. => 계산 결과
코드 구현
class ArrayStack:
def __init__(self):
self.data = []
def size(self):
return len(self.data)
def isEmpty(self):
return self.size() == 0
def push(self, item):
self.data.append(item)
def pop(self):
return self.data.pop()
def peek(self):
return self.data[-1]
def splitTokens(exprStr):
tokens = []
val = 0
valProcessing = False
for c in exprStr:
if c == ' ':
continue
if c in '0123456789':
val = val * 10 + int(c)
valProcessing = True
else:
if valProcessing:
tokens.append(val)
val = 0
valProcessing = False
tokens.append(c)
if valProcessing:
tokens.append(val)
return tokens
def infixToPostfix(tokenList):
prec = {
'*': 3,
'/': 3,
'+': 2,
'-': 2,
'(': 1,
}
opStack = ArrayStack()
postfixList = []
for token in tokenList:
if type(token) is int:
postfixList.append(token)
elif token=='(':
opStack.push(token)
elif token==')':
while opStack.peek()!='(':
postfixList.append(opStack.pop())
opStack.pop()
else:
while opStack.size()!=0 and prec[opStack.peek()]>=prec[token]:
postfixList.append(opStack.pop())
opStack.push(token)
while not opStack.isEmpty():
postfixList.append(opStack.pop())
return postfixList
def postfixEval(tokenList):
valStack = ArrayStack()
for token in tokenList:
if type(token) is int:
valStack.push(token)
elif token=='*':
a=valStack.pop()
b=valStack.pop()
valStack.push(b*a)
elif token=='/':
a=valStack.pop()
b=valStack.pop()
valStack.push(b/a)
elif token=='+':
a=valStack.pop()
b=valStack.pop()
valStack.push(b+a)
elif token=='-':
a=valStack.pop()
b=valStack.pop()
valStack.push(b-a)
return valStack.pop()
def solution(expr):
tokens = splitTokens(expr)
postfix = infixToPostfix(tokens)
val = postfixEval(postfix)
return val
너무 지저분해 보인다..^^;
큐
큐란? 선입선출(FIFO : First In First Out)의 특징을 갖는 선형 자료구조 (ex : 영화관 입장 / 식당 입장 대기열)
삭제되는 노드보다 바로 다음 키를 갖는 노드를 찾아 그 노드를 삭제되는 노드 자리에 대신 배치
코드 구현
class Node:
def __init__(self, key, data):
self.key = key
self.data = data
self.left = None
self.right = None
def insert(self, key, data):
if key < self.key:
if self.left:
self.left.insert(key, data)
else:
self.left = Node(key, data)
elif key > self.key:
if self.right:
self.right.insert(key, data)
else:
self.right = Node(key, data)
else:
raise KeyError('Key %s already exists.' % key)
def lookup(self, key, parent=None):
if key < self.key:
if self.left:
return self.left.lookup(key, self)
else:
return None, None
elif key > self.key:
if self.right:
return self.right.lookup(key, self)
else:
return None, None
else:
return self, parent
def inorder(self):
traversal = []
if self.left:
traversal += self.left.inorder()
traversal.append(self)
if self.right:
traversal += self.right.inorder()
return traversal
def countChildren(self):
count = 0
if self.left:
count += 1
if self.right:
count += 1
return count
class BinSearchTree:
def __init__(self):
self.root = None
def insert(self, key, data):
if self.root:
self.root.insert(key, data)
else:
self.root = Node(key, data)
def lookup(self, key):
if self.root:
return self.root.lookup(key)
else:
return None, None
def remove(self, key):
node, parent = self.lookup(key)
if node:
nChildren = node.countChildren()
# The simplest case of no children
if nChildren == 0:
# 만약 parent 가 있으면
# node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
# parent.left 또는 parent.right 를 None 으로 하여
# leaf node 였던 자식을 트리에서 끊어내어 없앱니다.
if parent:
if parent.left == node:
parent.left = None
else:
parent.right = None
# 만약 parent 가 없으면 (node 는 root 인 경우)
# self.root 를 None 으로 하여 빈 트리로 만듭니다.
else:
self.root=None
# When the node has only one child
elif nChildren == 1:
# 하나 있는 자식이 왼쪽인지 오른쪽인지를 판단하여
# 그 자식을 어떤 변수가 가리키도록 합니다.
if node.left:
child = node.left
else:
child = node.right
# 만약 parent 가 있으면
# node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
# 위에서 가리킨 자식을 대신 node 의 자리에 넣습니다.
if parent:
if parent.left == node:
parent.left = child
else:
parent.right = child
# 만약 parent 가 없으면 (node 는 root 인 경우)
# self.root 에 위에서 가리킨 자식을 대신 넣습니다.
else:
self.root = child
# When the node has both left and right children
else:
parent = node
successor = node.right
# parent 는 node 를 가리키고 있고,
# successor 는 node 의 오른쪽 자식을 가리키고 있으므로
# successor 로부터 왼쪽 자식의 링크를 반복하여 따라감으로써
# 순환문이 종료할 때 successor 는 바로 다음 키를 가진 노드를,
# 그리고 parent 는 그 노드의 부모 노드를 가리키도록 찾아냅니다.
while successor.left:
parent = successor
successor = successor.left
# 삭제하려는 노드인 node 에 successor 의 key 와 data 를 대입합니다.
node.key = successor.key
node.data = successor.data
if parent.left == successor:
parent.left =successor.right
else:
parent.right = successor.right
# 이제, successor 가 parent 의 왼쪽 자식인지 오른쪽 자식인지를 판단하여
# 그에 따라 parent.left 또는 parent.right 를
# successor 가 가지고 있던 (없을 수도 있지만) 자식을 가리키도록 합니다.
return True
else:
return False
def inorder(self):
if self.root:
return self.root.inorder()
else:
return []
이진 탐색 트리는 특정 키 값을 가지는 원소를 빠르게 검색할 수 있으나, 힙은 특정한 키 값이 어느 트리에 들어있는가를 알아내는데 좋은 방법이 없다.
힙은 이진 탐색 트리에 비해 완전 이진 트리여야 한다는 부가의 제약 조건이 있다.
연산 정의
__init__() - 빈 최대 힙 생성
insert(item) - 새로운 원소 삽입
remove() - 최대 원소 (root node) 반환과 동시에 삭제
배열을 이용한 최대힙의 표현
노드 번호 m을 기준으로
왼쪽 자식 번호 : 2*m
오른쪽 자식 번호 : 2*m+1
부모 노드의 번호 : m//2
완전 이진 트리이므로 노드의 추가 / 삭제는 마지막 노드에서만 이뤄진다.
최대 힙에 원소 삽입
트리의 마지막 자리에 새로운 원소 임시 저장
부모 노드와 키 값을 비교해 위로 이동
복잡도 = 부모 노드와의 대소 비교 최대 회수 => log₂n
∴ 최악 복잡도 O(logn)의 삽입 연산
최대 힙에 원소 삭제
루트 노드 제거 - 이것이 원소들 중 최댓값
트리 마지막 자리 노드를 임시로 루트 노드 자리에 배치
자식 노드들과 값을 비교해 아래로 이동
자식이 둘이 있다면 더 큰 값을 기준으로 아래로 이동하게 된다.
복잡도 = 자식 노드들과의 대소 비교 최대 회수 => 2log₂n
∴ 최악 복잡도 O(logn)의 삭제 연산
코드 구현
class MaxHeap:
def __init__(self):
self.data = [None]
def insert(self, item):
self.data.append(item)
idx = len(self.data)-1
while idx != 1:
parent = idx//2
if self.data[parent] < self.data[idx]:
self.data[parent],self.data[idx] = self.data[idx], self.data[parent]
idx = parent
else:
break
def remove(self):
if len(self.data) > 1:
self.data[1], self.data[-1] = self.data[-1], self.data[1]
data = self.data.pop(-1)
self.maxHeapify(1)
else:
data = None
return data
def maxHeapify(self, i):
# 왼쪽 자식 (left child) 의 인덱스를 계산합니다.
left = 2*i
# 오른쪽 자식 (right child) 의 인덱스를 계산합니다.
right = 2*i+1
greatest = i
# 왼쪽 자식이 존재하는지, 그리고 왼쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단합니다.
if left<len(self.data) and self.data[left]>self.data[greatest]:
# 조건이 만족하는 경우, smallest 는 왼쪽 자식의 인덱스를 가집니다.
greatest=left
# 오른쪽 자식이 존재하는지, 그리고 오른쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단합니다.
if right<len(self.data) and self.data[right]>self.data[smallest]:
# 조건이 만족하는 경우, smallest 는 오른쪽 자식의 인덱스를 가집니다.
greatest=right
if greatest != i:
# 현재 노드 (인덱스 i) 와 최댓값 노드 (왼쪽 아니면 오른쪽 자식) 를 교체합니다.
self.data[i],self.data[greatest]=self.data[greatest],self.data[i]
# 재귀적 호출을 이용하여 최대 힙의 성질을 만족할 때까지 트리를 정리합니다.
self.maxHeapify(greatest)
def heapsort(unsorted):
H = MaxHeap()
for item in unsorted:
H.insert(item)
sorted = []
d = H.remove()
while d :
sorted.append(d)
d = H.remove()
return sorted
