지난주 목요일에 W01 마무리로 시험을 봤는데, 무려 세개중에 0개나 맞았다..!
호기롭게 두개는 맞추자고 각오하고 들어갔는데.. 첫 문제에서 무언가에 홀린듯이 moo 순열을 만들기 위해 최선을 다했고, 무슨 무슨 초과를 보며 마음은 점점 다급해져갔다.
메모리 초과를 해결해보겠다고 재귀함수를 이리뜯어보고 저리 뜯어보고 했지만 해결될리가 없지.. 첫문제에만 1시간 넘게 쓰고 다른 문제는 제대로 보지도 못했다.
moo에게 대패하고 나서야 왜 문제 풀기전에 입력값을 확인하고 이에 따른 시간과 공간 복잡도를 미리 예상하고 문제를 풀어야 하는지 체감할 수 있었다.
그래서 이번주에는 전략을 바꿔서 문제 풀기전에 미리 입력값과 시간 및 공간제한을 확인하고, 대~충 O(?) 안에 풀면 되겠다고 에디터 맨 위에 적고 시작한다. 물론 시간, 공간에 대해 통달하지는 못해서 이렇게 미리 체크를 해주어도 문제가 발생하는 경우가 허다하지만, 무턱대고 코드부터 치는 것 보다는 훨씬 낫다고 느끼고 있다.
이와 더불어서 실제 코드 치기전에 문제 풀이 방법을 한글말로 쭉 적고, 이를 보면서 코드를 짜는 버릇을 들이고 있다.
현재는 그냥 에디터 맨 위에다가 줄글로 쭉 적고 있지만,
내가 생각하는 이상적인 모습은 문제 풀기 전에 주석으로 특정 위치에 필요한 로직을 적어놓고, 그 주석을 코드로 바로 바꾸는... 일종의 구조화를 미리 거치는 것인데, 이는 연습이 더 필요한듯 하다.
BFS
보통 그래프 탐색 문제이고, "최소 OR 최단" 키워드가 들어 있으면 죄다 BFS를 사용하는 문제(DFS를 사용하면 시간초과 발생) 이길래, 궁금해하던 차에 팀원분이 이유를 설명해주셨다.
트리를 탐색한다고 가정하면,
DFS는 Depth가 우선이 된다는 이름 그대로 트리의 가지 끝까지 들어가보았다가, 거기서 빠져나와서 다시 또 다른 가지를 끝까지 탐색한다. 그에 반해서 BFS는 루트부터 시작해서 한 층 한 층 내려가면서 탐색을 진행하기에, 제일 짧은 단말(leaf)노드가 있는 층까지만 내려가면 최단을 판단할 수 있다.. 라고 해주셨는데, 그림으로 그려서 보니까 빠르게 이해할 수 있었다.
미로만들기 같은 경우가 이런 전형적인 문제가 아닐까 싶다.
이 문제는 두가지 방법으로 풀 수가 있었다.
- 첫번째, heap을 활용하는 방법
- 두번째, visited 배열에 경로를 업데이트하고 , 큐의 삽입 방향을 달리하는 방법
힙을 사용하던, 큐의 삽입 방향을 달리하던, 둘 모두의 목표는 같다.
검은방을 최대한 거치지 않고 흰방에 최대한 빨리 도달하는 것.
그래서 힙을 사용하게 되면, bfs를 진행하며
- 검은 방을 만나게 되면, (비용 + 1, 행, 열) 의 튜플을 최소힙에 넣어준다.
- 반대로 흰 방을 만나게 되면 비용을 그대로 유지한 채 (비용, 행, 열) 을 최소힙에 넣어준다.
이러면 최소힙의 특성상, 비용이 높은 경로는 누르고, 비용이 낮은 경로를 빨리 꺼내기 때문에, 검은 방을 "최대한 덜 거친 경로" 를 우선적으로 탐색하게 된다.
이렇게 탐색해 나가다가 원하는 위치에 도달하게 되면, 힙에서 방금 꺼낸(튜플의 맨 앞에 있는) 비용을 리턴해주기만 하면 된다.
큐의 삽입 위치를 다르게 하고, visited배열에 경로를 기록하는 방식도 유사하다.
- 큐의 왼쪽에서 경로를 꺼내서 탐색한다
- 검은 방을 만나게 되면 해당 경로는 큐의 우측에 넣어준다
- 반대로 흰 방을 만나게 되면 해당 경로는 큐의 좌측에 넣어준다
- 소요 시간은 현재 visited배열의 값 + 1 을 다음 탐색하는 visited배열 위치에 기록해준다.
밑은 힙을 사용한 코드이다
import sys
from heapq import heappush, heappop
input = sys.stdin.readline
n = int(input())
matrix = [list(map(int, list(input().strip()))) for _ in range(n)]
visited = [[0] * n for _ in range(n)]
dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]
heap = []
visited[0][0] = True
heappush(heap, (0,0,0))
while True:
cost, row, col = heappop(heap)
if row == n -1 and col == n -1:
print(cost)
break
for i in range(4):
newR = row + dr[i]
newC = col + dc[i]
if 0 <= newR < n and 0 <= newC < n and not visited[newR][newC]:
if matrix[newR][newC] == 0:
heappush(heap, (cost + 1, newR, newC))
else:
heappush(heap, (cost, newR, newC))
visited[newR][newC] = True
밑은 큐의 삽입순서와, 시간을 visited배열에 반영한 코드이다.
# bfs 풀이
import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
graph = []
for _ in range(n):
graph.append(list(map(int, list(input().strip()))))
dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]
visited = [[-1]* n for _ in range(n)]
visited[0][0] = 0
q = deque([(0,0)])
while q:
row, col = q.popleft() # 왼쪽에서 pop
# 최단 경로(흰방을 최대한 많이 만난 애)가
# 끝에 다다르면 끝냄
if row == n-1 and col == n-1:
print(visited[row][col])
break
for i in range(4):
newR = row + dr[i]
newC = col + dc[i]
if not (0 <= newR < n and 0 <= newC < n):
continue
if visited[newR][newC] == -1: # 방문한적 없음
if graph[newR][newC] == 0: # 검은방
visited[newR][newC] = visited[row][col] + 1
q.append((newR, newC)) # 검은방을 만난경우 오른쪽에 넣음 - 후순위
else: # 흰방
visited[newR][newC] = visited[row][col]
q.appendleft((newR, newC)) # 흰방을 만난경우 왼쪽에 넣음 - 선순위
DFS
확실히 첫주에 재귀를 공부한 이유가 있다.
재귀함수의 구조를 잘 이해하고 있어야만 DFS를 잘 할 수 있겠다고 느꼈다.
예를 들어, 이번주 문제였던 이분 그래프 의 경우 dfs를 타고 들어가면서, 현재 나의 그룹과, 나에게 연결된 노드들의 그룹을 달리 해주고, 만약 나와 연결된 노드들의 그룹이 같다면 이분이 아님을 나타내는게 관건인 문제였다.
그래서 아래처럼 visited 배열에 그룹을 기록해가며 dfs를 진행하면 되는데..
def dfs(start, group):
visited[start] = group # 정점의 그룹 설정(-1, 1)
for i in graph[start]:
if not visited[i]:
a = dfs(i, -group)
if not a: # dfs의 결과가 false
return False
elif visited[i] == visited[start]:
return False
return True처음에는 이 코드에서 살짝만 바꾼, 그러나 오답인 코드를 밑과 같이 짰다.
def dfs(start, group):
visited[start] = group # 정점의 그룹 설정(-1, 1)
for i in graph[start]:
if not visited[i]:
return dfs(i, -group)
elif visited[i] == visited[start]:
return False
return True이렇게 짜놓고 계속 틀리길래, 아무리 봐도 답이랑 똑같은데 뭐가 문제지?? 이러고 있었다.
저기서 바로 재귀호출한 함수의 결과값을 리턴해버리면 당연히 바로 그 밑 라인인 elif~ 을 거치지 않아서 나와 연결된 노드들의 그룹이 같은지를 검사하지 않게 된다.
재귀함수를 짤때, 이런 사소해보이는 차이가 결과에 큰 영향을 불러온다는것을 dfs문제들에게 맞아가면서 이렇게 배우고 있다.
위상정렬
작업 문제, 작업을 모두 완료하기 위해서는, 특정 작업의 선행 작업 중 "가장 큰 것" 이 완료되어야만 다음 작업이 진행되는 식으로 작업의 시간을 이전 작업들 중 제일 시간이 오래 걸리는 것 + 현재 작업시간 의 식으로 업데이트 해줄 필요가 있었다.
이를 위해 time 배열을 활용해 줬는데, 다음주에 할 dp의 일종이 아닌가 하는 생각이 든다.
import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
cost = [0] * (n+1) # 그냥 단순한 작업의 시간
time = [0] * (n+1) # 누적된 - 최대시간
graph = [[] for _ in range(n+1)]
indegree = [0] * (n+1)
q = deque()
for i in range(1, n+1):
lst = list(map(int, input().split()))
cost[i] = lst[0]
if lst[2:]:
for j in lst[2:]:
graph[j].append(i)
indegree[i] += 1
if indegree[i] == 0:
q.append(i)
time[i] = cost[i]
while q:
now = q.pop()
for i in graph[now]:
if time[i] < time[now] + cost[i]:
time[i] = time[now] + cost[i]
indegree[i] -= 1
if indegree[i] == 0:
q.appendleft(i)
print(max(time))
그 밖의 것들..
백준 알파벳
dfs를 해나가며, 현재까지 경로의 알파벳들과 다른 알파벳들에 대해서만 경로 탐색을 이어나갈 수 있는 문제였다.
여태까지 지나온 알파벳을 set에 저장해주고, 새로운 노드를 탐색할때마다 set 의 in 연산으로 해당 알파벳을 지나온 적이 있는지 확인해주었다.
결과는 시간초과.
아무리 생각해도 시간을 줄일게 없어서 고민하다가, 혹시나해서 알파벳 중복체크를 set이 아닌 인덱스(26 길이의 리스트)로 해주었더니 시간초과를 극복할 수 있었다.
둘다 O(1)아님?? 해서 스택오버플로우에 물어보니 왜 그런지 알게됐다.
둘다 Big - O표기로는 O(1)이지만, set의 경우는 hash collision이 발생할 수 있기때문에, 해당 해시값에 해당하는 버킷들을 탐색하는데 1 opertaion 이상의 연산이 발생할 수 "있다".
근데 그거는 그냥 "가능성"이고, 실제로는 알파벳 26개 이상의 값을 집어넣지는 않을텐데, 실제 시간차이가 있나?? 라는 의문을 가졌지만..
Big O는 scalability, 즉 해당 프로그램에 주어지는 입력값의 사이즈가 커질때, 연산이 어느정도 수준으로 증가하는 지를 알려주는 값이고, 실제 프로그램을 돌렸을때 우리가 느끼는 실행시간은 이와 다르다.
따라서 비록 둘다 O(1)이라도, 무조건 한번의 연산을 보장하는 인덱싱과 달리, 여러번의 연산이 발생할수 있는 set의 in 연산은 실제 실행 시간에 있어 큰 차이가 발생할 수 있다.
