토요일이지만 아침 일찍부터 나와서 알찬 하루를 보냈다.
내일 쉬어야하므로... 근데 이 글을 쓰는 시점에, 이미 내일 아침에도 일찍 나와서 더 해보기로 했다.
메세지가 생각보다 잘 안돼서...! 7시쯤 나와서 올라가기 전까지 또 열심히 하다 가야지.
어쨌든 오늘 공부한 내용들을 정리해보겠다 :)
나만의 무기
명함생성 관련 로그인 오류 픽스
오전에는 명함생성 관련 오류를 해결했다.
태그도 이미지 피커로 넣을 수 있도록 해당 페이지를 담당한 팀원분이 수정 중에 발견한 오류였는데, 회원가입 직후 명함생성 후에 POST 요청을 보내면 정상적으로 처리되지 않는 것이었다. 확인해보니 로그인 정보가 없어서 ID가 null로 나왔다. 곰곰이 생각해보니, 로그인 정보는 login.dart에서 로그인을 했을 때에 저장이 된다. 하지만 signup 후에 바로 cardgenerator로 넘어가다보니, 현재 카드를 생성하는 주인공이 누구인지 그 ID를 가져오지 못하는 것이었다.
static final storage = FlutterSecureStorage();
dynamic userInfo = '';
saveIdSecure(id) async {
var val = jsonEncode(Login(객체));
await storage.write(key: '로그인', value: val);
}따라서 위와 같이 회원가입 직후에 서비스를 이용할 때에도 정상적으로 접근이 가능하도록 signup.dart를 업데이트 해주었다. 정상적으로 회원가입이 이루어지고 명함생성으로 넘어가는 경우엔, 로그인을 할 때와 동일하게 로그인 정보를 FlutterSecureStorage에 저장하도록 하였다!
채팅 구현을 위한 공부
오후에는 드디어 Flutter-Node.js를 활용해 어떡하면 실제 채팅 서비스를 구현할 수 있을지를 공부해보기 시작했다. 기존에도 뼈대는 다 만들어놓긴 했지만, 아직 서버나 DB를 구축하지 않은 상태에서 메세지를 보내면 state에 저장하도록 해서 업데이트 해주는... 즉 일방향적인 시연만 가능한 상태였다. 이를 실제 채팅서비스로 바꿔서 양방향 소통이 가능하도록 하는 것이 기술적 챌린지이다.
우선은 코딩애플 node.js 강의에 있는 채팅 관련 강의들을 쭉 들었다. 또한 각종 블로그를 찾아보며 공부를 했다. 특히 웹소켓과 socket.io 이 글이 괜찮았는데, 덕분에 ws를 쓰든 socket.io를 쓰든 알맞게 서버를 열어볼 수 있었다.
이후 실제로 구현해보는데 Flutter에서는 StreamBuilder라는 것을 활용하면 편하다고 해서 사용했지만, 역시나 쉬운 길은 없다.
하하하,,, 에러 해결을 위해 2시간 내내 씨름하고 각종 글을 찾아보았으나 만족스러운 답변을 찾지 못했다.
결국 스택오버플로우로 직접 진출. 형들 도와줘요 🥲 그나저나 오픽도 다시 따야하는데..? 영어가 많이 줄었다.
알고리즘 스터디
프로그래머스 - 배달
오늘 풀어본 문제는 배달이라는 문제였다.
다른 사람들은 문자열, 구현 문제가 어렵다고 하는 반면 나는 다익스트라, DFS 같이 그래프와 관련된 문제에 상대적으로 약한 편이다. 그냥 외워서 풀면 된다고들 하는데, 그런 것에는 막연한 거부감이 있었다. 물론 좋든 싫든 뛰어난 개발자가 되려면 극복해야 한다고 생각하기에, 정글이 끝나고나서 가장 먼저 할 일로 그래프 관련 알고리즘 정리를 다시 하려고 했다.
그런 와중에 스터디에서 다익스트라 문제가 나온게 처음이라서, 약간 당황했다. 기억도 안나는데...?
그래서 그냥 직접 짜버렸다.
큐를 활용한 풀이
from collections import defaultdict, deque
from math import inf
def solution(N, road, K):
/* defaultdict를 활용해 if u not in graph: graph[u] = list() 등의 초기화를 생략 */
graph = defaultdict(list)
for u,v,d in road:
graph[u].append([v,d])
graph[v].append([u,d])
delivery = [inf]*(N+1) // 비교를 통해 최단경로 소요시간으로 업데이트하기 위해, 배달시간은 무한대로 초기화
delivery[1] = 0 // 도시 1에서 배달을 시작하므로 도시 1까지 소요시간은 0이다.
q = deque([1]) // 큐 초기화. 도시 1에서 배달을 시작한다.
while q:
now_city = q.popleft() // 현재 방문한 도시. 이전에 최단경로였던 적이 있기에 큐에 들어있다.
for next_city, time in graph[now_city]:
if delivery[next_city] > delivery[now_city] + time:
/* 최단경로 소요시간 업데이트가 가능한 경우에만 처리해준 후에 q에 넣어줌*/
delivery[next_city] = delivery[now_city] + time
if next_city != 1:
q.append(next_city)
return len([x for x in delivery[1:] if x <= K]) // 거리가 K이하인 도시들의 갯수를 리턴나는 BFS, 즉 큐를 활용하는 방식을 생각해냈다.
어차피 1번 도시에서 출발하는건 똑같으니까, 1번 도시에서 갈 수 있는 다음 도시들을 쭉 큐에 넣어주는 것이다. 그리고, 하나씩 뽑아서 또 다음 도시들을 탐색하도록 만든다. 이 때, 새로운 경로 소요시간(현재 도시까지의 최단경로 소요시간 + 현재도시~ 다음 도시의 소요시간)와 기존의 다음 도시까지의 최단 경로 소요시간 비교한다. 만약 새로운 경로를 거치는게 기존 최단경로보다 소요시간이 짧다면, 그때만 새로운 경로를 통해 다음 도시를 방문하고, 그걸 q에 넣어주는 방식으로 풀어냈다. 
풀고나서 코드리뷰를 하다보니, 완벽한 다익스트라 풀이는 아니었다. 그리고 next_city != 1은 어차피 절대 실행될 일이 없으니 불필요한 조건이었다. 문제 조건(배달시간은 1이상 500,000 이하)에 따라, 어떤 경로로 1번 도시에 방문해도, 최초로 설정해놓은 시간 0보다 짧아질 수 없다.
그래도 생각해서 짠게 거의 비슷하게 나온 것이니 만족....! (물론 이전에 공부한게 어렴풋이 기억났겠지만)
힙을 활용한 풀이
사실 좀 더 효율적인 풀이는 heap을 활용하는 것이다. 외운 것이 아니라 깨달은 김에, 정리해보고자 한다. 정리에서는 '시간' 대신에 일반적으로 통용되는 '거리'를 기준으로 작성하도록 하겠다.
heap에서 뽑았을 때 4번 도시로 도달하기까지의 B경로의 경유 거리 총합, 즉 [해당 경로로 방문도시까지 지나온 거리, 방문도시]가 나왔다고 하자. 그리고 그 거리의 총합은 10km이었다고 가정해보자. 해당 시점에 만약 이전에 이미 A경로로 4번 도시을 방문하는 경우가 heap에서 뽑아나와 처리되었다고 가정해보자. 이 때, 2가지 선택지가 존재한다.
만약 A경로로 4번 도시에 도달하기까지의 거리가 8km였다면, 이미 B경로는 4번 도시에 도달하기 위한 최단 경로가 아니게 된다. 따라서, 굳이 처리할 필요없이 다음 선택지를 heap에서 뽑아내게 하면 될 것이다. 참고로 그 거리가 10km였다고 해도, 이미 A경로를 통해 4번 도시에 방문한 후에 다음 도시들을 heap에 넣어줬을테니, 8km인 경우와 동일하게 다음 선택지로 넘어가면 될 것이다. 물론 애초에 heap이라 짧은 거리의 경로들이 빨리빨리 뽑혀나왔을 것이기에, 이런 경우는 자주 발생하지 않는 것 같다.
그 외에는 현재 뽑아나온 경로를 기준으로 다음 도시로의 경로를 탐색해주면 되겠다. 4번 도시에서 다른 도시로의 경로도 새롭게 탐색하기 위해서 [10km + 4번 도시~다음 도시를 연결하는 거리 길이, 4번 도시에 연결된 다음 도시]를 heap에 넣어주면 될 것이다. 다만 (10km + 4번 도시~다음 도시 거리) 값보다 현재 기준으로 다음 도시까지의 최단 거리가 이미 짧다면, B경로는 그 다음 도시까지의 최단경로가 될 수 없으므로 굳이 heap에 추가하지 않아도 된다. 대신 heap에 추가해주는 경우, 즉 새로운 경로가 더 매력적인 경우, 해당 다음 도시까지의 최단 거리도 미리 업데이트 해둔다. 그래야 heap에서 뽑아나온 선택지가 의미없을 때, 더 빨리 쳐낼수가 있다.
이를 코드로 풀어내면 다음과 같다.
from collections import defaultdict
from heapq import heappush, heappop
from math import inf
def solution(N, road, K):
answer = 0
graph = defaultdict(list)
for u,v,d in road:
graph[u].append([v,d])
graph[v].append([u,d])
delivery = [inf]*(N+1)
delivery[1] = 0
heap = []
heappush(heap, [0,1])
while heap:
now_time, now_city = heappop(heap)
if delivery[now_city] < now_time:
continue
for next_city, now_to_next_time in graph[now_city]:
new_next_time = now_time + now_to_next_time
if delivery[next_city] > new_next_time:
delivery[next_city] = new_next_time
heappush(heap, [new_next_time, next_city])
return len([x for x in delivery[1:] if x <= K])
큐로 풀었을 때에 비해 테스트 25,26,27 등의 속도가 확연하게 빠르다 ! 1ms의 차이도 엄청난 것이므로..
내일은 일요일이지만, message를 구현하기 위해 중간중간 작업할 것 같다.
그래도 좀 가닥이 잡히는 것 같아서 즐겁다 :D 😋
