그래프

해당 포스팅은 프로그래밍 인사이트에서 출판한 (이브 포셀로, 알렉스 뱅크스 저)을 바탕으로 작성한 글임을 먼저 밝힙니다. GraphQL이란? 클라이언트의 종류가 다양해지고 복잡해지면서 서버로부터 데이터를 받아와서 빠르고 손실없이 클라이언트에 전송하는 기술은 끊임없이 발전해 왔고 현재도 진행 중에 있다. GraphQL은 이 과정에서 만들어진 쿼리 언어이다. GraphQL 쿼리는 실제로 필요한 데이터만 받도록 작성할 수 있다. 응답은 JSON 형태로 주어진다. 쿼리문을 중첩하여 실행하면 연관된 객체를 응답 데이터로 같이 받을 수도 있다. GraphQL 서버에서는 쿼리가 실행될 때마다 타입 시스템에 기초해 쿼리가 유효한지 검사한다. GraphQL 서비스를 만드려면 GraphQL 스키마에서 사용할 타입을 정의해..

이번 포스팅에서는 킥스타트 2020 Round D에 대한 문제 풀이를 공유하고자 한다. 1. Record Breaker 배열을 반복하면서 조건문을 통해 카운팅을 하면 쉽게 풀 수 있는 문제이다. 시간복잡도는 O(N) 2. Alien Piano 이 문제는 Greedy 알고리즘을 사용해서 풀었다. 먼저 배열을 통해 각각의 note의 pitch를 받아서 채워준다. 이 때 연속해서 같은 값이 나오게 되면 같은 alien piano key를 사용하게 되므로 배열에 넣어주지 않아도 된다. 이렇게 배열을 넣어 주었을 때 만약 다음과 같이 배열이 생겼다고 가정해 보자. 이 때는 연속해서 두 숫자가 같은 경우는 존재하지 않을 것이다. [1, 8, 9, 7, 6, 5, 4, 3, 2, 1, 3, 2, 1, 3, 5, 7]..

이번에 살펴볼 문제는 백준 1507번 궁금한 민호 문제이다. https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 www.acmicpc.net 이 문제는 플로이드 와셜 알고리즘을 통해 모든 경로를 탐색하여 푸는 문제이다. 모든 쌍의 최단 경로를 다 확인하는 문제로 이 알고리즘이 익숙하지 않으면 조금 생각하기 어려울 수도 있다. 먼저 플로이드 와셜 알고리즘에 대해 간단하게 설명한 후에 문제를 풀어 보도록 하겠다. 플로이드 와셜 알고리즘(Floyd Warshall Algorit..

오늘은 백준 1865번 웜홀 문제를 풀어보려고 한다. https://www.acmicpc.net/problem/1865 1865번: 웜홀 문제 때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다. 시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 한 지점에서 www.acmicpc.net 이 문제는 개인적으로 정말 많이 틀리고 나서 해결했던 문제이다. 그래서 더욱 꼼꼼하게 문..

이번 포스팅에서는 그래프 자료구조에 대해서 공부해 본다. 그래프 그래프(Graph)는 노드(node)와 그 노드를 연결하는 간선(edge)을 하나로 모아놓은 자료구조이다. 즉, 연결되어 있는 객체 간의 관계를 표현할 수 있다. 예를 들면 지하철에서 다른 역으로 가는 최단 경로를 찾아주는 서비스도 그래프 알고리즘을 사용한다. 그래프의 한 종류로 트리 자료구조가 있는데 그래프와 트리의 차이는 다음과 같다. 그래프 관련 용어를 정리하면 다음과 같다. 먼저 정점과 간선의 연결 관계에서 방향성을 가지는 지를 가지고 나누어 볼 수 있다. 방향성이 없는 그래프를 무향 그래프(Undirected Graph)라 하고, 방향성이 포함되어 있는 그래프를 유향 그래프(Directed Graph)라고 한다. 무향 그래프에서 각..