1. 위상정렬에 대해 위상정렬은 방향 그래프에서 사용되는 알고리즘 중 하나이다. 주로 모든 노드의 방향이 한쪽으로 정렬된 경우에 사용 가능하고(순서가 존재해야 함), 그래프에 사이클이 존재한다면 사용 불가능하다.(방향이 없어지기 때문.) 실제 알고리즘에서는 A를 수행하기 위한 선행조건 B가 있는 경우에 주로 사용된다. 알고리즘 문제에 등장하는 몇...

풀어본 최소 스패닝 트리 문제 중 어려웠던 문제를 정리했다. MST에 대한 개념은 아래 링크에서 정리했다. 최소 신장 트리 1. 세부 백준 13905번: 세부 난이도 골드 4의 최소 스패닝 트리 문제이다. 특정 발상을 요구했기에 체감은 골드 4보다 어려웠다. 1.1 발상 출발하는 섬과 도착하는 섬이 지정되어 있고, 두 섬을 잇는 경로들 ...

1. 최소 신장 트리? 1.1 개념 최소 신장 트리(MST)는 가중치가 있는 연결 그래프에서 다음의 조건을 만족해야 한다. 연결 그래프가 모든 정점을 포함해야 한다.(모두 이어져 있어야 한다.) 노드들 간의 사이클이 없어야 한다. 사용된 간선들의 가중치 합이 최소가 되어야 한다. 1.2 사용 기본적으로 전체 그래프에서의 최소 비...

파이썬 코드를 보다 보면 클래스 내에서 자주 등장하는 데코레이터인 @classmethod와 @staticmethod에 대해 자세히 알아보았다. 1. @staticmethod 1.1 특징 인스턴스에 접근하지 않는다. @staticmethod로 정의된 메서드는 함수의 인자로 클래스 인스턴스(’self’)나 클래스 그 자체(’...

풀었던 최단거리 문제(다익스트라, 플로이드 워셜 등) 중 개인적으로 어려웠던 문제들을 정리해보았다. 1. 궁금한 민호 백준 1507번: 궁금한 민호 난이도 골드 2의 플로이드 - 워셜 문제이다. 1.1 발상 플로이드 - 워셜 그래프가 미리 주어졌을때, 역으로 도시에 존재해야할 최소 갯수의 다리와, 모든 도로의 시간의 합을 구하는 문제이다. ...

풀었던 다익스트라 문제 중 개인적으로 어려웠던 문제들을 정리해보았다. 1. 집 구하기 백준 13911번: 집 구하기 난이도 골드2 의 다익스트라 문제이다. 1.1 발상 처음엔 반복문을 통해 모든 도시에서 맥날까지의 거리, 스타벅스까지의 거리를 구해 두 개의 합 중 가장 작은 값을 구하려 했다. 하지만 이 방식대로면 시간초과가 나온다. 다익스...

프론트 서버에서 실시간으로 API 정보를 전달받고 싶어서 웹소켓(Web Socket) 기술에 대해 알아보았다. 웹소켓이란? fastapi로 만든 백엔드 서버와 svelte로 만든 프론트엔드 서버로 웹소켓을 실습해보았다. 1. 1초마다 현재 시간 전송하기 from fastapi import FastAPI, WebSocket, WebSocke...

프론트 서버에서 실시간으로 API 정보를 전달받고 싶어서 웹소켓(Web Socket) 기술에 대해 알아보았다. 1. 웹소켓이란? 웹소켓(Web Socket)은 HTML5 사양의 일부로, 클라이언트와 서버 간의 양방향 통신을 가능하게 하는 프로토콜이다. 단순히 클라이언트와 서버 간의 통신만 한다면 평소에 사용하던 HTTP 통신과 다를 바 없다. 굳...

풀었던 DFS 문제 중 개인적으로 어려웠던 문제들을 정리해보았다. 3. 피리 부는 사나이 백준 16724번: 피리 부는 사나이 난이도 골드 3의 문제이다. 문제의 설명은 꽤나 복잡하지만 하나하나 뜯어보면 결국 맵에 존재하는 사이클의 숫자를 세는 문제이다. (하나의 사이클 안에 존재하는 장판은 모두 한 곳으로 수렴하기 때문.) 3.1 발상 맵...

1. 문제 상황 적은 학습, 빠른 결과물 출력을 위해 svelte를 도입해 간단한 프론트 페이지를 만들었다. 로컬에서는 원하는 기능이 모두 이루어졌지만, docker-compose를 통해 컨테이너를 만들어 프론트엔드 서버와 백엔드 서버가 서로 내부 통신을 하게 만들었더니 작동하지 않았다. 좀 더 구체적으로 문제 상황을 분석해보면 백엔드 서...