TL;DR 그래프란 정점(노드)와 간선(엣지)로 이루어진 자료구조로 정점 간의 관계를 나타내는 자료구조다. 구현 : 인접 행렬과 인접 리스트 그래프 탐색 : 하나의 정점으로부터 차례로 모든 정점들을 한 번씩 방문하기 너비 우선 탐색 BFS 깊이 우선 탐색 DFS 그래프 최단 경로 다익스트라 Dijkstra 플로드 와샬 Floyd-Washall 밸만 포드 Bellman-Ford 유니온 파인드 : 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조. union과 find 2개의 연산으로 조작 최소 스패닝 트리 : 그래프의 모든 정점이 사이클 없이 연결된 간선 합이 최소인 스패닝 트리 크루스칼과 프림 알고리즘으로 구현할 수 있다. 그래프 Graph 그래프는 정점(노드)와 간선(엣지)로 이루..

문제 다양한 모양과 크기의 명함들을 모두 수납할 수 있으면서, 작아서 들고 다니기 편한 지갑을 만들어야한다. 모든 명함을 수납할 수 있는 가장 작은 지갑을 만들 때, 지갑의 크기를 return 1

문제 다각형 모양의 둘레를 따라 캐릭터가 이동할 때, 특정 위치의 아이템을 줍기 위해 이동해야 하는 가장 짧은 거리 찾기 캐릭터의 위치 (cX, cY)와 아이템의 위치 (iX, iY)가 주어진다. 1

문제 다트 과녁에는 1 부터 20 까지의 수가 하나씩 있고 각 수마다 "싱글", "더블", "트리플" 칸이 있다. "싱글"을 맞히면 해당 수만큼 점수를 얻고 "더블"을 맞히면 해당 수의 두 배만큼 점수를 얻고 "트리플"을 맞히면 해당 수의 세 배만큼 점수를 얻습니다. 가운데에는 "불"을 맞추면 50점을 얻는다. 최소한의 다트로 target 점수를 만들어야 한다. 다트의 수가 동일하다면 "싱글" 또는 "불"을 최대한 많이 던지는 방법을 선택해야 한다. 1 dp[i-k][0] + 1:# 다트 최소개수 갱신 dp[i] = [ dp[i-k][0] + 1, dp[i-k][1]] elif dp[i][0] == dp[i-k][0] + 1 :# 싱글/불 최대개수 갱신 dp[i][1] = max(dp[i][1], dp[..

문제 [출발지, 도착지]의 항공권들을 모두 이용해 여행경로 짜기 항상 "ICN" 공항에서 출발 3

문제 지역은 번호로 구분되고 두 지역 간 길을 통과하는 데 1시간이 걸린다. roads 변수에는 길이 있는 두 지역의 번호를 포함하고 있다. 3