플러터를 사용하면서, 제 아무리 'flutter pub run build_runner build' 코드를 돌려도 '.g.dart' 파일이 생성이 되지 않아 너무 고생했었다.. 검색해도 잘 나오지 않은 실수라서 혹시나 같은 실수로 인해 고생할 사람을 위해 글을 남겨보려고 한다.
일단 먼저 플러터 개발자 사이트에 직렬화에 대한 설명히 자세히 나와있다.
다음 내용을 간략히 요약하자면 다음과 같다.
먼저, pubspec.yaml 폴더에 다음과 같이 추가해주고 'flutter pub get'을 실행해준다.
dependencies:
json_annotation: ^4.6.0
dev_dependencies:
build_runner: ^2.1.7
json_serializable: ^6.1.4
그런 다음 다음과 같이 코드를 구성해주면 된다.
1. 'json_annotation.dart' 패키지를 import 해준다.
2. part '파일 명.g.dart'를 해준다.
3. map 구조에서 새로운객체(코드에서는 Example)를 생성하기 위한 생성자인User.fromJson()생성자, 객체를 map 구조로 변환하기 위한 메서드인toJson()메서드를 담은 class를 다음과 같이 만들어 준다.
4. Terminal에서 'flutter pub run build_runner build' 를 실행하여 준다.
5. 생성된 '.g.dart'를 확인 할 수 있다.
근데 여기서주의해야할 점이 있다.
이 부분을이 충족 되지 않으면 '.g.dart' 파일이 생성되지 않으므로 꼭!! 신경써줘야 하는 부분이다.
1.part 'OOOO.g.dart' 안에 들어가는 파일 명 부분(OOOO에 해당되는 부분)은해당 파일 명과동일해야한다.
2. FromJson() 생성자와 ToJson() 메소드 앞에 붙는 이름은해당 Class 명과 동일해야한다.
(특히 이 부분에서, '_＄' 또한 빠지면 안된다. 위 코드와 같이 _＄ExampleToJson() 과 같이 온전하게 작성해야한다)
3. 마지막으로, 제가 제일 고생했던 부분인데코드가 저장되지 않은 상태로는 생성되지 않습니다.
코드를 꼭 저장하고 명령어를 실행해주세요!
잘못된 방식으로 코드를 빌드할 경우 다음과 같은 결과를 얻을 수 있다.
flutter pub run build_runner build과정에서 아무런 action이 완료되지 않는 모습flutter pub run build_runner build 결과 output이 나오지 않는 경우
그럼 올바르게 코드를 작성한 후, 결과를 확인해보면 다음과 같다.
flutter pub run build_runner build결과, 깔끔하게 output이 나오는 것을 볼 수 있다.
터미널에서 위와 같은 결과를 얻고 나면, 왼쪽 원본파일 밑에 다음과 같은 파일이 생성된 것을 볼 수 있다.
풀이 방법: stack(list)을 활용하여 '(' 에 대해서 ')'가 맞게 있는지 확인하였습니다.
풀이코드:
import sys
t = int(sys.stdin.readline())
for _ in range(t):
stack = []
ps = list(sys.stdin.readline().rstrip())
vps = True
for nps in ps:
if nps =='(':
stack.append(nps)
else:
if stack:
stack.pop()
else:
vps = False
break
if vps and not stack:
print('YES')
else:
print('NO')
풀이 설명:
for nps in ps:
if nps =='(':
stack.append(nps)
else:
if stack:
stack.pop()
else:
vps = False
break
여기가 핵심 코드인데요.
입력 값을 하나씩 확인하면서 '(' 를 만날 경우, stack에 담아줍니다.
그러고 난 후, ')'를 만날 경우, stack에서 '(' 를 하나씩 pop 해주게 되면, '()'가 이루어집니다.
이때, ')' 가 '(' 보다 많아서 입력받은 문자열은 남아있는데, stack이 빈 경우가 생기게 됩니다.
혹은 '')(' 패턴이 들어간 경우에도 stack이 빈 경우가 생기게 됩니다. ex. ')(' '() )( ()'
if stack:
stack.pop()
else:
vps = False
break
위 코드를 통해, stack이 비었는지 여부를 확인해주고 만약에 비었다면 ')' 갯수가 더 많은 것이므로 vps라는 변수에 False를 설정하고 break 해줍니다.
만약 반복문이 종료가 되었을 때, ')' 갯수가 적어서 '(' 이 남아있는 경우가 있으므로 이 부분도 신경써줘야 합니다.
if vps and not stack:
print('YES')
else:
print('NO')
위 코드와 같이, 구성해줬는데요.
vps가 True, 그리고 stack이 빈 경우에만 'YES'를 출력하고 이외에는 다 'NO'를 출력하도록 설정되어있습니다.
')' 갯수가 많거나 ')(' 패턴이 있다면, vps가 False 일 것이고
')' 갯수가 적을 경우, stack에 '(' 이 남아있을 것이므로 'NO'가 출력되게 될 것입니다.
문제: 고속도로 길이와 지름길이 주어졌을 때, 고속도로를 운전해야하는 최소 거리를 구하는 문제 입니다.
풀이 방법: 다이크스트라 알고리즘을 활용하였습니다. 알고리즘을 활용하여, 지름길 정보에 대해 계속해서 갱신해주는 방식을 사용하였습니다.
풀이코드:
import sys
import heapq
MAX = 10001
n,d = map(int,sys.stdin.readline().rstrip().split())
road = [[]*(MAX) for _ in range(MAX)]
heap = []
dist = [i for i in range(MAX)]
for _ in range(n):
start, end, cost = map(int,sys.stdin.readline().rstrip().split())
heapq.heappush(heap,(end,start,cost))
while heap:
newEnd, newStart, newCost = heapq.heappop(heap)
if newCost > (dist[newEnd] - dist[newStart]) or newEnd > d:
continue
distance = dist[newStart] + newCost
if dist[newEnd] > distance:
dist[newEnd] = distance
for i in range(newEnd+1,MAX):
dist[i] = min(dist[i],dist[i-1]+1)
print(dist[d])
풀이 설명:
dist = [i for i in range(MAX)]
먼저 지름길이 없을 경우에는 목적지 x 까지 주행해야 하는 거리는 x이므로, 다음과 같이 저장해줬습니다.
for _ in range(n):
start, end, cost = map(int,sys.stdin.readline().rstrip().split())
heapq.heappush(heap,(end,start,cost))
지름길에 대한 정보를 heapq를 활용해 저장하였습니다. 다만 저장할 때, 출발점으로부터 가까운 지름길 정보부터 갱신해주기 위해 (end,start,cost)형태로 저장하였습니다.
*heapq.heappush를 사용하면 end 값 기준으로 오름차순 정렬하여 데이터가 저장됩니다.
while heap:
newEnd, newStart, newCost = heapq.heappop(heap)
if newCost > (dist[newEnd] - dist[newStart]) or newEnd > d:
continue
distance = dist[newStart] + newCost
if dist[newEnd] > distance:
dist[newEnd] = distance
그런 다음 저장된 값을 순차적으로 접근하면서, 지름길에 대한 정보를 업데이트 해줬습니다.
기존에 다른 지름길을 통해 이미 end값 까지 도착하는 거리가 갱신되었을 수 있으므로, if문을 통해 현재 계산된 거리와 기존에 저장된 거리를 비교하여 최소값을 저장해주었습니다.
for i in range(newEnd+1,MAX):
dist[i] = min(dist[i],dist[i-1]+1)
마지막으로, 지름길 정보가 갱신 될 때 마다 지름길에 대한 정보를 전체 거리정보가 담겨있는 dist에 업데이트 해줬습니다.
어제 1916번 최소비용 구하기 문제를 풀며, 아직 다익스트라 알고리즘에 대해 이해가 부족하다고 느껴 해당 문제를 찾아서 풀어봤습니다.
문제: 도시의 개수, 도로의 개수, 찾고자 하는 거리 정보, 출발 도시의 번호, 그리고 도로의 정보가 주어졌을 때, 거리가 K인 도시를 찾는 문제입니다.
풀이 방법: 다익스트라 알고리즘을 활용했습니다.
풀이코드:
import sys
import heapq
n,m,k,x = map(int, sys.stdin.readline().rstrip().split())
graph = [[] *(n+1) for _ in range(n+1)]
for _ in range(m):
node1, node2 = map(int,sys.stdin.readline().rstrip().split())
graph[node1].append(node2)
q = [(0,x)]
dist = [1E9] * (n+1)
dist[x] = 0
while q:
cost, node = heapq.heappop(q)
if dist[node] < cost: continue
for i in graph[node]:
newCost, newNode = 1, i
distance = newCost + cost
if dist[newNode] > distance:
dist[newNode] = distance
heapq.heappush(q,(distance,newNode))
else:
continue
if dist.count(k) == 0:
print(-1)
else:
for j in range(1,n+1):
if dist[j] == k:
print(j)
풀이 설명:
graph에는 도시 ~ 도시 까지 도로 정보를 담습니다.
for _ in range(m):
node1, node2 = map(int,sys.stdin.readline().rstrip().split())
graph[node1].append(node2)
graph에는 도시 ~ 도시 까지 도로 정보를 담습니다.
q = [(0,x)]
dist = [1E9] * (n+1)
dist[x] = 0
그리고 heapq에는 (거리, 도시)의 값이 들어 갑니다. 초기 값은 (0, 시작 도시)로 설정합니다.
dist는 거리를 계산하여 담을 배열로 시작점 ~ 시작점의 거리는 0이므로, 0으로 설정해줍니다.
while q:
cost, node = heapq.heappop(q)
if dist[node] < cost: continue
for i in graph[node]:
newCost, newNode = 1, i
distance = newCost + cost
if dist[newNode] > distance:
dist[newNode] = distance
heapq.heappush(q,(distance,newNode))
else:
continue
while문을 통해서 갈 수 있는 도시들의 정보를 꺼냅니다.
다음 heapq를 통해 얻은 정보를 통해 for문으로 graph에서 연결된 도시 정보를 끌어옵니다.
마지막으로 연결된 도시의 거리정보를 계산한 다음 계속해서 거리정보 값들 중 작은 값으로 거리 값을 갱신해줍니다.(dist 배열)
시작점 = 1, 도로 정보 (1,2) (2,3) (3,4) 가 주어졌다고 가정해보겠습니다.
위 예시를 통해 자세히 설명하자면, heapq에는 초기값 (0,1)가 들어갔다가 while 문 안에서 (0,1)이 pop 되겠죠.
그럼 for문을 통해 1에서 갈 수 있는 2의 값이 꺼내지고(in graph[1]), 도시 1에서 2로 가는 거리의 값인 1이 dist[2]의 값으로 계산 된 후 다시 heapq에는 (1(dist),2(node))가 들어가게 됩니다.
그럼 다음 싸이클에서는 newCost = 1, newNode = 2가 나오게 되고, for문을 통해 2에서 갈 수 있는 노드를 찾게되겠죠.
그럼 또 (2,3)인 도로 정보가 graph[2]에 담겨있으니, 이번에는 1->2까지의 거리 + 2->3까지의 거리가 계산된 후 (2(dist),3(node))
결과적으로 노드 4까지 도달하게 되면, 1에서 2,3을 거쳐 4까지 도달하는 최소 거리가 계산되게 됩니다.
if dist.count(k) == 0:
print(-1)
else:
for j in range(1,n+1):
if dist[j] == k:
print(j)
시작점으로 부터 도달할 수 있는 모든 노드의 거리 정보를 계산하고 나면, 다음 구문을 통해 요구하는 결과 값을 출력해줍니다.
solved.ac의 class 4로 진입했는데 갑자기 난이도가 너무 높아져서 당황했습니다. 진짜 해결 방안이 쉽사리 떠오르지 않더라구요.
문제 푸는데 시간이 꽤 오래 걸린 문제였습니다...
문제: 도시 ~ 도시의 비용이 주어졌을 때, 출발 도시에서 도착 도시까지의 최소비용을 구하는 문제 입니다.
풀이 방법: heapq를 이용하여 최소 cost 계산.
풀이 설명:
일단 입력 값에 대해 다음과 같이 graph를 구성하였습니다.
for _ in range(m):
node1, node2, value = map(int,sys.stdin.readline().rstrip().split())
graph[node1].append((value,node2))
이때, 값을 (value,node) 순으로 구성한 이유는 heapq를 비용 기준으로 활용할 계획이기 때문입니다.
graph와 heapq를 통해 시작점으로 부터 갈 수 있는 노드의 비용들을 탐색하고, 이 과정에서 도착 노드에 대해 나오는 결과 값들 중 최소 값만 저장되도록 다음과 같이 코드를 작성하였습니다 .
heapq.heappush(heap, [0, start])# 초기 값을 시작점으로 setting
dist[start] = 0# 시작점 cost = 0
while heap:
cost, node = heapq.heappop(heap)
if cost > dist[node]:
continue
for i in graph[node]:# 시작점으로부터 도달할 수 있는 노드 탐색
nextCost, nextNode = i
distance = nextCost + cost
if dist[nextNode] > distance:
dist[nextNode] = distance# 기존 입력된 거리와 새로 계산된 거리의 최소 값 저장
heapq.heappush(heap, [distance, nextNode])
else:
continue
풀이코드:
import sys
import heapq
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
graph = [[]*(n+1) for _ in range(n+1)]
dist = [1E9]*(n+1)
heap = []
for _ in range(m):
node1, node2, value = map(int,sys.stdin.readline().rstrip().split())
graph[node1].append((value,node2))
start, destination = map(int,sys.stdin.readline().rstrip().split())
heapq.heappush(heap, [0, start])# 초기 값을 시작점으로 setting
dist[start] = 0# 시작점 cost = 0
while heap:
cost, node = heapq.heappop(heap)
if cost > dist[node]:
continue
for i in graph[node]:# 시작점으로부터 도달할 수 있는 노드 탐색
nextCost, nextNode = i
distance = nextCost + cost
if dist[nextNode] > distance:
dist[nextNode] = distance# 기존 입력된 거리와 새로 계산된 거리의 최소 값 저장
heapq.heappush(heap, [distance, nextNode])
else:
continue
print(dist[destination])
문제: 그림의 색상이 주어졌을 때, 적록색약인 사람과 적록 색약이 아닌 사람이 볼 수 있는 색상의 구역 수를 각각 구하는 문제 입니다.
(이때, 적록 색약인 사람은 빨강과 초록을 구분하지 못합니다.)
풀이 방법: 그래프 탐색 방법중 BFS로 문제를 풀었습니다.
풀이 설명:
문제는 총 3가지 idea에서 착안해서 풀었습니다.
1.
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
for k in range(4):
x = i + dx[k]
y = j + dy[k]
위 방식을 통한, 각 위치의 상하좌우 요소 탐색. (그래프 탐색 뿐만 아니라 해당 코드를 통해 간단하게 상하좌우 요소를 접근할 수 있다는 점에서 매우 유용한 코드라고 생각합니다.)
2. BFS 를 통한 그래프 탐색
3. 색약인 경우, 파란색을 기준으로 색 판별
if color != 'B' and array[x][y] != 'B':
visited[x][y] = True
q.append([x,y])
elif color == 'B' and array[x][y] == 'B':
visited[x][y] = True
q.append([x,y])
풀이코드:
import sys
from collections import deque
sys.setrecursionlimit(10000)
n = int(sys.stdin.readline())
array = [[]*n for _ in range(n)]
for i in range(n):
array[i] = list(sys.stdin.readline().strip())
cnt = 0
visited = [[False]*n for _ in range(n)]
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
def bfs(a,b,color):
q = deque()
q.append([a, b])
visited[a][b] = True
while q:
i, j = q.pop()
for k in range(4):
x = i + dx[k]
y = j + dy[k]
if x < 0 or x >= n or y < 0 or y >= n or visited[x][y]:
continue
if color == array[x][y]:
visited[x][y] = True
q.append([x,y])
return
def bfs_blind(a,b,color):
q = deque()
q.append([a,b])
visited[a][b] = True
while q:
i,j = q.pop()
for k in range(4):
x = i + dx[k]
y = j + dy[k]
if x < 0 or x >= n or y < 0 or y >= n or visited[x][y]:
continue
if color != 'B' and array[x][y] != 'B':
visited[x][y] = True
q.append([x,y])
elif color == 'B' and array[x][y] == 'B':
visited[x][y] = True
q.append([x,y])
return
for i in range(n):
for j in range(n):
if not visited[i][j]:
bfs(i,j,array[i][j])
cnt += 1
print(cnt,end=' ')
visited = [[False]*n for _ in range(n)]
cnt = 0
for i in range(n):
for j in range(n):
if not visited[i][j]:
bfs_blind(i,j,array[i][j])
cnt += 1
print(cnt)
일단 BFS 탐색 코드를 2가지로 나누어 구현하였습니다.
적록 색맹이 아닌 경우, 탐색 시작점의 색과 동일한지 여부만 판단하면 되는 반면에
적록 색맹인 경우, 빨간색과 초록색을 동일한 색으로 보고 판단해야하기 때문입니다.
이제 BFS 함수 내부에서 상하좌우 요소를 접근하는데,
if x < 0 or x >= n or y < 0 or y >= n or visited[x][y]:
continue
해당 코드를 통해 index가 배열을 벗어나는지를 판별함과 동시에 해당 위치를 방문한적이 있는지 판별하였습니다.
마지막으로 큐와 visited 배열을 활용하여 해당 노드를 방문한적 있는지 여부를 바탕으로 구역을 탐색하였습니다.
다른 풀이:
import sys
sys.setrecursionlimit(10000)
n = int(sys.stdin.readline())
array = [[]*n for _ in range(n)]
for i in range(n):
array[i] = list(sys.stdin.readline().strip())
cnt = 0
visited = [[False]*n for _ in range(n)]
def bfs(a,b,eyes,color):
dx = [0,0,-1,1]
dy = [-1,1,0,0]
for i in range(4):
x = a + dx[i]
y = b + dy[i]
if x < 0 or x >= n or y < 0 or y >=n or visited[x][y]:
continue
if(eyes == 'color-blindness'):
if((color != 'B') and array[x][y] != 'B'):
visited[x][y] = True
bfs(x, y, eyes, color)
elif(color == 'B' and array[x][y] =='B'):
visited[x][y] = True
bfs(x, y, eyes, color)
else:
continue
else:
if color == array[x][y]:
visited[x][y] = True
bfs(x,y,eyes,color)
return
for i in range(n):
for j in range(n):
if not visited[i][j]:
bfs(i,j,'!color-blindness',array[i][j])
cnt += 1
print(cnt,end=' ')
visited= [[False]*n for _ in range(n)]
cnt = 0
for i in range(n):
for j in range(n):
if not visited[i][j] :
bfs(i,j,'color-blindness',array[i][j])
cnt += 1
print(cnt)
이 코드를 통해 문제를 맞췄지만 문제를 다시 푼 이유는 다음과 같았습니다.
1. 그래프 탐색을 반복문이 아닌 재귀로 문제를 품으로써 메모리 사용량과 속도가 반복문에 비해 떨어질 것이라고 생각했습니다.
2. 함수를 호출 할 때마다, 색약의 여부에 따라 함수를 다르게 구현한 풀이 코드와 달리 색약을 판단하는 조건문이 계속적으로 동작하기 때문에 속도가 뒤떨어질 것이라고 판단했습니다.
첫번째가 풀이 코드인데요. 반복문으로 구현한 만큼 메모리는 적게 사용했지만 오히려 속도 부분에서는 느렸습니다.
반복적인 조건문의 동작과 재귀함수의 사용으로 인해 속도 부분은 확실하게 빠를 것이라 판단했지만 그렇지 않은 결과가 나와서 조금은 당황스러웠습니다.
해당 부분을 조금 더 공부한 후, 메모리와 속도 모두 효율적인 코드를 짤 수 있기 위해 노력하려고 합니다.
