1. 그래프(Graph)란? 그래프란 실제 세계의 현상이나 사물의 정점(Vertex) 또는 노드(Node)와 간선(Edge)로 표현하기 위해 사용한다. 위 이미지에서 A, B, C, D, E는 정점에 해당하며 각 정점들을 잇는 선은 간선에 해당한다. 2. 그래프 관련 용어 📌 주요 용어 노드(Node): 위치를 말하며, 정점(Vertex)라고도 함 간선(Edge): 위치 간의 관계를 표시한 선으로 노드를 연결한 선임(Link 또는 branch라고도 함) 인점 정점(Adjacent Vertex): 간선으로 직접 연결된 정점(또는 노드) 📌 참고 용어 정점의 차수 (Degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 진입 차수 (In-Degree): 방향 그래프에서 외부에서 오는 간선의 수 진..
해당 게시글에서는 [백준] 13305 주유소 문제를 해설하고 Python을 이용하여 풀고자 한다. 💡 문제 풀이 13305번 문제는 Greedy에 대한 문제로 각 단계마다 최적의 상황을 선택하여 최종적인 해답에 도달하는 방식의 알고리즘이다. 이 문제에서는 제일 오른쪽 지점에 도달했을 때 기름의 비용이 최소가 되는 것을 원하므로, 각 도시를 지나기 위해 기름의 비용을 계산할 때 상황에 따라 작은 값을 이용하여 계산해야 한다. 만약 앞 도시의 기름의 비용이 뒷 도시의 기름의 비용보다 싸다면, 앞 도시에서 주유하는 것이 비용이 적게 드므로 뒷 도시에서 주유하는 것이 아닌 앞 도시에서 미리 주유해야 한다. 따라서 왼쪽에서 오른쪽으로 순차적으로 이동하면서 최소 비용을 저장하여 (최소 비용)*(각 도시 사이 거리)..
해당 게시글에서는 [백준] 1522 문자열 교환 문제를 해설하고 Python을 이용하여 풀고자 한다. 💡 문제 풀이 1522번 문제는 투 포인터에 대한 문제로 두 개의 포인터를 조절하여 두 포인터가 가리키는 값이 특정한 조건을 만족하도록 하는 방식의 알고리즘이다. 투 포인터 알고리즘 중에서도 두 포인터를 일정한 간격으로 이동하는 슬라이딩 윈도우 알고리즘에 해당한다. 슬라이딩 윈도우인 이유는 아래 문제 해설에서 설명하겠다. 이 문제에서 구하고자 하는 값은 a와 b로만 이루어진 문자열에 대해 a를 모두 연속으로 만들기 위한 최소 교환 횟수이다. 예시를 통해 풀이 방법을 설명하기 전에 다음을 이해하자! 1️⃣ 교환 후 연속된 a 문자열의 길이는 입력된 문자열 속 a의 개수와 같다. 2️⃣ 즉, a의 개수와 동..
해당 게시글에서는 [백준] 12847 꿀 아르바이트 문제를 해설하고 Python을 이용하여 풀고자 한다. 💡 문제 풀이 1522번 문제는 투 포인터에 대한 문제 중에서도 슬라이딩 윈도우 알고리즘 문제에 해당한다. 슬라이딩 윈도우 알고리즘이 된 이유는 다음의 조건 때문이다. 한 번이라도 퇴직한 자를 다시 취직 시키지 않는다.(만약 취직을 한다면, 일을 시작 한 날부터 끝날 때까지 하루도 빠지면 안 된다.) 즉, 준수가 일을 할 수 있는 날(m)이 주어졌을 때 일을 시작한 날(st)로부터 m일 동안 빠짐없이 일해야 한다는 것이다. 따라서 준수가 최대 이익을 얻기 위해선 시작한 날(st)로부터 m일 동안 일했을 때의 이익을 모든 경우에 대해서 구하고 최댓값을 출력해주면 된다. m일이라는 길이가 계속 고정되기 ..
