해당 글에서는 텀 프로젝트 문제를 Python을 이용해 풀이하고자 한다. 9466번: 텀 프로젝트이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을www.acmicpc.net 원래는 이 문제를 풀 생각이 아니었지만, 아래에 있는 Union-Find를 통해 무방향 그래프의 사이클을 구하는 알고리즘에 대해 공부하다가, 방향 그래프에서 사이클을 구하는 방법이 궁금해져 찾아보다가 해당 문제를 풀게 됐다. [알고리즘] Union-Find(유니온 파인드)로 무방향 그래프에서 사이클(cycle) 찾기1️⃣ 유니온 파인드란?Union-Find는 서로소 집합을 찾는 알고리즘으로, 서로..
해당 글에서는 부등호 문제를 Python을 이용해 풀이하고자 한다. 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시 www.acmicpc.net 🔷 문제 설명 더보기 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자. A ⇒ 부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열..
해당 게시글에서는 [백준] 13305 주유소 문제를 해설하고 Python을 이용하여 풀고자 한다. 💡 문제 풀이 13305번 문제는 Greedy에 대한 문제로 각 단계마다 최적의 상황을 선택하여 최종적인 해답에 도달하는 방식의 알고리즘이다. 이 문제에서는 제일 오른쪽 지점에 도달했을 때 기름의 비용이 최소가 되는 것을 원하므로, 각 도시를 지나기 위해 기름의 비용을 계산할 때 상황에 따라 작은 값을 이용하여 계산해야 한다. 만약 앞 도시의 기름의 비용이 뒷 도시의 기름의 비용보다 싸다면, 앞 도시에서 주유하는 것이 비용이 적게 드므로 뒷 도시에서 주유하는 것이 아닌 앞 도시에서 미리 주유해야 한다. 따라서 왼쪽에서 오른쪽으로 순차적으로 이동하면서 최소 비용을 저장하여 (최소 비용)*(각 도시 사이 거리)..
해당 게시글에서는 [백준] 1522 문자열 교환 문제를 해설하고 Python을 이용하여 풀고자 한다. 💡 문제 풀이 1522번 문제는 투 포인터에 대한 문제로 두 개의 포인터를 조절하여 두 포인터가 가리키는 값이 특정한 조건을 만족하도록 하는 방식의 알고리즘이다. 투 포인터 알고리즘 중에서도 두 포인터를 일정한 간격으로 이동하는 슬라이딩 윈도우 알고리즘에 해당한다. 슬라이딩 윈도우인 이유는 아래 문제 해설에서 설명하겠다. 이 문제에서 구하고자 하는 값은 a와 b로만 이루어진 문자열에 대해 a를 모두 연속으로 만들기 위한 최소 교환 횟수이다. 예시를 통해 풀이 방법을 설명하기 전에 다음을 이해하자! 1️⃣ 교환 후 연속된 a 문자열의 길이는 입력된 문자열 속 a의 개수와 같다. 2️⃣ 즉, a의 개수와 동..
