코딩테스트 낙서장
~
원래 C++로 준비했었으나, 새로운 마음으로 준비하기 위해 Python으로 갈아탔습니다.
코딩테스트 준비 과정에서 문법적, 테크닉적으로 필요하겠다 싶은 것들을 기록하는 글입니다.
이차원 리스트
# 0으로 초기화된 N*M 리스트 선언
lst = [
[0 for _ in range(M)]
for _ in range(N)
]
input() -> sys.stdin.readline()
sys.stdin.readline()의 입력 처리 속도가 더 빠릅니다.import sys n = int(sys.stdin.readline())
map
- 동시에 여러 값을 입력받기 위해 사용합니다.
x, y = tuple(map(int, input().split())) # x, y lst = map(int, input().split()) # lst lst2 = map(int, sys.stdin.readline().split()) # sys.stdin.readline().strip(): readline()은 문자열 뒤에 개행문자가 붙는데, 이를 제거하는 함수이다.
최빈값 구하기
from collections import Counter
...
mod = Counter(lst).most_common(n) # n 생략시 1
# [(idx1, mod1), (idx2, mod2)] 꼴로 return 됨.
문자열<->리스트
- 문자열에 sort함수를 사용하는 등의 경우에 사용합니다.
import sys
N = sys.stdin.readline()
temp = list(N)
temp.sort(reverse=True)
N = ''.join(temp)
print(N)
객체 리스트 정렬시 다중 조건 적용하기
C.sort(key=lambda c: (c.x, c.y))
'''
x와 y를 멤버 변수로 가지는 Coordinate 클래스가 담긴 객체 리스트 C를 정렬하는 것.(백준 11650번 문제)
c는 object로 임의 지정.
'''
백준 14889번 문제
- Silver II 난이도의 백트래킹 문제입니다. 처음 짠 알고리즘에서 점수를 구하는 부분이 비효율적인줄 알고 2시간을 투자했으나, backtracking 하는 부분이 비효율적이었다는 사실에 심히 통탄하고 이렇게 적습니다..
import sys
MIN_DIF = 999
def backtracking(start_idx, cnt):
if cnt == N/2:
global MIN_DIF
team_start = 0
team_link = 0
'''
처음에 이 부분에서 시간을 많이 잡아먹는 줄 알고 O(N^2)를 줄이고자 2시간을 투자하였다.
하지만 그 어떤 방식으로도 해결할 수 없었다.
'''
for i in range(N-1):
for j in range(i+1, N):
if checking[i] and checking[j]:
team_start += team[i][j] + team[j][i] # lst[lst_[i]] 꼴의 참조는 시간을 더 잡아먹는다고 한다.
elif not checking[i] and not checking[j]:
team_link += team[i][j] + team[j][i]
dif = abs(team_start - team_link)
MIN_DIF = min(MIN_DIF, dif)
return
'''
해당 부분에서 continue를 통해 backtracking을 하면 비효율적이다.
- 아래 구문을 사용했을 때 '시간 초과' 발생
for i in range(N):
if checking[i]:
continue
start_idx 변수를 통해 경우의 수를 최대한 줄여주자.
'''
for i in range(start_idx, N):
checking[i] = 1
backtracking(i + 1, cnt + 1)
checking[i] = 0
N = int(sys.stdin.readline())
team = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
checking = [0] * N
backtracking(0, 0)
print(MIN_DIF)
백준 15663번 문제
- Silver II의 백트래킹 문제입니다. 기존 값을 저장하기 위해 global list에 deepcopy를 사용해보았습니다.
import sys
BEFORE = []
RESULT = []
def backtracking(idx):
global BEROFE
if idx == M:
if RESULT not in BEFORE:
BEFORE.append(RESULT[:]) # BEFORE는 지워지면 안되므로 deepcopy
output = " ".join(RESULT)
print(output)
return
for i in range(idx, N):
RESULT.append(str(lst[i]))
backtracking(idx+1)
RESULT.pop()
N, M = tuple(map(int, sys.stdin.readline().split()))
lst = list(map(int, sys.stdin.readline().split()))
lst.sort()
backtracking(0)
백준 15663번 문제
- Silver II 백트래킹 문제입니다. N과 M 시리즈 중에서 2번째로 정답 비율이 낮은 문제입니다. 주어진 N개의 자연수 중에서 M개를 고른 수열을 구하면 되는데 중복되는 수열은 한 번만 출력해야 합니다. 처음 시도했던 방법은 일일히 수열을 구해 RESULT 리스트에 없으면 저장하고, 모든 경우의 수를 다 구한 후 출력하는 방식이었는데 시간초과가 났습니다.
- 이후 backtracking 함수 내부의 for문에서 checking[i]가 직전 숫자와 같다면 거르는 구문을 추가하고, RESULT 리스트에 추가하는게 아닌 바로 출력하는 방식으로 고쳤더니 통과되었습니다.
- 문제를 풀다 집중력이 떨어져 쓸 데 없는 경우의 수 까지 고려해, 쉽게 갈 수 있던 문제를 빙빙 돌아온 것 같습니다.
import sys
RESULT = []
def backtracking(cnt):
if cnt == M:
print(" ".join(RESULT))
return
prev_num = -1
for i in range(N):
if checking[i] == 0 and prev_num != lst[i]:
RESULT[cnt] = str(lst[i])
checking[i] = 1
backtracking(cnt+1)
prev_num = lst[i]
checking[i] = 0
N, M = tuple(map(int, sys.stdin.readline().split()))
lst = list(map(int, sys.stdin.readline().split()))
lst.sort()
checking = [0] * 10001
RESULT = [-2] * M
backtracking(0)
2차원 리스트 슬라이싱
temp = [row[c:c+j] for row in lst[r:r+i]]
리스트에서 값의 위치 찾기, 삽입하기, 삭제하기
# 리스트: lst, 값: city
# 특정 값의 위치 찾기
idx = lst.index(city)
# 삽입 1
lst.append(city) # 마지막 위치에 삽입
# 삽입 2
lst.insert(idx, city) # 해당 위치에 값 삽입
# 삭제 1(마지막 값)
lst.pop()
# 삭제 2(값 이용)
lst.remove(city)
# 삭제 3(위치 이용)
del lst[idx]
Stack
- 스택이 따로 없기 때문에 리스트를 사용한다.
stack = []
# Push
stack.append(x)
# Pop
stack.pop()
# Top
stack[-1]
# Size
len(stack)
# Empty
False if len(stack) else True # True if len(stack) > 0 else False
백준 1038번 문제
'''
백준 1038번 문제
Gold V, Backtracking + Brute force
처음엔 Brute force로 풀어보았으나, 역시 재귀의 깊이가 깊어져 오류가 발생했다.
1. 생각을 해보면 조건에 맞는 숫자들 중 가장 큰 숫자는 9876543210이다.
2. 그렇다면 0부터 9까지의 숫자들로 1~10자리의 조합을 만들어서 리스트에 저장하면 N번째 숫자가 무엇인지 알 수 있지 않을까?
3. 조합은 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [01] [02] [03] ... 꼴로 만들어진다.
4. 따라서 만들어진 조합을 내림차순으로 정렬해서 문자열로 변환한 것을 정수형으로 변환해 리스트에 저장하면 되지 않을까?
5. 리스트 요소들을 문자열로 만들기 위해서는 리스트 요소들이 '문자열'이어야 한다. 하지만 리스트의 요소들은 정수형이다.
6. 따라서 우선 리스트 요소들을 문자열로 변환하기 위해 map함수를 이용해 리스트의 요소들을 문자열로 바꿔줘야 한다.
7. 그것을 정수형으로 변환해 리스트에 저장하자.
8. N은 1부터 1,000,000까지 주어진다. 리스트에 N으로 접근해서 N번째 숫자가 있다면 결과값이 return될 것이고, N번째 숫자가 없다면 index error가 발생할 것이다.
9. 그렇다면 일단 리스트의 N번째 요소를 부르자. 예외처리를 사용하면 값이 없을 때 index error가 발생해 예외처리 구문이 실행될 것이다.
itertools로 조합을 만들어 내림차순으로 정렬하면 감소하는 숫자가 만들어진다.
그것을 number list에 저장 후, 오름차순으로 정렬하면 우리가 문제를 푸는데 필요한 list가 만들어진다.
map(function, iterable): iterable(list 등)을 function 함수를 적용해 return.
map(str, lst) = lst의 요소들을 string화 시킨 list가 return된다.
'''
from itertools import combinations
import sys
input = sys.stdin.readline
N = int(input())
numbers = list()
for i in range(1, 11):
for combi in combinations(range(0, 10), i):
combi = list(combi)
combi.sort(reverse=True)
numbers.append(int("".join(map(str, combi))))
numbers.sort()
try:
print(numbers[N])
except:
print(-1)
Counter
- 문자열의 갯수를 세는 방법은 dictionary를 사용하는 방법도 있지만, Counter 라이브러리를 사용할 수도 있습니다.
Counter(문자열).most_common(1)[0]의 [0]은 글자, [1]은 글자수 입니다.
from collections import Counter
str = "MyLifeWouldSuckWithOut You"
# Use Dictionary
str.lower()
counter = {}
for s in str:
if s not in counter:
counter[s] = 0
counter[s] += 1
print(counter)
print()
# Use Counter
cntr = Counter(str) # 자동 정렬되어 제공됨
print(cntr) # SET로 return
print(cntr.most_common()) # SET
print(cntr.most_common(1)) # SET를 LIST로 return
print(cntr.most_common(1)[0][0])
print(cntr.most_common(1)[0][1])
Set Recursion Limit
- 파이썬으로 DFS 등 재귀를 사용하는 문제를 풀다보면 재귀의 깊이가 깊어져 오류가 나는 경우가 있습니다. 파이썬의 재귀 깊이 제한은 1000인데, 이것을 풀 수 있는 방법이 있습니다.
import sys
sys.setrecursionlimit(10000)
프로그래머스 코딩테스트 연습 > 깊이/너비 우선 탐색(DFS/BFS) > 여행경로
- level 3의 DFS/BFS 문제입니다. 코드의 주석에 문제를 풀던 과정이 기재되어 있습니다. 코드를 덧붙이고 덧붙이다보니 조금 복잡해진 것 같은데, 처음부터 counting dictionary를 사용했다면 조금 더 깔끔한 코드가 되었을 것 같아 아쉽습니다.
'''
https://programmers.co.kr/learn/courses/30/lessons/43164
DFS/BFS 문제.
출발지를 key로, 도착지를 value의 list로 하는 dictionary, 중복표를 위한 counting dictionary를 사용함.
Hash의 key로 변할 수 있는 값을 사용할 수 없기 때문에 tuple로 바꾸어 줌.
1. 백트래킹을 제대로 하지 못함(1, 2? 4? 오류) -> 해결
2. 표가 중복인 경우를 찾지 못함 -> counting dictionary를 추가 -> (1 오류)
3. 문제의 조건이 잘못되었다? -> 그건 잘 모르겠고 문제 설명이 조금은 불친절하긴 하다.
4. 왜 ICN이 처음에 없는가?(이거다) -> DFS 내부 로직에 문제가 있다.
-> 중복을 고려하면서 (앞에서부터 지우는) remove를 사용했던게 문제 -> 아니 애초에 pop을 썼으면 됐잖아 DFS는 STACK이라고 STACK!
'''
answer = []
custom_tickets = {}
ticket_counting = {}
def DFS(ticket, used_tickets, tickets, used_counting):
global answer, custom_tickets, ticket_counting
if len(used_tickets) == len(tickets):
temp = [used_tickets[0][0]]
for i in range(len(used_tickets)):
temp.append(used_tickets[i][1])
answer.append(temp[:])
return
# 예외처리
if ticket[1] not in custom_tickets:
return
for dest in custom_tickets[ticket[1]]:
next_ticket = (ticket[1], dest)
if used_counting[next_ticket] < ticket_counting[next_ticket]:
used_tickets.append(next_ticket)
used_counting[next_ticket] += 1
DFS(next_ticket, used_tickets, tickets, used_counting)
# used_counting.remove(next_ticket)
used_tickets.pop()
used_counting[next_ticket] -= 1
def solution(tickets):
global answer, ticket_counting
used_tickets = []
used_counting = {}
# Preprocessing
for ticket in tickets:
if ticket[0] not in custom_tickets:
custom_tickets[ticket[0]] = list()
custom_tickets[ticket[0]].append(ticket[1])
if tuple(ticket) not in ticket_counting:
ticket_counting[tuple(ticket)] = 0
used_counting[tuple(ticket)] = 0
ticket_counting[tuple(ticket)] += 1
# Processing
for dest in custom_tickets['ICN']:
ticket = ('ICN', dest)
if used_counting[ticket] < ticket_counting[ticket]:
used_tickets.append(ticket)
used_counting[ticket] += 1
DFS(ticket, used_tickets, tickets, used_counting)
# used_tickets.remove(ticket)
used_tickets.pop()
used_counting[ticket] -= 1
answer.sort()
answer = answer[0]
return answer
tickets = [["ICN","A"],['ICN', 'B'], ['B','ICN']]
answer = solution(tickets)
print(answer)
프로그래머스 코딩테스트 연습 > 탐욕법(Greedy) > 큰 수 만들기
- level 2의 탐욕법(Greedy) 문제입니다. 문제의 방향을 잡지 못했으나, 그 과정이 주석의 참조1 링크의 내용과 같아 참조했습니다.
'''
문제: https://programmers.co.kr/learn/courses/30/lessons/42883
참조1: https://velog.io/@soo5717/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%81%B0-%EC%88%98-%EB%A7%8C%EB%93%A4%EA%B8%B0-%ED%8C%8C%EC%9D%B4%EC%8D%AC
참조2: https://programmers.co.kr/questions/25858
-> 탐욕법이나 DP나 이론만 대충 알고있었는데, 막상 코드를 짜보니 막막하다.
'''
def solution(number, k):
stack = []
# 앞에서부터, 뒷 숫자보다 작으면 총 k개 삭제하는 알고리즘
for n in number:
if not len(stack):
stack.append(n)
else:
if k > 0:
while stack[-1] < n:
stack.pop()
k -= 1
# 앞의 숫자를 다 지운 경우 // 총 개수를 다 지운 경우(하단 else)
if not len(stack) or k <= 0:
break
stack.append(n)
# if문의 경우, 앞의 숫자를 다 지웠으나 k개 만큼 지우지 못했다면 맨 뒷쪽에서 남은 갯수만큼 지워주면 된다.
stack = stack[:-k] if k > 0 else stack
return ''.join(stack)
number = "654321"
k = 1
answer = solution(number, k)
print(answer)
프로그래머스 > 코딩테스트 연습 > 그래프 > 가장 먼 노드(Level 3)
- 최초 실행 코드에서 custom의 사이즈를 줄여 해결했습니다. 하단의 기존 코드에서는 custom을 n+1만큼 선언하고 BFS애서 반복문을 N만큼 돌렸는데, 통과 코드에서는 custom을 edge 수만큼 append 연산을 해주고 BFS에서 해당 edge의 수만큼만 반복문을 돌렸습니다. 이 차이가 7~9번 테스트 케이스의 시간 초과를 해결해준 것 같습니다.
- 잘은 모르겠으나, 통과 코드가 다익스트라 알고리즘과 유사해보입니다.
'''
https://programmers.co.kr/learn/courses/30/lessons/49189
TMI: 코드 분석(solution)
- 기존 코드: O(N) + O(N) = 2N = N
- 통과 코드: O(N log N) + O(1) = N log N + 1 = N log N
-> sort보다는 원래 쓰던 max + count 조합을 쓰자.
'''
# 통과 코드
from queue import Queue
q = Queue()
def BFS(custom, node, n):
q.put(n)
while not q.empty():
curnode = q.get()
for e in custom[curnode]:
if node[curnode]+1 < node[e]: # 해당 경우를 만족하지 않으면 1에서 최단거리로 가는 경우가 아님
q.put(e)
node[e] = node[curnode]+1
def solution(n, vertex):
# Graph
custom = [[] for _ in range(n+1)]
for v in vertex:
s, e = v[0], v[1]
custom[s].append(e)
custom[e].append(s)
# 노드별 최단 거리 저장
node = [55555] * (n+1)
node[0] = 0 # reset
node[1] = 1 # 시작점
BFS(custom, node, 1)
node.sort()
k = node.index(node[-1])
answer = n+1-k
return answer
n = 6
vertex = [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]
answer = solution(n, vertex)
print(answer)
'''
# 최초 코드(TC 7~9에서 시간초과)
from queue import Queue
q = Queue()
def BFS(custom, node, n):
q.put(n)
while not q.empty():
curnode = q.get()
for i in range(1, len(custom)):
if curnode == i:
continue
if custom[curnode][i] == 1:
if node[curnode]+1 < node[i]: # 해당 경우를 만족하지 않으면 1에서 최단거리로 가는 경우가 아님
q.put(i)
node[i] = node[curnode]+1
def solution(n, vertex):
# Graph
custom = [
[0 for _ in range(n+1)]
for _ in range(n+1)
]
for v in vertex:
s, e = v[0], v[1]
custom[s][e] = 1
custom[e][s] = 1
# 노드별 최단 거리 저장
node = [55555] * (n+1)
node[0] = 0 # reset
node[1] = 1 # 시작점
BFS(custom, node, 1)
maxnum = max(node)
answer = node.count(maxnum)
return answer
n = 6
vertex = [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]
answer = solution(n, vertex)
print(answer)
'''
다익스트라 알고리즘(Dijkstra Algorithm)
- 다익스트라 알고리즘은 다이나믹 프로그래밍(Dynamic Programming)을 활용한 최단 경로(Shortest Path) 탐색 알고리즘입니다. ‘특정 정점에서 다른 모든 정점’로 가는 최단 경로를 계산합니다. 단, 다익스트라 알고리즘은 음의 간선을 적용할 수 없어 음의 간선이 없는 현실 세계에 사용하기 매우 적합한 알고리즘입니다. 해당 알고리즘을 대입한 문제가 바로 위에 있는 ‘가장 먼 노드’ 문제이기도 합니다. -> 해당 문제는 가중치가 모두 1인 경우라 BFS로 풀어도 무관하지만, 가중치가 있다면 무조건 다익스트라 알고리즘을 사용해야합니다. 참고 블로그
- 최단 거리는 여러 개의 최단 거리로 이루어져 있기 때문에 작은 문제가 큰 문제의 부분 집합에 속해있다고 볼 수 있으며, 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 이용합니다. 따라서 다익스트라 알고리즘은 다이나믹 프로그래밍 문제이기도 합니다.
- 가중치가 없는 그래프 탐색은 BFS, 가중치가 있다면 다익스트라 알고리즘을 씁시다.
for e in range(n):
if not visited[e]:
if d[cur]+graph[cur][e] < d[e]:
d[e] = d[cur] + graph[cur][e]
'''
백준 1753: 최단경로(Gold VI)
https://www.acmicpc.net/problem/1753
그래프 이론, 다익스트라
기존의 BFS처럼 queue를 사용하면, 노드 개수가 많을 때 비효율적이다.
고로 우선순위큐로 최대한 경우의 수를 줄이자.
+ 우선순위큐로 PriorityQueue와 heapq를 사용한다. PriorityQueue도 내부적으로 heapq를 사용하기 때문에 heapq를 사용하자.
https://velog.io/@t1won/Python-PriorityQueue-vs-heapq
+ 어.. 입력의 개수가 많으면 그냥 sys.stdin.readline을 씁시다. 이거 하니까 2시간동안 시간초과 뜬게 바로 해결되네요?
'''
import heapq, sys
input = sys.stdin.readline
INF = 22222222
# u: start, v: end, w: weight
def dijkstra(graph, dist, k):
q = []
# (가중치, 시작노드)
heapq.heappush(q, (0, k))
while q:
w, u = heapq.heappop(q)
if dist[u] < w: # 이미 처리됨/고려할 필요가 없음 -> 없어도 되나, 경우의 수를 줄여줌
continue
for vl in graph[u]:
v, vw = vl[0], vl[1]
cost = w + vw
if dist[v] > cost:
dist[v] = cost
heapq.heappush(q, (cost, v))
V, E = map(int, input().split())
i = int(input())
# 방향 그래프(가중치))
graph = [[] for _ in range(V)]
for _ in range(E):
u, v, w = map(int, input().split())
graph[u-1].append([v-1, w])
dist = [INF for _ in range(V)]
dist[i-1] = 0
dijkstra(graph, dist, i-1)
for w in dist:
print(w if w != INF else 'INF')
'''
# 영겁의 시간 직전 작성했던 코드입니다. 이거도 sys.stdin.readline 쓰니까 풀리긴 하네요.
from queue import PriorityQueue
import sys
input = sys.stdin.readline
INF = 222222
def dijkstra(graph, node, k):
q = PriorityQueue()
# (가중치, 시작노드)
q.put((0, k))
while not q.empty():
w, u = q.get()
for v in graph[u]:
if v[1] > 0 and node[v[0]] > v[1] + w:
node[v[0]] = v[1] + w
q.put((node[v[0]], v[0]))
V, E = map(int, input().split())
i = int(input())
# 방향 그래프(가중치))
graph = [[] for _ in range(V)]
for _ in range(E):
u, v, w = map(int, input().split())
if v > V:
continue
graph[u-1].append([v-1, w])
node = [INF for _ in range(V)]
node[i-1] = 0
dijkstra(graph, node, i-1)
for w in node:
print(w) if w != INF else print('INF')
'''
플로이드 와샬 알고리즘(Floyd Warshall Algorithm)
- 플로이드 와샬 알고리즘은 ‘모든 정점에서 모든 정점’으로의 최단 경로를 구하는 알고리즘입니다. 다익스트라 알고리즘은 가장 적은 비용을 하나씩 선택했지만 플로이드 와샬 알고리즘은 ‘거쳐가는 정점’을 기준으로 수행됩니다. 또한, 플로이드 와샬 알고리즘 역시도 다이나믹 프로그래밍을 활용합니다. 참고 블로그
- 사담)그래프의 경우 간선의 방향성이 있는지 없는지, 가중치가 있는지 없는지에 따라 구현부의 코드가 조금씩 달라지지만 큰 틀을 벗어나지는 않는듯 하네요.
- 알고리즘은 간단하게 A to B의 최소 비용 vs. A to C + C to B의 최소 비용의 비교입니다. 3중 for문으로 구현하는 방식이 있습니다.
for m in range(n): # 거쳐가는 노드
for s in range(n): # 출발 노드
for e in range(n): # 도착 노드
if d[s][m] + d[m][e] < d[s][e]: # 경유 거리가 직행 거리(초기)/최단 거리(갱신 후)보다 짧은 경우
d[s][e] = d[s][m] + d[m][e] # 최단 거리 갱신
우선순위 큐(Priority Queue)
- 우선순위 큐는 FIFO로 데이터를 관리하는 큐와는 달리, 데이터를 제거될 때 정렬된 순서대로 삭제되는 큐입니다. 병원이나 운영체제의 대기열 등에 사용될 수 있으며, 다익스트라 알고리즘에도 사용될 수 있습니다.
from queue import PriorityQueue
pq = PriorityQueue() # maxsize를 설정하고 싶다면 PriorityQueue(maxsize=10)
# PriorityQueue의 put과 get 함수는 O(log N)의 시간복잡도를 가진다.
pq.put(2) # 2
pq.put(1) # 1-2
pq.put(3) # 1-2-3
pq.get() # 2-3
pq.get() # 3
pq.get() #
# (우선순위, 값))
pq.put((3, 'A')) # (3, 'A')
pq.put((1, 'B')) # (1, 'B')-(3, 'A')
pq.put((2, 'C')) # (1, 'B')-(2, 'C')-(3, 'A')
print(pq.get()[1]) # 'B'
pq.get() # (3, 'A')
pq.get() #
힙(Heap)
- 힙은 binary tree 기반의 자료구조로, 데이터들이 정렬된 상태로 추가되고 삭제합니다. Min heap의 경우 root의 값이 가장 작은 값이고, Max heap의 경우 root의 값이 가장 큰 값입니다.
- 파이썬에서는 binary heap 기반의 min heap을 지원하는 heapq 모듈을 사용할 수 있습니다. 내부 데이터[k]들은 항상 자식 원소들([2k+1], [2k+2])보다 크거나 같도록 관리됩니다.
- 단, 보통의 모듈들과는 달리 별도의 자료구조가 아니라 list를 min heap처럼 다룰 수 있게 도와주는 모듈이기 때문에 heapq의 원소를 호출하면서 리스트를 원자로 넘겨야 합니다.
import heapq
heap = []
# pushheap: O(log N)
heqpq.pushheap(heap, 4) # [4]
heqpq.pushheap(heap, 1) # [1, 4]
heqpq.pushheap(heap, 7) # [1, 7, 4]
heqpq.pushheap(heap, 3) # [1, 3, 7, 4]
# heappop: O(log N)
heapq.heappop(heap) # [3, 4, 7]
heapq.heappop(heap) # [4, 7]
# 최소값 접근 O(1) // 단, [0]에 최소값이 있다고 해서 [1]과 [2]에 다음 최소값이 있다고 보장할 수 없다.
heap[0] # 4
# heapify: 기존 리스트를 힙으로 변환(O(N))
lst = [4, 1, 7, 3, 8, 5]
heapq.heapify(lst) # [1, 3, 5, 4, 8, 7]
'''
1. 만약 파이썬에서 max heap을 사용하고 있다면, tuple을 이용해 (우선순위, 값)->(-값, 값)을 넣어 힙[데이터][1]로 사용하면 되겠습니다.
2. heap을 사용해 K번째 최소값/최대값을 구할 수 있습니다. list를 heap으로 바꾸고, heappop() 함수를 K번 호출하면 됩니다.
'''
Two Pointer
- 투포인터는 리스트에 순차적으로 접근해야 할 때 두 개의 index를 이용해 처리하는 알고리즘으로, 정렬되어 있는 두 리스트의 합집합이나 병합정렬에도 사용됩니다.
'''
백준 3273: 두 수의 합(Silver III)
https://www.acmicpc.net/problem/3273
정렬, 투 포인터
'''
n = int(input())
a = list(map(int, input().split()))
x = int(input())
answer = 0
i, j = 0, n-1
a.sort()
# 정렬을 해서 start -> <- end의 부분합 쌍을 구하는 알고리즘.
while True:
if i >= j:
break
temp = a[i] + a[j]
if temp == x:
answer += 1
i += 1
j -= 1
elif temp < x:
j += 1
else:
i -= 1
print(answer)
이분 탐색(Binary Search)
- 이분 탐색 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법입니다. 찾으려는 리스트의 데이터들이 정렬되어 있어야만 사용할 수 있으며, O(log N)의 시간복잡도를 가집니다. 따라서 n의 크기가 큰 리스트에서 값을 찾을 경우 사용하면 좋습니다.
'''
백준 1764: 듣보잡(Silver VI)
https://www.acmicpc.net/problem/1764
자료구조, 문자열, 정렬, 해시를 사용한 집합과 맵
- 이분탐색
- 완전탐색 * 순차탐색(in 연산): N * N -> N^2
- 정렬 + 이분탐색: N log N + N * log N -> N log N
+ 교집합 + 정렬: N + N log N = N log N
'교집합 + 정렬'은 '정렬 + 이분탐색'에 비해 작은 N의 크기로 정렬하기 때문에 비교적 작은 시간복잡도를 가진다고 기대할 수 있다.
'''
def binarysearch(lst, s, e, key):
if s > e:
return -1
m = (s+e)//2
if lst[m] == key:
return m
elif key < lst[m]:
return binarysearch(lst, s, m-1, key)
else:
return binarysearch(lst, m+1, e, key)
d, b = map(int, input().split())
D = []
B = []
for _ in range(d):
D.append(input())
for _ in range(b):
B.append(input())
D.sort()
B.sort()
answer = []
for d in D:
if binarysearch(B, 0, len(B)-1, d) != -1:
answer.append(d)
print(len(answer))
for a in answer:
print(a)
'''
# 풀이2: 파이썬의 교집합
d, b = map(int, input().split())
D = set()
B = set()
for _ in range(d):
D.add(input())
for _ in range(b):
B.add(input())
'''
# 파이썬 합집합(|)의 시간 복잡도는 O(M+N), 교집합(&)의 시간 복잡도는 O(M) (M<N)이다.
'''
answer = sorted(list(D & B)) # 교집합 연산()
print(len(answer))
for a in answer:
print(a)
'''
프로그래머스 > 코딩테스트 연습 > 탐욕법(Greedy) > 단속카메라
- 백준의 1931(회의실 배정, S1) 문제와 접근법이 동일한 문제입니다. 비슷한 유형의 문제가 코딩테스트에 출제될 수 있을 것이라 판단되어 정리합니다. 탐욕법은 단순하면서도 구현하기 까다로운 느낌이네요..
def solution(routes):
routes.sort(key = lambda r: (r[1], r[0]))
answer = 1 # 첫 차량의 구간에 대한 기본 카메라 1대
out = routes[0][1]
for i in range(1, len(routes)):
if out < routes[i][0]: # 이전 차량의 구간 종료 전 현재 차량의 구간이 시작되지 않는다면 갱신
out = routes[i][1]
answer += 1
return answer
프로그래머스 > 코딩테스트 연습 > 탐욕법(Greedy) > 섬 연결하기
- 그래프 탐색과 탐욕법을 섞어놓은 이런 유형의 문제는 지금껏 풀어본 적이 없었습니다. 어떻게 구현해야 할지 몰랐기 때문입니다.
- 하지만 이 문제와 같이 가장 적은 비용으로 노드들을 연결시키는 문제는 크러스컬 알고리즘을 통해 풀 수 있습니다.
- 해당 문제의 최대 변수 크기가 100과 4950이기 때문에 각 노드들의 최상위 노드를 갱신하는 알고리즘을 Brute Force로 구현했습니다. 변수의 크기가 더 커질 경우 최적화된 알고리즘으로 바꿔야 할 것입니다. 합집합 찾기라는 의미를 가진 Union-Find 알고리즘이 있는데 서로소 집합(Disjoint-Set) 알고리즘이라고도 합니다. 여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘입니다. 만약 추후에 비슷한 유형의 문제를 풀다 효율성 문제에 막힐 경우, 이 링크로 가서 다시 공부하겠습니다.
'''
https://programmers.co.kr/learn/courses/30/lessons/42861
- 크러스컬 알고리즘(Kruskal Algorithm): 그리디 알고리즘을 이용하여 가중치가 존재하는 그래프를 최소의 비용으로 연결하는 최적의 해답을 구하는 알고리즘.
1. MST(최소 비용 신장 트리)가 최소 비용의 간선으로 구성되어 있고, 사이클을 포함하지 않은 조건에서 각 단계에서 "사이클을 이루지 않는" 최소 비용 간선을 선택한다.
2. "최상위 노드를 저장하는 리스트" -> 만약 두 노드를 연결할 때 최상위 노드가 같다면, 연결했을 때 사이클이 발생함.
3. 간선 정보를 가중치(이 문제에서는 costs[2])를 기준으로 오름차순 정렬시키고, 사이클이 발생하지 않게 1/2 조건에 맞추어 노드들을 연결한다.
'''
def solution(n, costs):
answer = 0
costs.sort(key = lambda c:(c[2], c[0], c[1]))
check = [i for i in range(n)]
for i in range(len(costs)):
if sum(check) == 0:
break
start, end = costs[i][0], costs[i][1]
if check[start] == check[end]:
continue
if check[start] > check[end]:
savedcheck = check[start]
for j in range(n):
if check[j] == savedcheck:
check[j] = check[end]
else:
savedcheck = check[end]
for j in range(n):
if check[j] == savedcheck:
check[j] = check[start]
answer += costs[i][2]
return answer
n = 5
costs = [[0, 1, 5], [1, 2, 3], [2, 3, 3], [3, 1, 2], [3, 0, 4], [2, 4, 6], [4, 0, 7]]
print(solution(n, costs))
프로그래머스 > 코딩테스트 연습 > 탐욕법(Greedy) > 구명보트
# https://programmers.co.kr/learn/courses/30/lessons/42885
# 보트에 탈 수 있는건 최대 2명(two pointer)
# 사람들을 구출할 수 없는 경우는 없다
def solution(people, limit):
answer = 0
people.sort()
i, j = 0, len(people)-1
while i <= j:
if len(people) == 1:
answer += 1
break # j -= 1
weight = people[i] + people[j]
if weight > limit:
answer += 1
else:
answer += 1
i += 1
j -= 1
return answer
print(solution([70,80,50], 100))
프로그래머스 > 코딩테스트 연습 > 탐욕법(Greedy) > 체육복 // in list[:]
- for문에 in 연산자를 쓰게 될 경우, for문에 들어가는 리스트가 기본적으로 복사본이 아니라 원본이기 때문에, remove연산으로 삭제시 데이터 원소를 주의해야 한다.
- 이를 해결하기 위해, 원하는 식으로 for문을 돌리기 위해 in 연산자 뒤에 “리스트의 복사본”을 주면 해결된다.
def solution(n, lost, reserve):
answer = n - len(lost)
for l in lost[:]:
if l in reserve[:]:
lost.remove(l)
reserve.remove(l)
answer += 1
# 입력값 정렬
lost.sort()
reserve.sort()
for r in reserve:
'''
for문에 in 연산자를 쓰게 될 경우, for문에 들어가는 리스트가 기본적으로 복사본이 아니라 원본이기 때문에, remove연산으로 삭제시 데이터 원소를 주의해야 한다.
이를 해결하기 위해, 원하는 식으로 for문을 돌리기 위해 in 연산자 뒤에 "리스트의 복사본"을 주면 해결된다.
'''
if r-1 in lost[:]:
lost.remove(r-1)
answer += 1
elif r+1 in lost[:]:
lost.remove(r+1)
answer += 1
return answer
print(solution(5, [1, 2, 4], [4, 2, 5]))
# 해당 현상 분석
lst = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
for n in lst:
if 4 <= n <= 7:
lst.remove(n)
print(n, lst)
# 원래 유도하려는 값: [1, 2, 3, 8, 9, 10]
'''
나오는 값
1 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
2 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
3 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
4 [1, 2, 3, 5, 6, 7, 8, 9, 10] # 4가 지워지고 이후 연산이 5를 건너뛰고 6으로 감
6 [1, 2, 3, 5, 7, 8, 9, 10] # 6이 지워지고 이후 연산이 7를 건너뛰고 8으로 감
8 [1, 2, 3, 5, 7, 8, 9, 10]
9 [1, 2, 3, 5, 7, 8, 9, 10]
10 [1, 2, 3, 5, 7, 8, 9, 10]
# -> i는 그대로 0 1 2 3 4 5 6 7 8 9 순으로 올라가는데, 값이 앞으로 당겨지면서 일어나는 현상같음.
'''
SW Expert Academy > 1249. [S/W 문제해결 응용] 4일차 - 보급로(D4)
- 시도는 좋았으나, 공부의 필요성을 다시 한 번 느끼게 해준 문제입니다.
'''
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD
help: 탐색의 방향이 "상하좌우"라, 기존에 내가 알고 있던 방식대로 풀 수가 없었음
기존의 탐색에 가지치기 + DP를 섞으면 해결
원리: 아직 들리지 않았거나, "현재 위치의 dp 값과 다음 위치의 합"이 갈 곳의 dp 값보다 작을 때 갱신
'''
from queue import Queue
# U, D, L, R
dx = [-1, +1, +0, +0]
dy = [+0, +0, -1, +1]
def in_range(x, y):
return 0 <= x < N and 0 <= y < N
def BFS():
global dist, check, dp
q = Queue()
check[0][0] = 1
dp[0][0] = 0
q.put((0, 0))
while not q.empty():
front = q.get()
cx, cy = front[0], front[1]
for i in range(4):
nx = cx + dx[i]
ny = cy + dy[i]
# 방문하지 않은 위치거나, "현재 누적합+다음 위치"가 다음 위치의 누적합보다 작은 경우
if in_range(nx, ny) and (check[nx][ny] == 0 or dp[nx][ny] > dp[cx][cy] + dist[nx][ny]):
check[nx][ny] = 1
dp[nx][ny] = dp[cx][cy] + dist[nx][ny]
q.put((nx, ny))
dist = []
check = []
dp = []
T = int(input())
for c in range(1, T+1):
N = int(input())
# 입력받은 지도
dist = []
# 방문 여부 확인
check = [
[0 for _ in range(N)]
for _ in range(N)
]
# 최단 거리 확인
dp = [
[0 for _ in range(N)]
for _ in range(N)
]
for _ in range(N):
temp = list(map(int, input()))
dist.append(temp)
BFS()
print("#%d %d" % (c, dp[N-1][N-1]))
이진 탐색 > 떡볶이 떡 만들기
- 최적의 절단기 길이를 찾기 위해 이진 탐색적 기법을 이용한 문제입니다. 파라메트릭 서치(Parametric Search) 유형이기도 한데, 이는 최적화 문제를 결정 문제(Yes or No)로 바꾸어 해결하는 기법입니다. 즉, 원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제에 사용합니다.
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
rc = list(map(int, input().split()))
start = 0
end = max(rc)
answer = 0
while start <= end:
total = 0 # 잘린 길이
mid = (start+end) // 2 # 절단기의 길이
for r in rc:
# 잘린 떡의 길이 합
if r > mid:
total += (r-mid)
# 양이 적으면 더 많이 자름(왼쪽)
if total < M:
end = mid - 1
# 양이 같거나 많으면 더 적게 자름(오른쪽)
else:
answer = mid # 최대한 덜 잘랐을 때가 정답이며, 최적해가 나올 때 마다 갱신됨
start = mid + 1
print(answer)
최단 경로 > 미래 도시
import heapq
INF = 9999999999
N, M = map(int, input().split())
# 다익스트라
dist = [INF for _ in range(N)]
graph = [[] for _ in range(N)]
for _ in range(M):
s, e = map(int, input().split())
graph[s-1].append((1, e-1))
graph[e-1].append((1, s-1))
X, K = map(int, input().split())
X -= 1
K -= 1
def dijkstra(start, end):
q = []
heapq.heappush(q, (0, start))
dist[start] = 0
while q:
sw, se = heapq.heappop(q)
# start 기존 최단거리가 입력된 거리보다 짧은 경우(이미 처리가 되어 고려할 필요가 없는 경우)
if dist[se] < sw:
continue
for nextnode in graph[se]:
nw, ne = nextnode
cost = dist[se] + nw # 현재까지의 최단 거리 + 다음 노드까지의 거리(여기서는 1로 고정)(A)
if cost < dist[ne]: # A가 다음까지의 최단 거리보다 짧은 경우 갱신
dist[ne] = cost
heapq.heappush(q, (cost, ne))
return dist[end]
answer = dijkstra(0, K) + dijkstra(K, X)
# 플로이드 워셜
'''
graph = [
[INF for _ in range(N)]
for _ in range(N)
]
for i in range(N):
graph[i][i] = 0
for _ in range(M):
s, e = map(int, input().split())
graph[s-1][e-1] = 1
graph[e-1][s-1] = 1
X, K = map(int, input().split())
X -= 1
K -= 1
for m in range(N):
for s in range(N):
for e in range(N):
if graph[s][e] > graph[s][m] + graph[m][e]:
graph[s][e] = graph[s][m] + graph[m][e]
answer = graph[0][K] + graph[K][X]
'''
print(answer if answer < INF else -1)
서로소 집합(Disjoint Sets)
- 서로소 집합은 공통 원소가 없는 두 집합을 의미하며, 서로소 집합 자료구조는 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조입니다.
- union과 find 연산을 가지며, tree 자료구조를 이용하여 집합을 표현합니다. union(합집합) 연산을 통해 서로 연결된 두 노드 A, B를 확인한 뒤, A를 B의 부모 노드로 설정합니다.(B가 A를 가리키도록) 모든 union 연산을 처리할 때까지 앞의 과정을 반복합니다.
- 간단히 하자면, min heap 느낌의 자료구조라고 가정했을 때 노드의 부모를 번호가 작은 쪽으로 합치는 것입니다. (nodenum, parentnode)라고 했을 때, (0, 0)과 (1, 1), (2, 1)을 union하면 (0, 0), (1, 0), (2, 1)가 됩니다. 이때, (2, 1)의 최종 부모 노드를 계산하면 0이 나옵니다.
# 팀 결성: 서로소 집합 알고리즘
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
N, M = map(int, input().split())
team = [i for i in range(N+1)]
answer = []
for _ in range(M):
cmd, a, b = map(int, input().split())
if cmd == 0:
union_parent(team, a, b)
else:
if find_parent(team, a) == find_parent(team, b):
answer.append("YES")
else:
answer.append("NO")
for a in answer:
print(a)
'''
input
7 8
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1
output
NO
NO
YES
'''
그래프 이론 > 크루스칼 알고리즘
- https://www.acmicpc.net/problem/1647(도시 분할 계획, 백준 G4)
# 크루스칼
# 최소 비용으로 2구간을 만들기: 최소신장트리를 찾은 후, 가장 큰 가중치를 가지는 edge를 없애면 된다.
import sys
input = sys.stdin.readline # 알고리즘이 "맞는데 왜 틀림?" -> input 대신 sys.stdin.readline을 쓰자.
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
N, M = map(int, input().split())
city = [i for i in range(N+1)]
# >크루스칼
edges = []
answer = 0
for _ in range(M):
start, end, weight = map(int, input().split())
edges.append((weight, start, end))
edges.sort()
# >크루스칼
max_edge = -1 # 최소 비용으로 2구간을 만들기: 최소신장트리를 찾은 후, 가장 큰 가중치를 가지는 edge를 없애면 된다.
for w, s, e in edges:
w, s, e = edge
# >서로소
if find_parent(city, s) != find_parent(city, e):
union_parent(city, s, e)
answer += w
max_edge = w
# >서로소
print(answer - max_edge)
'''
input
7 12
1 2 3
1 3 2
3 2 1
2 5 2
3 4 4
7 3 6
5 1 5
1 6 2
6 4 1
6 5 3
4 5 3
6 7 4
output
8
'''
그래프 이론 > 위상 정렬
- 추가 공부 필요
# 위상 정렬(Topology Sort): 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용.
# 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것
# 예시) 선수과목을 고려한 학습 순서 설정-> 진입차수가 낮은 노드부터 처리
from collections import deque
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
N = int(input())
indegree = [0] * (N+1) # 선수과목-위상정렬
graph = [[] for _ in range(N+1)] # 해당 과목의 선수과목
time = [0] * (N+1) # 과목별 이수 시간
for i in range(1, N+1):
in_ = list(map(int, input().split()))
time[i] = in_[0]
for d in in_[1:-1]:
indegree[i] += 1
graph[d].append(i)
def topology_sort():
answer = time[:]
q = deque()
# 초기값: 진입차수가 0인 노드
for i in range(1, N+1):
if indegree[i] == 0:
q.append(i)
while q:
cur = q.popleft()
for next_ in graph[cur]:
answer[next_] = max(answer[next_], answer[cur] + time[next_])
indegree[next_] -= 1
if indegree[next_] == 0:
q.append(next_)
for i in range(1, N+1):
print(answer[i])
topology_sort()
'''
input
5
10 -1
10 1 -1
4 1 -1
4 3 1 -1
3 3 -1
output
10
20
14
18
17
'''
프로그래머스 > 다단계 칫솔 판매(Level 3)
- 서로소 집합을 이용한 문제입니다. 거기에 더해 hash 개념을 더해야 모든 테스트케이스를 만족시킬 수 있었습니다.
'''
조건에 따라, 다단계의 상위 담당자는 담당하는 직원보다 번호가 빠르다.
일반 리스트로 풀었을 때 11~13번 테스트케이스에서 시간초과가 발생 -> Hash를 이용해 해결
'''
def find(parent, x, money, result):
if parent[x][1] != x:
nextmoney = money//10
result[parent[x][0]] += (money - nextmoney)
if nextmoney == 0:
return
find(parent, parent[x][1], nextmoney, result)
else:
result[parent[x][0]] += money
def solution(enroll, referral, seller, amount):
result = [0] * (len(enroll)+1)
parent = {}
'''
key = Name
value = (Name's index, Parent's name)
'''
parent['-'] = (0, '-')
for i in range(len(enroll)):
parent[enroll[i]] = (i+1, referral[i])
for i in range(len(seller)):
x = seller[i]
money = 100*amount[i]
find(parent, x, money, result)
return result[1:]
print(solution(["john", "mary", "edward", "sam", "emily", "jaimie", "tod", "young"], ["-", "-", "mary", "edward", "mary", "mary", "jaimie", "edward"], ["young", "john", "tod", "emily", "mary"], [12, 4, 2, 5, 10]))