본문 바로가기

전체 글23

Programmers. 합승 택시 요금 (2021 KAKAO BLIND RECRUITMENT) 합승 택시 요금에 대한 문제이다. 문제는 2가지로 풀어볼 수 있을 것 같다. 1번째로는 다익스트라, 2번째로는 플로이드-와샬이 가능하다고 생각했다. https://ds-jungsoo.tistory.com/7 Shortest Paths(다익스트라 알고리즘 (Dijkstra Algorithm)) 이번에는 다익스트라 알고리즘에 대해서 공부를 해보았다. 다익스트라 알고리즘은 단일 시작점으로부터 다른 노드들까지의 최단 경로를 구하는 알고리즘이다. 또한, 음의 가중치를 허용하지 ds-jungsoo.tistory.com 다익스트라에 대해서 공부했기 때문에 다익스트라로 생각해보았다. Dijkstra를 두번 사용하는 것으로 접근을 하였고, 1번째는 A,B가 같이 가는 구간 (합승 구역) 2번째는 합승 후, 각자 가는 구.. 2021. 11. 8.
Shortest Paths(다익스트라 알고리즘 (Dijkstra Algorithm)) 이번에는 다익스트라 알고리즘에 대해서 공부를 해보았다. 다익스트라 알고리즘은 단일 시작점으로부터 다른 노드들까지의 최단 경로를 구하는 알고리즘이다. 또한, 음의 가중치를 허용하지 않는 최단경로를 말한다. 위의 그림을 설명하자면, 시작점을 제외한 모든 저점과 시작점 사이의 거리를 무한으로 표현하고 다음과 같은 수행을 반복한다. 1. 현재 선택한 정점(처음엔 시작점)에 곧장 연결되고, 아직 방문하지 않은 정점들을 모두 본다. 2. 선택한 정점과 보고있는 정점 사이의 거리와 시작 정점과 선택한 정점까지의 최단거리의 합이 현재까지 구한 시작 정점과 보고 있는 정점 사이의 거리보다 짧을 경우, 이를 갱신해준다. 3. 1, 2번 수행이 모두 끝난 이후, 아직 방문하지 않은 정점들 중 시작점과의 거리가 가장 짧은 정.. 2021. 11. 2.
GCN : Graph convolution Network (2) 이어서 포스팅을 하려고 한다. GNN Layer는 크게 3가지 동작으로 나눌 수 있다. Aggregate (메시지 패싱) Combine (업데이트) Readout (Graph Level Task에서만) 아래 그림과 같이 어떠한 그래프가 Input으로 들어오게 되면 GNN Layer를 거쳐서 새로운 그래프가 형성이 된다고 보면 된다. 위의 3가지 동작을 설명하기 앞서서 GNN의 표기법에 대해서 짚고 넘어간다. 이렇게 표기가 되어있고, 이를 바탕으로 위의 그림을 다시 나타내자면, 위와 같이 나타낼 수 있다. 다시 돌아와서, 3가지 동작에 대해서 설명을 하고자 한다. 1. Aggregate : 타겟 노드의 이웃 노드들의 k-1시점의 hideen state를 결합한다. 2. Combine : k-1 시점 타겟 .. 2021. 11. 2.
백준 5904 : moo 게임 재귀함수 부분을 공부하고 moo게임이라는 풀어보았다. 겉으로 봤을 때 재미있어 보였으나, 쉽지 않았다. 문제를 해석하자면 S(0) = moo S(1) = S(0) mooo S(0) S(2) = S(1) moooo S(1) 이런식으로 반복되는 것을 알 수 있다. 결론적으로는 계속 씨름해보았지만 조금씩 엇나가서 완벽히 풀지 못했다. 생각을 비슷하게 한 https://hae-ong.tistory.com/82 백준 5904 moo 게임 처음엔 문제 그대로 수열을 재귀적으로 계속 만들다가 수열의 크기가 n 이상이 되면 재귀를 끝내고 해당 수열[n]으로 문자를 찾아주는 코드를 작성했으나 역시나 메모리 초과로 실패하였다. 따 hae-ong.tistory.com 이 분의 코드를 보면서 한번 더 배우는 계기가 되었다. .. 2021. 10. 25.

티스토리툴바